102102024-03-29 14:50:50111Misztikus táblázatcpp17Időlimit túllépés 40/1001.103s154752 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];
	for(int i=2;i<=K;i++){
		set<int>s,z;
		for(int j=1;j<=L;j++){
			s.insert(X[i][j]);
			z.insert(X[i-1][j]);
		}
		int y=0;
		for(int j=1;j<=N;j++){
			y+=!s.count(j)&&!z.count(j);
		}
		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
1Elfogadva3ms1828 KiB
2Elfogadva3ms2052 KiB
3Elfogadva787ms89676 KiB
subtask20/5
4Időlimit túllépés1.083s80752 KiB
5Időlimit túllépés1.065s100832 KiB
6Időlimit túllépés1.07s120348 KiB
7Időlimit túllépés1.077s131796 KiB
subtask30/9
8Elfogadva3ms69920 KiB
9Elfogadva3ms70272 KiB
10Időlimit túllépés1.103s131816 KiB
11Időlimit túllépés1.067s131748 KiB
subtask415/15
12Elfogadva3ms69668 KiB
13Elfogadva3ms69628 KiB
14Elfogadva3ms69508 KiB
15Elfogadva3ms69640 KiB
16Elfogadva3ms69856 KiB
17Elfogadva3ms69952 KiB
18Elfogadva3ms69960 KiB
19Elfogadva3ms70084 KiB
subtask50/16
20Elfogadva3ms70172 KiB
21Elfogadva3ms70176 KiB
22Időlimit túllépés1.087s131812 KiB
23Elfogadva48ms133168 KiB
24Elfogadva711ms154752 KiB
subtask625/25
25Elfogadva17ms72032 KiB
26Elfogadva13ms71972 KiB
27Elfogadva18ms72160 KiB
28Elfogadva3ms71284 KiB
29Elfogadva8ms71768 KiB
30Elfogadva14ms72108 KiB
31Elfogadva12ms71760 KiB
32Elfogadva12ms71832 KiB
subtask70/30
33Elfogadva222ms139492 KiB
34Elfogadva180ms138336 KiB
35Időlimit túllépés1.103s131812 KiB
36Elfogadva65ms130580 KiB
37Elfogadva765ms148432 KiB
38Időlimit túllépés1.062s118428 KiB
39Időlimit túllépés1.08s111580 KiB
40Elfogadva202ms134524 KiB
41Elfogadva949ms153288 KiB
42Időlimit túllépés1.037s122220 KiB