102112024-03-29 14:54:35111Misztikus táblázatcpp17Elfogadva 100/100488ms182960 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MOD 1000000007

int inv(int x){
	int p=MOD-2;
	int r=1;
	for(int p=MOD-2;p;p>>=1){
		if(p&1){
			r*=x;
			r%=MOD;
		}
		x*=x;
		x%=MOD;
	}
	return r;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K,L;
	cin>>N>>K>>L;
	int X[K+1][L+1];
	for(int i=1;i<=K;i++){
		for(int j=1;j<=L;j++){
			cin>>X[i][j];
		}
	}
	int F[N+1];
	F[0]=1;
	for(int i=1;i<=N;i++){
		F[i]=F[i-1]*i%MOD;
	}
	int FI[N+1];
	for(int i=0;i<=N;i++){
		FI[i]=inv(F[i]);
	}
	int dp[N+1][N+1];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=N;i++){
		dp[0][i]=0;
		dp[i][0]=F[i]*F[i]%MOD;
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]+=dp[i-1][j]*(i-j)*(i-j);
			dp[i][j]+=dp[i-1][j-1]*j*(i-j)*2;
			if(j>=2){
				dp[i][j]+=j*(j-1)*dp[i-1][j-2];
			}
			dp[i][j]%=MOD;
		}
	}
	for(int i=0;i<=N;i++){
		for(int j=0;j<=i;j++){
			dp[i][j]*=FI[i];
			dp[i][j]%=MOD;
		}
	}
	// for(int i=1;i<=N;i++){
		// for(int j=0;j<=i;j++){
			// vector<int>v(i),w(i);
			// for(int k=0;k<j;k++){
				// v[k]=w[k]=k;
			// }
			// for(int k=j;k<i;k++){
				// v[k]=i+k;
				// w[k]=i*2+k;
			// }
			// int ans=0;
			// do{
				// int ok=1;
				// for(int k=0;k<i;k++){
					// ok&=v[k]!=w[k];
				// }
				// ans+=ok;
			// }
			// while(next_permutation(w.begin(),w.end()));
			// if(ans!=dp[i][j]){
				// cout<<i<<' '<<j<<endl;
				// cout<<"got "<<dp[i][j]<<'\n';
				// cout<<"exp "<<ans<<'\n';
				// exit(1);
			// }
		// }
	// }
	int ans=F[N-L];
	int v[N+1];
	for(int i=2;i<=K;i++){
		memset(v,0,sizeof(v));
		for(int j=1;j<=L;j++){
			v[X[i][j]]++;
			v[X[i-1][j]]++;
		}
		int y=0;
		for(int j=1;j<=N;j++){
			y+=v[j]==0;
		}
		ans*=dp[N-L][y];
		ans%=MOD;
	}
	for(int i=K+1;i<=N;i++){
		ans*=dp[N][N];
		ans%=MOD;
	}
	cout<<ans<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1888 KiB
2Elfogadva3ms2124 KiB
3Elfogadva172ms89496 KiB
subtask25/5
4Elfogadva451ms138980 KiB
5Elfogadva481ms161764 KiB
6Elfogadva488ms181056 KiB
7Elfogadva467ms181156 KiB
subtask39/9
8Elfogadva3ms56216 KiB
9Elfogadva3ms56140 KiB
10Elfogadva451ms178280 KiB
11Elfogadva481ms181508 KiB
subtask415/15
12Elfogadva3ms56416 KiB
13Elfogadva3ms56632 KiB
14Elfogadva3ms56860 KiB
15Elfogadva3ms57072 KiB
16Elfogadva3ms57308 KiB
17Elfogadva3ms57340 KiB
18Elfogadva2ms57336 KiB
19Elfogadva3ms57176 KiB
subtask516/16
20Elfogadva2ms57068 KiB
21Elfogadva3ms57192 KiB
22Elfogadva458ms180828 KiB
23Elfogadva39ms119896 KiB
24Elfogadva180ms140892 KiB
subtask625/25
25Elfogadva6ms58308 KiB
26Elfogadva6ms58260 KiB
27Elfogadva7ms58588 KiB
28Elfogadva3ms57980 KiB
29Elfogadva4ms58356 KiB
30Elfogadva4ms58536 KiB
31Elfogadva4ms58576 KiB
32Elfogadva4ms58564 KiB
subtask730/30
33Elfogadva75ms125824 KiB
34Elfogadva76ms124544 KiB
35Elfogadva479ms182960 KiB
36Elfogadva50ms118572 KiB
37Elfogadva150ms136188 KiB
38Elfogadva314ms156408 KiB
39Elfogadva246ms142968 KiB
40Elfogadva57ms122656 KiB
41Elfogadva194ms141500 KiB
42Elfogadva333ms163908 KiB