QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68632#4787. Entanglement275307894aWA 2ms10136kbC++141.7kb2022-12-17 22:27:072022-12-17 22:27:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-17 22:27:09]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10136kb
  • [2022-12-17 22:27:07]
  • 提交

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'