QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419365#1423. Bingrass8cow#AC ✓4748ms48876kbC++172.0kb2024-05-23 20:58:342024-05-23 20:58:36

Judging History

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

  • [2024-05-23 20:58:36]
  • 评测
  • 测评结果:AC
  • 用时:4748ms
  • 内存:48876kb
  • [2024-05-23 20:58:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,G=3,GI=(mod+1)/3,inv2=(mod+1)/2;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
int L,lb[1<<21];
void init(int n){
    L=1;while(L<=n)L<<=1;
    for(int i=1;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0);
}
int wi[1<<21][2];
void NTT(int *a,int fl){
	for(int i=0;i<L;i++)if(i<lb[i])swap(a[i],a[lb[i]]);
	for(int o=1;o<L;o<<=1){
		for(int i=0;i<L;i+=(o<<1))for(int j=0;j<o;j++){
			int x=a[i+j],y=1ll*a[i+j+o]*wi[j+o][fl]%mod;
			a[i+j]=x+y;if(a[i+j]>=mod)a[i+j]-=mod;
            a[i+j+o]=x+mod-y;if(a[i+j+o]>=mod)a[i+j+o]-=mod;
		}
	}
	if(!fl){
		int I=qpow(L,mod-2);
		for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod; 
	}
}
int n,m,f[1010000];
int p[1<<21],q[1<<21];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void cdq(int l,int r){
    if(l==r){
        if(l==1)return;
        if(!(l&1))
            (f[l]+=1ll*f[l/2]*f[l/2]%mod)%=mod;
        f[l]=1ll*f[l]*inv2%mod;
        for(int j=l/2+1;j<=(l+m)/2&&j<l;j++)
        (f[l]+=1ll*f[j]*f[l-j]%mod)%=mod;
        return;
        //2j>i,2j<=i+m
    }
    int mi=(l+r)>>1;cdq(l,mi);init(r-l+mi-l+1);
    for(int i=0;i<L;i++)p[i]=q[i]=0;
    for(int i=l;i<=mi;i++)p[i-l]=f[i];
    for(int i=1;i<=mi&&i<=r-l;i++)q[i]=f[i];
    NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
    NTT(p,0);
    for(int i=mi+1;i<=r;i++)ad(f[i],p[i-l]);
    //---
    for(int i=0;i<L;i++)p[i]=q[i]=0;
    for(int i=l;i<=mi;i++)p[i-l]=f[i];
    for(int i=1;i<l&&i<=r-l;i++)q[i]=f[i];
    NTT(p,1),NTT(q,1);for(int i=0;i<L;i++)p[i]=1ll*p[i]*q[i]%mod;
    NTT(p,0);
    for(int i=mi+1;i<=r;i++)ad(f[i],p[i-l]);
    cdq(mi+1,r);
}
int main(){
    for(int fl=0;fl<2;fl++)for(int o=1;o<(1<<21);o<<=1){
        int Wn=qpow(fl?G:GI,(mod-1)/(o<<1)),w=1;
        for(int i=0;i<o;i++,w=1ll*w*Wn%mod)wi[i+o][fl]=w;
    }
    scanf("%d%d",&n,&m);f[1]=1;
    cdq(1,n);
    printf("%d",f[n]);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 22ms
memory: 26508kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 15ms
memory: 26512kb

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 18ms
memory: 26440kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 15ms
memory: 26320kb

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 15ms
memory: 26376kb

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 18ms
memory: 26508kb

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 15ms
memory: 26500kb

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

score: 0
Accepted
time: 22ms
memory: 26324kb

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

score: 0
Accepted
time: 22ms
memory: 26476kb

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

score: 0
Accepted
time: 22ms
memory: 26436kb

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

score: 0
Accepted
time: 18ms
memory: 26440kb

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 199ms
memory: 26956kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: 0
Accepted
time: 4748ms
memory: 48748kb

input:

787788 78

output:

394429402

result:

ok 1 number(s): "394429402"

Test #14:

score: 0
Accepted
time: 15ms
memory: 26404kb

input:

5 92

output:

14

result:

ok 1 number(s): "14"

Test #15:

score: 0
Accepted
time: 22ms
memory: 26376kb

input:

88 79

output:

931161641

result:

ok 1 number(s): "931161641"

Test #16:

score: 0
Accepted
time: 24ms
memory: 26416kb

input:

749 77

output:

615055472

result:

ok 1 number(s): "615055472"

Test #17:

score: 0
Accepted
time: 26ms
memory: 26524kb

input:

2281 89

output:

282226588

result:

ok 1 number(s): "282226588"

Test #18:

score: 0
Accepted
time: 34ms
memory: 26524kb

input:

5765 35

output:

293680396

result:

ok 1 number(s): "293680396"

Test #19:

score: 0
Accepted
time: 112ms
memory: 26756kb

input:

43189 12

output:

805295564

result:

ok 1 number(s): "805295564"

Test #20:

score: 0
Accepted
time: 4416ms
memory: 48816kb

input:

806855 5

output:

593114139

result:

ok 1 number(s): "593114139"

Test #21:

score: 0
Accepted
time: 4575ms
memory: 48836kb

input:

994514 45

output:

678426421

result:

ok 1 number(s): "678426421"

Test #22:

score: 0
Accepted
time: 4561ms
memory: 48696kb

input:

999921 62

output:

752162081

result:

ok 1 number(s): "752162081"

Test #23:

score: 0
Accepted
time: 4611ms
memory: 48876kb

input:

995033 94

output:

130314865

result:

ok 1 number(s): "130314865"

Test #24:

score: 0
Accepted
time: 4534ms
memory: 48872kb

input:

901438 97

output:

809128292

result:

ok 1 number(s): "809128292"

Test #25:

score: 0
Accepted
time: 4554ms
memory: 48780kb

input:

993020 0

output:

926771801

result:

ok 1 number(s): "926771801"

Test #26:

score: 0
Accepted
time: 4629ms
memory: 48836kb

input:

1000000 100

output:

470305140

result:

ok 1 number(s): "470305140"