QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690892#3799. It's Surely Complexydzr00000AC ✓3261ms107132kbC++173.3kb2024-10-31 07:57:402024-10-31 07:57:41

Judging History

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

  • [2024-10-31 07:57:41]
  • 评测
  • 测评结果：AC
  • 用时：3261ms
  • 内存：107132kb
查看
  • [2024-10-31 07:57:40]
  • 提交

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 void Output(){printf("%lld %lld\n",rl,im);}
};
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],M1[1100001],M2[1100001],M3[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));
    
    
    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++)
        M1[i]=a[i]*a[i];
    for(int i=0;i<lim;i++)
        M2[i]=a[i]*b[i];
    for(int i=0;i<lim;i++)
        M3[i]=b[i]*b[i];
    FFT(M1,-1);FFT(M2,-1);FFT(M3,-1);
    for(int i=0;i<lim;i++)
    {
        M1[i]=M1[i]/(1.00*lim)+0.5;
        M2[i]=M2[i]/(1.00*lim)+0.5;
        M3[i]=M3[i]/(1.00*lim)+0.5;
    }

    memset(c,0,sizeof(c));
    for(int i=0;i<lim;i++)
        c[i%p]+=(long long)M3[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++)
        c[i%p]+=(long long)M2[i].real();
    c[0]--;
    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++)
        c[i%p]+=(long long)M1[i].real();
    c[0]--;
    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=1;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);

    Ans.Output();

    return 0;
}
源文件, 语言: C++17

详细

Test #1:

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

input:

2 1

output:

1 1

result:

ok single line: '1 1'

Test #2:

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

input:

2 2

output:

1 1

result:

ok single line: '1 1'

Test #3:

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

input:

2 3

output:

0 0

result:

ok single line: '0 0'

Test #4:

score: 0
Accepted
time: 3ms
memory: 23356kb

input:

2 4

output:

0 0

result:

ok single line: '0 0'

Test #5:

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

input:

3 1

output:

2 1

result:

ok single line: '2 1'

Test #6:

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

input:

3 2

output:

2 0

result:

ok single line: '2 0'

Test #7:

score: 0
Accepted
time: 2ms
memory: 24184kb

input:

3 3

output:

1 0

result:

ok single line: '1 0'

Test #8:

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

input:

3 4

output:

1 1

result:

ok single line: '1 1'

Test #9:

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

input:

3 5

output:

1 0

result:

ok single line: '1 0'

Test #10:

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

input:

3 6

output:

1 0

result:

ok single line: '1 0'

Test #11:

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

input:

5 1

output:

4 1

result:

ok single line: '4 1'

Test #12:

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

input:

5 2

output:

0 0

result:

ok single line: '0 0'

Test #13:

score: 0
Accepted
time: 3ms
memory: 23188kb

input:

5 3

output:

0 0

result:

ok single line: '0 0'

Test #14:

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

input:

5 4

output:

0 0

result:

ok single line: '0 0'

Test #15:

score: 0
Accepted
time: 3ms
memory: 23444kb

input:

5 5

output:

0 0

result:

ok single line: '0 0'

Test #16:

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

input:

5 6

output:

0 0

result:

ok single line: '0 0'

Test #17:

score: 0
Accepted
time: 2ms
memory: 22532kb

input:

5 7

output:

0 0

result:

ok single line: '0 0'

Test #18:

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

input:

5 8

output:

0 0

result:

ok single line: '0 0'

Test #19:

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

input:

5 9

output:

0 0

result:

ok single line: '0 0'

Test #20:

score: 0
Accepted
time: 2ms
memory: 22612kb

input:

5 10

output:

0 0

result:

ok single line: '0 0'

Test #21:

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

input:

7 1

output:

6 1

result:

ok single line: '6 1'

Test #22:

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

input:

7 2

output:

3 0

result:

ok single line: '3 0'

Test #23:

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

input:

7 3

output:

2 5

result:

ok single line: '2 5'

Test #24:

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

input:

7 4

output:

1 0

result:

ok single line: '1 0'

Test #25:

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

input:

7 5

output:

5 2

result:

ok single line: '5 2'

Test #26:

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

input:

7 6

output:

6 0

result:

ok single line: '6 0'

Test #27:

score: 0
Accepted
time: 3ms
memory: 23248kb

input:

7 7

output:

1 0

result:

ok single line: '1 0'

Test #28:

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

input:

7 8

output:

4 4

result:

ok single line: '4 4'

Test #29:

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

input:

7 9

output:

4 0

result:

ok single line: '4 0'

Test #30:

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

input:

7 10

output:

2 2

result:

ok single line: '2 2'

Test #31:

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

input:

7 11

output:

1 0

result:

ok single line: '1 0'

Test #32:

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

input:

7 12

output:

4 4

result:

ok single line: '4 4'

Test #33:

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

input:

7 13

output:

1 0

result:

ok single line: '1 0'

Test #34:

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

input:

7 14

output:

1 0

result:

ok single line: '1 0'

Test #35:

score: 0
Accepted
time: 3ms
memory: 23892kb

input:

2 1000000000000000000

output:

0 0

result:

ok single line: '0 0'

Test #36:

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

input:

3 1000000000000000000

output:

1 1

result:

ok single line: '1 1'

Test #37:

score: 0
Accepted
time: 3165ms
memory: 107132kb

input:

499979 1000000000000000000

output:

486292 0

result:

ok single line: '486292 0'

Test #38:

score: 0
Accepted
time: 3261ms
memory: 106784kb

input:

499973 1000000000000000000

output:

0 0

result:

ok single line: '0 0'

Test #39:

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

input:

2 576460752303423488

output:

0 0

result:

ok single line: '0 0'

Test #40:

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

input:

3 864691128455135232

output:

1 0

result:

ok single line: '1 0'

Test #41:

score: 0
Accepted
time: 2ms
memory: 23204kb

input:

43 41

output:

32 11

result:

ok single line: '32 11'

Test #42:

score: 0
Accepted
time: 2ms
memory: 23972kb

input:

89 646243632056227082

output:

0 0

result:

ok single line: '0 0'

Test #43:

score: 0
Accepted
time: 4ms
memory: 22276kb

input:

79 3818048575756175

output:

61 18

result:

ok single line: '61 18'

Test #44:

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

input:

43 417918461

output:

1 0

result:

ok single line: '1 0'

Test #45:

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

input:

67 9225777529942049

output:

26 0

result:

ok single line: '26 0'

Test #46:

score: 0
Accepted
time: 2ms
memory: 23280kb

input:

29 1894616718601

output:

0 0

result:

ok single line: '0 0'

Test #47:

score: 0
Accepted
time: 3ms
memory: 22836kb

input:

73 24891833259

output:

0 0

result:

ok single line: '0 0'

Test #48:

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

input:

751 45

output:

36 715

result:

ok single line: '36 715'

Test #49:

score: 0
Accepted
time: 3ms
memory: 22804kb

input:

631 870852734504724166

output:

101 0

result:

ok single line: '101 0'

Test #50:

score: 0
Accepted
time: 5ms
memory: 22228kb

input:

479 939006

output:

52 0

result:

ok single line: '52 0'

Test #51:

score: 0
Accepted
time: 2ms
memory: 23448kb

input:

503 223239772447

output:

381 0

result:

ok single line: '381 0'

Test #52:

score: 0
Accepted
time: 5ms
memory: 23084kb

input:

317 73782933513241136

output:

0 0

result:

ok single line: '0 0'

Test #53:

score: 0
Accepted
time: 5ms
memory: 23632kb

input:

577 4897864747011

output:

0 0

result:

ok single line: '0 0'

Test #54:

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

input:

571 7326187013

output:

400 171

result:

ok single line: '400 171'

Test #55:

score: 0
Accepted
time: 14ms
memory: 26492kb

input:

9787 39

output:

953 8834

result:

ok single line: '953 8834'

Test #56:

score: 0
Accepted
time: 25ms
memory: 22940kb

input:

4177 296229723194145403

output:

0 0

result:

ok single line: '0 0'

Test #57:

score: 0
Accepted
time: 29ms
memory: 25712kb

input:

5039 71501150263015946

output:

4425 4425

result:

ok single line: '4425 4425'

Test #58:

score: 0
Accepted
time: 17ms
memory: 25148kb

input:

7027 44142

output:

6075 0

result:

ok single line: '6075 0'

Test #59:

score: 0
Accepted
time: 3ms
memory: 22844kb

input:

1877 5605079

output:

0 0

result:

ok single line: '0 0'

Test #60:

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

input:

2251 187

output:

1847 404

result:

ok single line: '1847 404'

Test #61:

score: 0
Accepted
time: 4ms
memory: 22948kb

input:

3863 699

output:

3850 13

result:

ok single line: '3850 13'

Test #62:

score: 0
Accepted
time: 153ms
memory: 46436kb

input:

92557 64

output:

28440 0

result:

ok single line: '28440 0'

Test #63:

score: 0
Accepted
time: 360ms
memory: 35604kb

input:

62047 410196757795686372

output:

11479 11479

result:

ok single line: '11479 11479'

Test #64:

score: 0
Accepted
time: 264ms
memory: 43932kb

input:

67129 2833304630

output:

0 0

result:

ok single line: '0 0'

Test #65:

score: 0
Accepted
time: 447ms
memory: 46504kb

input:

90793 25188225487855

output:

0 0

result:

ok single line: '0 0'

Test #66:

score: 0
Accepted
time: 89ms
memory: 35952kb

input:

55313 111467

output:

0 0

result:

ok single line: '0 0'

Test #67:

score: 0
Accepted
time: 327ms
memory: 46852kb

input:

69151 718198020401

output:

9621 59530

result:

ok single line: '9621 59530'

Test #68:

score: 0
Accepted
time: 99ms
memory: 35588kb

input:

48571 56301

output:

2628 0

result:

ok single line: '2628 0'

Test #69:

score: 0
Accepted
time: 690ms
memory: 103448kb

input:

326983 51

output:

39793 287190

result:

ok single line: '39793 287190'

Test #70:

score: 0
Accepted
time: 2635ms
memory: 103456kb

input:

406183 933021611983655873

output:

238788 167395

result:

ok single line: '238788 167395'

Test #71:

score: 0
Accepted
time: 768ms
memory: 69440kb

input:

152729 7971425537345

output:

0 0

result:

ok single line: '0 0'

Test #72:

score: 0
Accepted
time: 385ms
memory: 67876kb

input:

183047 6977

output:

141264 41783

result:

ok single line: '141264 41783'

Test #73:

score: 0
Accepted
time: 413ms
memory: 68724kb

input:

207973 3240

output:

0 0

result:

ok single line: '0 0'

Test #74:

score: 0
Accepted
time: 585ms
memory: 69568kb

input:

141907 10497585978

output:

141777 141777

result:

ok single line: '141777 141777'

Test #75:

score: 0
Accepted
time: 696ms
memory: 104988kb

input:

279317 6562

output:

0 0

result:

ok single line: '0 0'
English 繁體中文 简体中文

服务器时间: 2025-02-01 22:52:48 | 开源项目