102102024-03-29 14:50:50111Misztikus táblázatcpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted3ms2052 KiB
3Accepted787ms89676 KiB
subtask20/5
4Time limit exceeded1.083s80752 KiB
5Time limit exceeded1.065s100832 KiB
6Time limit exceeded1.07s120348 KiB
7Time limit exceeded1.077s131796 KiB
subtask30/9
8Accepted3ms69920 KiB
9Accepted3ms70272 KiB
10Time limit exceeded1.103s131816 KiB
11Time limit exceeded1.067s131748 KiB
subtask415/15
12Accepted3ms69668 KiB
13Accepted3ms69628 KiB
14Accepted3ms69508 KiB
15Accepted3ms69640 KiB
16Accepted3ms69856 KiB
17Accepted3ms69952 KiB
18Accepted3ms69960 KiB
19Accepted3ms70084 KiB
subtask50/16
20Accepted3ms70172 KiB
21Accepted3ms70176 KiB
22Time limit exceeded1.087s131812 KiB
23Accepted48ms133168 KiB
24Accepted711ms154752 KiB
subtask625/25
25Accepted17ms72032 KiB
26Accepted13ms71972 KiB
27Accepted18ms72160 KiB
28Accepted3ms71284 KiB
29Accepted8ms71768 KiB
30Accepted14ms72108 KiB
31Accepted12ms71760 KiB
32Accepted12ms71832 KiB
subtask70/30
33Accepted222ms139492 KiB
34Accepted180ms138336 KiB
35Time limit exceeded1.103s131812 KiB
36Accepted65ms130580 KiB
37Accepted765ms148432 KiB
38Time limit exceeded1.062s118428 KiB
39Time limit exceeded1.08s111580 KiB
40Accepted202ms134524 KiB
41Accepted949ms153288 KiB
42Time limit exceeded1.037s122220 KiB