QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#459584 | #8833. Equalizer Ehrmantraut | ucup-team1231# | WA | 1004ms | 19556kb | C++14 | 2.8kb | 2024-06-30 08:46:40 | 2024-06-30 08:55:34 |
Judging History
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