Submission #870273

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define	foreach( gg,itit )	for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define	mp make_pair
#define	pb push_back
#define sz(a) int((a).size())
#define all(a)  a.begin(), a.end()
#define	debug(ccc)	cout << #ccc << " = " << ccc << endl;
#define present(c,x) ((c).find(x) != (c).end())
const double eps = 1e-8;
#define EQ(a,b) (fabs((a)-(b))<eps)
inline int max(int a,int b){return a<b?b:a;}
inline int min(int a,int b){return a>b?b:a;}
inline ll max(ll a,ll b){return a<b?b:a;}
inline ll min(ll a,ll b){return a>b?b:a;}
const int mod = 1e9+7;
const int N = 4e6+10;
const ll inf = 1e18;

ll power(ll a,ll n){
	if(n==0){
		return 1;
	}
	ll b = power(a,n/2);
	b = b*b%mod;
	if(n%2) b= b*a%mod;
	return b;
}

int add(int a,int b){ return (a+b)%mod;}
int mul(int a,int b){ return (ll)a*b%mod;}

int n,k;
ll dp[2010][2010],F[N], inv[N];

ll nCk(int n,int k){
	if(k>n)	return 0;
	return F[n]*inv[k]%mod*inv[n-k]%mod;
}

ll f(int i,int j){
	if(i==n && j==n)	return 1;
	ll &ret = dp[i][j];
	if(ret!=-1) return ret;
	ret = 0;
	if(i!=n){
		ret = f(i+1,j);
	}
	if(i>j){
		ret = (ret+ (n-j)*f(i,j+1)%mod*nCk(n*k-i-j*(k-1)-1,k-2))%mod;
		// printf("%d %d %lld\n",n*k-i-j*(k-1)-1,k-2,nCk(n*k-i-j*(k-1)-1,k-2));
	}
	return ret;
}


int main(){
 // 	freopen("nice.in","r",stdin);
 // freopen("nice.out","w",stdout);
	scanf("%d %d",&n,&k);
	if(k==1){
		printf("1\n");return 0;
	}
	FILL(dp,-1);
	F[0] = inv[0] = 1;
	REPP(i,1,N) F[i] = F[i-1]*i%mod;
	inv[N-1] = power(F[N-1],mod-2);
	for(int i=N-2;i>=1;i--){
		inv[i] = inv[i+1]*(i+1)%mod;
		assert(inv[i]*F[i]%mod==1);
	}
	printf("%lld\n",f(0,0));
	return 0;
}

Submission Info

Compile Error

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

Judge Result