QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#437406#8782. Schoolgirlsucup-team1004WA 6ms3916kbC++142.1kb2024-06-09 10:02:002024-06-09 10:02:00

Judging History

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

  • [2024-06-14 13:48:47]
  • hack成功,自动添加数据
  • (/hack/679)
  • [2024-06-14 13:05:18]
  • hack成功,自动添加数据
  • (/hack/678)
  • [2024-06-14 12:22:35]
  • hack成功,自动添加数据
  • (/hack/676)
  • [2024-06-09 10:02:00]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3916kb
  • [2024-06-09 10:02:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e4+10,M=3e4+10,V=N+M;
bool isprime(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return 0;
	}
	return 1;
}
int n,m,q,mod,g;
ll qpow(ll x,ll y=mod-2,ll ans=1){
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
vector<int>d;
bool chk(int x){
	for(int y:d){
		if(qpow(x,(mod-1)/y)==1)return 0;
	}
	return 1;
}
void init(int n=mod-1){
	d.clear();
	for(int i=2;i*i<=n;i++)if(n%i==0){
		d.push_back(i);
		for(;n%i==0;n/=i);
	}
	for(g=2;!chk(g);g++);
}
struct opts{
	int a,b,c;
}o[M];
int no[N],w[V];
vector<int>t[N];
void solve(){
	init();
	int base=qpow(g,(mod-1)/n);
	for(int i=1,cur=1;i<=n;i++){
		w[i]=cur,cur=1ll*cur*base%mod;
	}
	for(int i=1;i<=m;i++){
		w[n+i]=(0u+w[o[i].c]+w[o[i].a]+mod-w[o[i].b])%mod;
	}
	// debug(ary(w,1,n));
	for(int i=1;i<=q;i++)if(!no[i]){
		if((mod-1)%t[i].size()){
			no[i]=1;
			continue;
		}
		int c=0;
		for(int x:t[i])(c+=w[x])%=mod;
		c=c*qpow(t[i].size())%mod;
		vector<int>p;
		int iv=qpow((w[t[i].back()]-c+mod)%mod);
		for(int x:t[i])p.push_back(1ll*iv*(w[x]-c+mod)%mod);
		base=qpow(g,(mod-1)/t[i].size());
		int cur=1;
		vector<int>s;
		for(int x:t[i])s.push_back(cur),cur=1ll*cur*base%mod;
		sort(all(p)),sort(all(s));
		if(p!=s)no[i]=1;//,debug(mod,i,p,s,base);
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&o[i].a,&o[i].b,&o[i].c);
	}
	for(int i=1,x;i<=q;i++){
		scanf("%d",&x);
		t[i].resize(x);
		for(int &y:t[i])scanf("%d",&y);
	}
	set<int>test;
	mt19937 rnd(time(0));
	for(;test.size()<100;){
		int lim=1e9/n/2,p=(rnd()%lim+1)*n*2+1;
		if(test.count(p))continue;
		if(isprime(p))test.insert(p);
	}
	for(int x:test)mod=x,solve();
	for(int i=1;i<=q;i++)puts(no[i]?"No":"Yes");
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

详细

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 3916kb

input:

3 6 8
1 2 3
3 1 4
5 4 3
3 1 2
4 5 3
4 5 2
6 4 7 6 5 1 2
3 1 3 2
3 1 1 8
4 2 5 6 7
3 2 1 4
3 6 5 9
3 4 7 9
4 1 3 2 8

output:

Yes
Yes
No
No
No
No
Yes
No

result:

wrong answer expected YES, found NO [3rd token]