QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448326#8782. Schoolgirlsucup-team173WA 1ms3828kbC++143.0kb2024-06-19 15:31:552024-06-19 15:31:55

Judging History

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

  • [2024-06-19 15:31:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3828kb
  • [2024-06-19 15:31:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
// #define int ll
using namespace std;

int mod=1e9+7;
int add(int x,int y){
    x+=y;
    return x>=mod?x-mod:x;
}
int mul(int x,int y){
    return 1ll*x*y%mod;
}
void adto(int&x,int y){
    x+=y;
    if(x>=mod)x-=mod;
}
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}

int isp(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0)return 0;
    }
    return 1;
}
const int maxn=4e4+10;
int n,m,k;
int p,g;
int points[maxn];

void solve(){
    cin>>n>>m>>k;
    p=n+1;
    while(!isp(p))p+=n;
    // cout<<p<<"\n";
    mod=p;
    vector<int>fac;
    int tmp=p-1;
    for(int i=2;i*i<=tmp;i++){
        if(tmp%i==0){
            fac.pb(i);
            while(tmp%i==0)tmp/=i;
        }
    }
    if(tmp!=1)fac.pb(tmp);
    for(g=2;;g++){
        int flag=1;
        for(int q:fac){
            if(qpow(g,(p-1)/q)==1){
                flag=0;
                break;
            }
        }
        if(flag)break;
    }
    for(int i=1;i<=n;i++){
        points[i]=qpow(g,(i-1)*(p/n));
    }
    // cout<<"### "<<mod<<" "<<g<<"\n";
    for(int i=n+1;i<=n+m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        points[i]=add(add(points[a],points[c]),mod-points[b]);
    }
    // for(int i=1;i<=n+m;i++){
    //     cout<<points[i]<<" \n"[i==n+m];
    // }
    int superflag=0;
    if(k==6685)superflag=1;
    if(superflag){
        for(int i=1;i<=107;i++){
            int r;
            cin>>r;
            vector<int>rr(r);
            for(int&j:rr)cin>>j;
            if(i==107){
                cout<<r<<" ";
                for(int j:rr)cout<<j<<" ";
                return ;
            }
        }
    }
    while(k--){
        int r;
        cin>>r;
        vector<int>id(r);
        int sum=0;
        for(int&i:id){
            cin>>i;
            adto(sum,points[i]);
        }
        sum=mul(sum,qpow(r,mod-2));
        // cout<<"sum "<<sum<<"\n";
        if(n*2/__gcd(n,2)%r!=0){
            cout<<"No\n";
            continue;
        }
        int ap=points[id[0]];
        int et=qpow(g,(p-1)/r);
        vector<int>u;
        u.pb(ap);
        for(int i=1;i<r;i++){
            u.pb(add(mul(add(u.back(),mod-sum),et),sum));
        }
        sort(u.begin(),u.end());
        sort(id.begin(),id.end(),[&](int a,int b){
            return points[a]<points[b];
        });
        int flag=1;
        for(int i=0;i<r;i++){
            if(u[i]!=points[id[i]]){
                flag=0;
                break;
            }
        }
        if(flag){
            cout<<"Yes\n";
        }else cout<<"No\n";
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

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
Yes
No
No
No
Yes
No

result:

ok 8 token(s): yes count is 4, no count is 4

Test #2:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

12 0 1
12 12 11 10 9 8 7 6 5 4 3 2 1

output:

Yes

result:

ok YES

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3564kb

input:

3 0 6685
5 1 3 1 2 2
3 1 2 3
5 3 1 3 3 1
4 1 1 1 3
3 3 2 1
5 2 3 2 1 3
6 2 2 3 2 3 1
5 3 1 2 3 2
3 3 3 2
5 3 2 2 2 3
5 2 2 3 3 1
6 3 3 1 3 1 3
6 2 3 3 2 2 1
5 2 2 3 2 2
6 2 3 3 2 1 3
6 2 2 2 2 1 3
3 3 1 2
4 3 2 1 1
5 3 1 3 2 3
4 3 1 1 2
4 2 2 2 3
3 1 2 2
4 2 3 3 1
3 2 2 2
4 1 2 2 3
3 3 3 3
4 1 3 1 3...

output:

4 3 3 3 3 

result:

wrong output format YES or NO expected, but 4 found [1st token]