102092024-03-29 14:48:22111Misztikus táblázatcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1956 KiB
2Hibás válasz3ms2024 KiB
3Időlimit túllépés1.101s47672 KiB
subtask20/5
4Időlimit túllépés1.069s80644 KiB
5Időlimit túllépés1.057s100648 KiB
6Időlimit túllépés1.069s120144 KiB
7Időlimit túllépés1.072s131792 KiB
subtask30/9
8Hibás válasz2ms69788 KiB
9Időlimit túllépés1.098s69660 KiB
10Időlimit túllépés1.06s131748 KiB
11Időlimit túllépés1.052s131812 KiB
subtask40/15
12Hibás válasz3ms70036 KiB
13Elfogadva3ms69996 KiB
14Hibás válasz3ms70004 KiB
15Elfogadva3ms70224 KiB
16Hibás válasz3ms70224 KiB
17Elfogadva3ms70228 KiB
18Elfogadva3ms70284 KiB
19Elfogadva3ms70152 KiB
subtask50/16
20Hibás válasz940ms70152 KiB
21Időlimit túllépés1.046s70392 KiB
22Időlimit túllépés1.065s131812 KiB
23Időlimit túllépés1.082s101324 KiB
24Időlimit túllépés1.069s117404 KiB
subtask60/25
25Időlimit túllépés1.069s76272 KiB
26Időlimit túllépés1.065s76428 KiB
27Időlimit túllépés1.069s76996 KiB
28Időlimit túllépés1.069s76404 KiB
29Időlimit túllépés1.065s76840 KiB
30Időlimit túllépés1.029s76752 KiB
31Időlimit túllépés1.069s76868 KiB
32Időlimit túllépés1.041s77000 KiB
subtask70/30
33Időlimit túllépés1.059s112140 KiB
34Időlimit túllépés1.062s112744 KiB
35Időlimit túllépés1.072s131816 KiB
36Időlimit túllépés1.07s99584 KiB
37Időlimit túllépés1.067s112632 KiB
38Időlimit túllépés1.072s131800 KiB
39Időlimit túllépés1.067s131748 KiB
40Időlimit túllépés1.067s122188 KiB
41Időlimit túllépés1.067s131812 KiB
42Időlimit túllépés1.06s131812 KiB