QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#437406 | #8782. Schoolgirls | ucup-team1004 | WA | 6ms | 3916kb | C++14 | 2.1kb | 2024-06-09 10:02:00 | 2024-06-09 10:02:00 |
Judging History
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
Details
Tip: Click on the bar to expand more detailed information
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]