Submission #826572

---

Source Code Expand

#include<cstdio>
#include<algorithm>

using namespace std;

const long long mod = 1000000007;

long long fact[4000400];
long long ifact[4000400];
long long invs[4000400];

const int MA = 4000300;

void init(){
	//factorial
	invs[1] = 1;
	for(int i = 2; i < MA; ++i){
		long long k = mod / i;
		long long l = mod % i;
		long long tmp = -k * invs[l];
		tmp %= mod;
		if(tmp < 0) tmp += mod;
		invs[i] = tmp;
	}
	
	fact[0] = 1;
	ifact[0] = 1;
	for(int i = 1; i < MA; ++i){
		fact[i] = (fact[i - 1] * i) % mod;
		ifact[i] = (ifact[i - 1] * invs[i]) % mod;
	}
}

long long C(int n, int k){
	if(k < 0 || k > n) return 0;
	long long res = fact[n];
	res *= ifact[k];
	res %= mod;
	res *= ifact[n - k];
	res %= mod;
	return res;
}

int N, K;

long long dp[2020][2020];
long long sum[2020][2020];

long long solve(){
	if(K == 1) return 1;
	for(int i = 0; i <= N; ++i){
		for(int j = 0; j <= N; ++j){
			dp[i][j] = 0;
			sum[i][j] = 0;
		}
	}
	dp[N][1] = 1;
	sum[N][1] = 1;
	sum[N][0] = 1;
	for(int i = N - 1; i >= 1; --i){
		for(int j = 1; j <= N; ++j){
			int d = N - i;
			if(j > d + 1){
				dp[i][j] = 0;
				continue;
			}
			int num = d * K - (j - 1);
			int cur = K - 1;
			long long coe = C(num + cur - 1, cur - 1);
			dp[i][j] += dp[i + 1][j - 1] * coe;
			dp[i][j] %= mod;
			
			coe = C(num + cur - 1, cur - 1);
			dp[i][j] += sum[i + 1][j] * coe;
			dp[i][j] %= mod;
		}
		sum[i][N] = dp[i][N];
		for(int j = N - 1; j >= 0; --j){
			sum[i][j] = (sum[i][j + 1] + dp[i][j]) % mod;
		}
	}
	long long ans = 0;
	for(int i = 0; i <= N; ++i){
		ans += dp[1][i];
		ans %= mod;
	}
	ans *= fact[N];
	ans %= mod;
	return ans;
}

int main(){
	scanf("%d%d", &N, &K);
	init();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
                       ^

Judge Result