10209 2024. 03. 29 14:48:22 111 Misztikus táblázat cpp17 Hibás válasz 0/100 1.101s 131816 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1956 KiB
2 Hibás válasz 3ms 2024 KiB
3 Időlimit túllépés 1.101s 47672 KiB
subtask2 0/5
4 Időlimit túllépés 1.069s 80644 KiB
5 Időlimit túllépés 1.057s 100648 KiB
6 Időlimit túllépés 1.069s 120144 KiB
7 Időlimit túllépés 1.072s 131792 KiB
subtask3 0/9
8 Hibás válasz 2ms 69788 KiB
9 Időlimit túllépés 1.098s 69660 KiB
10 Időlimit túllépés 1.06s 131748 KiB
11 Időlimit túllépés 1.052s 131812 KiB
subtask4 0/15
12 Hibás válasz 3ms 70036 KiB
13 Elfogadva 3ms 69996 KiB
14 Hibás válasz 3ms 70004 KiB
15 Elfogadva 3ms 70224 KiB
16 Hibás válasz 3ms 70224 KiB
17 Elfogadva 3ms 70228 KiB
18 Elfogadva 3ms 70284 KiB
19 Elfogadva 3ms 70152 KiB
subtask5 0/16
20 Hibás válasz 940ms 70152 KiB
21 Időlimit túllépés 1.046s 70392 KiB
22 Időlimit túllépés 1.065s 131812 KiB
23 Időlimit túllépés 1.082s 101324 KiB
24 Időlimit túllépés 1.069s 117404 KiB
subtask6 0/25
25 Időlimit túllépés 1.069s 76272 KiB
26 Időlimit túllépés 1.065s 76428 KiB
27 Időlimit túllépés 1.069s 76996 KiB
28 Időlimit túllépés 1.069s 76404 KiB
29 Időlimit túllépés 1.065s 76840 KiB
30 Időlimit túllépés 1.029s 76752 KiB
31 Időlimit túllépés 1.069s 76868 KiB
32 Időlimit túllépés 1.041s 77000 KiB
subtask7 0/30
33 Időlimit túllépés 1.059s 112140 KiB
34 Időlimit túllépés 1.062s 112744 KiB
35 Időlimit túllépés 1.072s 131816 KiB
36 Időlimit túllépés 1.07s 99584 KiB
37 Időlimit túllépés 1.067s 112632 KiB
38 Időlimit túllépés 1.072s 131800 KiB
39 Időlimit túllépés 1.067s 131748 KiB
40 Időlimit túllépés 1.067s 122188 KiB
41 Időlimit túllépés 1.067s 131812 KiB
42 Időlimit túllépés 1.06s 131812 KiB