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