QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#459584#8833. Equalizer Ehrmantrautucup-team1231#WA 1004ms19556kbC++142.8kb2024-06-30 08:46:402024-06-30 08:55:34

Judging History

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

  • [2024-06-30 08:55:34]
  • 评测
  • 测评结果:WA
  • 用时:1004ms
  • 内存:19556kb
  • [2024-06-30 08:46:40]
  • 提交

answer

#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SZ 666666
#define pb push_back
#define fi first
#define se second
#define mp make_pair
const int MOD=969999931;
const int omega=18844598;
int n,a[1005][1005],w[1005][1005];
ll v[1005][1005];
ll qp(ll a,ll b) {
    ll x=1; a%=MOD;
    while(b) {
        if(b&1) x=x*a%MOD;
        a=a*a%MOD; b>>=1;
    }
    return x;
}
ll ev(ll s) {
    // cerr<<"+\n";
    // calc det mod (x-s)
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j) {
            ll x=1;
            for(int ss=a[i][j];ss;--ss)
                x=x*s%MOD;
            v[i][j]=x*w[i][j]%MOD;
        }
    // cerr<<"+AA\n";
    ll r=1;
    for(int i=0;i<n;++i) {
        int j=i;
        while(j<n&&v[j][i]%MOD==0) ++j;
        if(j>=n) return 0;
        if(i!=j) {
            r=-r;
            for(int s=0;s<n;++s)
                swap(v[i][s],v[j][s]);
        }
        for(int s=0;s<n;++s) v[i][s]%=MOD;
        r=r*v[i][i]%MOD;
        if(r==0) return 0;
        ll iv=qp(v[i][i],MOD-2);
        for(int j=i+1;j<n;++j) {
            int vv=v[j][i]%MOD*iv%MOD;
            if(vv)
            for(int k=i+1;k<n;++k) {
                v[j][k]=(v[j][k]-(ll)vv*v[i][k]);
            }
            if(i%8==0) {
            for(int k=i+1;k<n;++k) v[j][k]%=MOD;
            }
        }
    }
    // cerr<<"+SS\n";
    return (r%MOD+MOD)%MOD;
}
ll ss[5];
ll PP[66],FF[66],QQ[66];
ll eval(ll*a,ll v) {
    ll x=0;
    for(int i=5;i>=0;--i)
        x=(x*v+a[i])%MOD;
    return x;
}
int main() {
    n=1e3;
//    cin>>n;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j) {
            a[i][j]=2;
//            cin>>a[i][j];
            w[i][j]=rand()%MOD;
        }
    PP[0]=1;
    ll o=1;
    for(int i=0;i<5;++i) {
        ss[i]=ev(o);
        ll Fe=eval(FF,o),Pe=eval(PP,o);
        ll sth=(ss[i]-Fe)*qp(Pe,MOD-2)%MOD;
        // cerr<<Fe<<"++"<<Pe<<"what"<<sth<<"++\n";
        // FF += PP * sth, PP *= x-o
        for(int j=0;j<=5;++j)
            FF[j]=(FF[j]+PP[j]*sth)%MOD;
        for(int j=0;j<=5;++j)
            QQ[j]=PP[j]*(-o)%MOD;
        for(int j=0;j<=5;++j)
            (QQ[j+1]+=PP[j])%=MOD;
        for(int j=0;j<=5;++j) PP[j]=QQ[j];
        o=o*omega%MOD;
        // cout<<ss[i]<<"++\n";
        // for(int j=0;j<=5;++j)
        //     cout<<FF[j]<<",";
        // cout<<"fff\n";
        // for(int j=0;j<=5;++j)
        //     cout<<QQ[j]<<",";
        // cout<<"xxx\n";
    }
        for(int j=0;j<5;++j) printf("%c",(FF[j]%MOD)?'Y':'N');
        printf("\n");
}
/*
x^{a[i][j]}

x^5-1=(x-1)(x-o)(x-o^2)(x-o^3)(x-o^4)

FFF mod P
?? mod (x-o)
FFF+something*P == ss[...] so that it equals to 0 when x=o

0 mod 1
xxx mod (x-o)

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1004ms
memory: 19556kb

input:

1 3

output:

YNNNN

result:

wrong output format Expected integer, but "YNNNN" found