10211 2024. 03. 29 14:54:35 111 Misztikus táblázat cpp17 Elfogadva 100/100 488ms 182960 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];
	int v[N+1];
	for(int i=2;i<=K;i++){
		memset(v,0,sizeof(v));
		for(int j=1;j<=L;j++){
			v[X[i][j]]++;
			v[X[i-1][j]]++;
		}
		int y=0;
		for(int j=1;j<=N;j++){
			y+=v[j]==0;
		}
		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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1888 KiB
2 Elfogadva 3ms 2124 KiB
3 Elfogadva 172ms 89496 KiB
subtask2 5/5
4 Elfogadva 451ms 138980 KiB
5 Elfogadva 481ms 161764 KiB
6 Elfogadva 488ms 181056 KiB
7 Elfogadva 467ms 181156 KiB
subtask3 9/9
8 Elfogadva 3ms 56216 KiB
9 Elfogadva 3ms 56140 KiB
10 Elfogadva 451ms 178280 KiB
11 Elfogadva 481ms 181508 KiB
subtask4 15/15
12 Elfogadva 3ms 56416 KiB
13 Elfogadva 3ms 56632 KiB
14 Elfogadva 3ms 56860 KiB
15 Elfogadva 3ms 57072 KiB
16 Elfogadva 3ms 57308 KiB
17 Elfogadva 3ms 57340 KiB
18 Elfogadva 2ms 57336 KiB
19 Elfogadva 3ms 57176 KiB
subtask5 16/16
20 Elfogadva 2ms 57068 KiB
21 Elfogadva 3ms 57192 KiB
22 Elfogadva 458ms 180828 KiB
23 Elfogadva 39ms 119896 KiB
24 Elfogadva 180ms 140892 KiB
subtask6 25/25
25 Elfogadva 6ms 58308 KiB
26 Elfogadva 6ms 58260 KiB
27 Elfogadva 7ms 58588 KiB
28 Elfogadva 3ms 57980 KiB
29 Elfogadva 4ms 58356 KiB
30 Elfogadva 4ms 58536 KiB
31 Elfogadva 4ms 58576 KiB
32 Elfogadva 4ms 58564 KiB
subtask7 30/30
33 Elfogadva 75ms 125824 KiB
34 Elfogadva 76ms 124544 KiB
35 Elfogadva 479ms 182960 KiB
36 Elfogadva 50ms 118572 KiB
37 Elfogadva 150ms 136188 KiB
38 Elfogadva 314ms 156408 KiB
39 Elfogadva 246ms 142968 KiB
40 Elfogadva 57ms 122656 KiB
41 Elfogadva 194ms 141500 KiB
42 Elfogadva 333ms 163908 KiB