10210 | 2024-03-29 14:50:50 | 111 | Misztikus táblázat | cpp17 | Időlimit túllépés 40/100 | 1.103s | 154752 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,z;
for(int j=1;j<=L;j++){
s.insert(X[i][j]);
z.insert(X[i-1][j]);
}
int y=0;
for(int j=1;j<=N;j++){
y+=!s.count(j)&&!z.count(j);
}
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 | 1828 KiB | ||||
2 | Elfogadva | 3ms | 2052 KiB | ||||
3 | Elfogadva | 787ms | 89676 KiB | ||||
subtask2 | 0/5 | ||||||
4 | Időlimit túllépés | 1.083s | 80752 KiB | ||||
5 | Időlimit túllépés | 1.065s | 100832 KiB | ||||
6 | Időlimit túllépés | 1.07s | 120348 KiB | ||||
7 | Időlimit túllépés | 1.077s | 131796 KiB | ||||
subtask3 | 0/9 | ||||||
8 | Elfogadva | 3ms | 69920 KiB | ||||
9 | Elfogadva | 3ms | 70272 KiB | ||||
10 | Időlimit túllépés | 1.103s | 131816 KiB | ||||
11 | Időlimit túllépés | 1.067s | 131748 KiB | ||||
subtask4 | 15/15 | ||||||
12 | Elfogadva | 3ms | 69668 KiB | ||||
13 | Elfogadva | 3ms | 69628 KiB | ||||
14 | Elfogadva | 3ms | 69508 KiB | ||||
15 | Elfogadva | 3ms | 69640 KiB | ||||
16 | Elfogadva | 3ms | 69856 KiB | ||||
17 | Elfogadva | 3ms | 69952 KiB | ||||
18 | Elfogadva | 3ms | 69960 KiB | ||||
19 | Elfogadva | 3ms | 70084 KiB | ||||
subtask5 | 0/16 | ||||||
20 | Elfogadva | 3ms | 70172 KiB | ||||
21 | Elfogadva | 3ms | 70176 KiB | ||||
22 | Időlimit túllépés | 1.087s | 131812 KiB | ||||
23 | Elfogadva | 48ms | 133168 KiB | ||||
24 | Elfogadva | 711ms | 154752 KiB | ||||
subtask6 | 25/25 | ||||||
25 | Elfogadva | 17ms | 72032 KiB | ||||
26 | Elfogadva | 13ms | 71972 KiB | ||||
27 | Elfogadva | 18ms | 72160 KiB | ||||
28 | Elfogadva | 3ms | 71284 KiB | ||||
29 | Elfogadva | 8ms | 71768 KiB | ||||
30 | Elfogadva | 14ms | 72108 KiB | ||||
31 | Elfogadva | 12ms | 71760 KiB | ||||
32 | Elfogadva | 12ms | 71832 KiB | ||||
subtask7 | 0/30 | ||||||
33 | Elfogadva | 222ms | 139492 KiB | ||||
34 | Elfogadva | 180ms | 138336 KiB | ||||
35 | Időlimit túllépés | 1.103s | 131812 KiB | ||||
36 | Elfogadva | 65ms | 130580 KiB | ||||
37 | Elfogadva | 765ms | 148432 KiB | ||||
38 | Időlimit túllépés | 1.062s | 118428 KiB | ||||
39 | Időlimit túllépés | 1.08s | 111580 KiB | ||||
40 | Elfogadva | 202ms | 134524 KiB | ||||
41 | Elfogadva | 949ms | 153288 KiB | ||||
42 | Időlimit túllépés | 1.037s | 122220 KiB |