QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68632 | #4787. Entanglement | 275307894a | WA | 2ms | 10136kb | C++14 | 1.7kb | 2022-12-17 22:27:07 | 2022-12-17 22:27:09 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=3e2+5,M=9e4+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=2e9+7;const db eps=1e-5;mt19937 rnd(263082);
int n,m,k,A[N][N],f[N][M],Ct[N];ll Ans;
void Add(int x,int y){for(int i=1;i<=n;i++) A[i][x]==y&&(Ct[i]+=!(f[i][y]++));}
void Del(int x,int y){for(int i=1;i<=n;i++) A[i][x]==y&&(Ct[i]-=!(--f[i][y]));}
namespace Trie{
int Si=1;map<int,int> son[M];vector<int> Id[M];
void Ins(int x){int Ns=1;for(int i=1;i<=n;i++) !son[Ns].count(A[i][x])&&(son[Ns][A[i][x]]=++Si),Ns=son[Ns][A[i][x]],Id[Ns].PB(x);}
void GA(int x,int d){
int i,j;if(!son[x].size()){ll Ts=1;for(i=1;i<=Id[x].size();i++) Ts=Ts*k%mod;Ans+=Ts;return;}
for(auto i:son[x]) for(int j:Id[i.second]) Del(j,i.first);ll Ts=1;
if(Ct[d]>1) Ts=0;for(auto i:son[x]) if(f[d][i.first]) Ts=0;if(!Ct[d]) Ts=Ts*(k-son[x].size())%mod;
for(i=d+1;i<=n;i++) if(Ct[i]>1) Ts=0;else if(!Ct[i]) Ts=Ts*k%mod;Ans+=Ts;
for(auto i:son[x]) {
for(int j:Id[i.second]) Add(j,i.first);Ct[x]==1&&(GA(i.second,d+1),0);for(int j:Id[i.second]) Del(j,i.first);
}
for(auto i:son[x]) for(int j:Id[i.second]) Add(j,i.first);
}
}
int main(){
int i,j;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&A[i][j]),Ct[i]+=!(f[i][A[i][j]]++);
for(i=1;i<=m;i++) Trie::Ins(i);Trie::GA(1,1);printf("%lld\n",Ans%mod);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9908kb
input:
2 2 2 1 1 1 2
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 1ms
memory: 10052kb
input:
2 1 2 1 2
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 10136kb
input:
3 3 6 6 5 6 6 5 6 5 6 5
output:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'