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 |