QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #690290 | #3799. It's Surely Complex | ydzr00000 | WA | 3ms | 18220kb | C++17 | 3.5kb | 2024-10-30 21:27:01 | 2024-10-30 21:27:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int p;
struct Complex{
long long rl,im;
Complex(long long x,long long y):rl(x),im(y){}
friend inline Complex operator+(const Complex &a,const Complex &b){return {(a.rl+b.rl)%p,(a.im+b.im)%p};}
friend inline Complex operator-(const Complex &a,const Complex &b){return {(a.rl-b.rl+p)%p,(a.im-b.im+p)%p};}
friend inline Complex operator*(const Complex &a,const Complex &b){return {(a.rl*b.rl%p-a.im*b.im%p+p)%p,(a.rl*b.im%p+a.im*b.rl%p)%p};}
};
inline Complex iqpow(Complex a,__int128 b)
{
Complex ans(1,0);
while(b)
{
if(b&1)
ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
const double PI=acos(-1.0);
complex<double>a[1100001],b[1100001];
int pos[1100001],cnt=0,lim=1;
inline void FFT(complex<double>*num,int typ)
{
for(int i=0;i<lim;i++)
if(i<pos[i])
swap(num[i],num[pos[i]]);
for(int mid=1;mid<lim;mid<<=1)
{
complex<double>Wn(cos(PI/mid),typ*sin(PI/mid));
int r=mid<<1;
for(int j=0;j<lim;j+=r)
{
complex<double>W(1,0);
for(int k=0;k<mid;k++,W=W*Wn)
{
complex<double>x=num[j+k],y=W*num[j+k+mid];
num[j+k]=x+y;
num[j+k+mid]=x-y;
}
}
}
}
int r[1200001],g[1200001],squ[500001];
long long c[500001];
int main(){
long long n;
cin>>p>>n;
Complex Num(1,0);
for(int i=1;i<p;i++)
Num=Num*(Complex){i,i};
Complex Ans(1,0);
Ans=Ans*iqpow(Num,n/p);
for(int i=1;i<=n%p;i++)
Ans=Ans*(Complex){i,i};
for(int i=0;i<p;i++)
squ[i]=1ll*i*i%p;
for(int i=0;i<p;i++)
{
r[squ[i]]++;
if(i<=n%p)
g[squ[i]]++;
}
while(lim<(p<<1))
{
lim<<=1;
cnt++;
}
for(int i=0;i<lim;i++)
pos[i]=(pos[i>>1]>>1)|((i&1)<<(cnt-1));
memset(c,0,sizeof(c));
for(int i=0;i<lim;i++)
{
a[i].real(g[i]);a[i].imag(0);
b[i].real(g[i]);b[i].imag(0);
}
FFT(a,1);FFT(b,1);
for(int i=0;i<lim;i++)
a[i]*=b[i];
FFT(a,-1);
for(int i=0;i<lim;i++)
a[i]=a[i]/(1.00*lim)+0.5;
for(int i=0;i<lim;i++)
c[i%p]+=(long long)a[i].real();
for(int i=0;i<=n%p;i++)
c[2*squ[i]%p]--;
for(int i=0;i<p;i++)
c[i]/=2;
for(int i=0;i<p;i++)
Ans=Ans*iqpow({0,i},c[i]);
memset(c,0,sizeof(c));
for(int i=0;i<lim;i++)
{
a[i].real(r[i]);a[i].imag(0);
b[i].real(g[i]);b[i].imag(0);
}
FFT(a,1);FFT(b,1);
for(int i=0;i<lim;i++)
a[i]*=b[i];
FFT(a,-1);
for(int i=0;i<lim;i++)
a[i]=a[i]/(1.00*lim)+0.5;
for(int i=0;i<lim;i++)
c[i%p]+=(long long)a[i].real();
for(int i=0;i<=n%p;i++)
c[2*squ[i]%p]--;
for(int i=0;i<p;i++)
Ans=Ans*iqpow(iqpow({0,i},c[i]),(n/p));
memset(c,0,sizeof(c));
for(int i=0;i<lim;i++)
{
a[i].real(r[i]);a[i].imag(0);
b[i].real(r[i]);b[i].imag(0);
}
FFT(a,1);FFT(b,1);
for(int i=0;i<lim;i++)
a[i]*=b[i];
FFT(a,-1);
for(int i=0;i<lim;i++)
a[i]=a[i]/(1.00*lim)+0.5;
for(int i=0;i<lim;i++)
c[i%p]+=(long long)a[i].real();
long long d=n/p;
for(int i=0;i<p;i++)
Ans=Ans*iqpow(iqpow({0,i},c[i]),(__int128)d*(d-1)/2);
for(int i=0;i<p;i++)
c[2*squ[i]%p]--;
for(int i=0;i<p;i++)
c[i]/=2;
for(int i=0;i<p;i++)
Ans=Ans*iqpow(iqpow({0,i},c[i]),d);
printf("%lld %lld\n",Ans.rl,Ans.im);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 16984kb
input:
2 1
output:
1 1
result:
ok single line: '1 1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 17736kb
input:
2 2
output:
1 1
result:
ok single line: '1 1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 17612kb
input:
2 3
output:
0 0
result:
ok single line: '0 0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 17300kb
input:
2 4
output:
0 0
result:
ok single line: '0 0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 17036kb
input:
3 1
output:
2 1
result:
ok single line: '2 1'
Test #6:
score: 0
Accepted
time: 3ms
memory: 16548kb
input:
3 2
output:
2 0
result:
ok single line: '2 0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 16912kb
input:
3 3
output:
1 0
result:
ok single line: '1 0'
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 18220kb
input:
3 4
output:
2 1
result:
wrong answer 1st lines differ - expected: '1 1', found: '2 1'