102092024-03-29 14:48:22111Misztikus táblázatcpp17Wrong answer 0/1001.101s131816 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;
		for(int j=1;j<=L;j++){
			s.insert(X[i][j]);
			s.insert(X[i-1][j]);
		}
		ans*=dp[N-L][L*2-s.size()];
		ans%=MOD;
	}
	for(int i=K+1;i<=N;i++){
		ans*=dp[N][N];
		ans%=MOD;
	}
	cout<<ans<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1956 KiB
2Wrong answer3ms2024 KiB
3Time limit exceeded1.101s47672 KiB
subtask20/5
4Time limit exceeded1.069s80644 KiB
5Time limit exceeded1.057s100648 KiB
6Time limit exceeded1.069s120144 KiB
7Time limit exceeded1.072s131792 KiB
subtask30/9
8Wrong answer2ms69788 KiB
9Time limit exceeded1.098s69660 KiB
10Time limit exceeded1.06s131748 KiB
11Time limit exceeded1.052s131812 KiB
subtask40/15
12Wrong answer3ms70036 KiB
13Accepted3ms69996 KiB
14Wrong answer3ms70004 KiB
15Accepted3ms70224 KiB
16Wrong answer3ms70224 KiB
17Accepted3ms70228 KiB
18Accepted3ms70284 KiB
19Accepted3ms70152 KiB
subtask50/16
20Wrong answer940ms70152 KiB
21Time limit exceeded1.046s70392 KiB
22Time limit exceeded1.065s131812 KiB
23Time limit exceeded1.082s101324 KiB
24Time limit exceeded1.069s117404 KiB
subtask60/25
25Time limit exceeded1.069s76272 KiB
26Time limit exceeded1.065s76428 KiB
27Time limit exceeded1.069s76996 KiB
28Time limit exceeded1.069s76404 KiB
29Time limit exceeded1.065s76840 KiB
30Time limit exceeded1.029s76752 KiB
31Time limit exceeded1.069s76868 KiB
32Time limit exceeded1.041s77000 KiB
subtask70/30
33Time limit exceeded1.059s112140 KiB
34Time limit exceeded1.062s112744 KiB
35Time limit exceeded1.072s131816 KiB
36Time limit exceeded1.07s99584 KiB
37Time limit exceeded1.067s112632 KiB
38Time limit exceeded1.072s131800 KiB
39Time limit exceeded1.067s131748 KiB
40Time limit exceeded1.067s122188 KiB
41Time limit exceeded1.067s131812 KiB
42Time limit exceeded1.06s131812 KiB