QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417612#8715. 放苹果grass8cow#AC ✓377ms23768kbC++172.1kb2024-05-22 20:07:092024-05-22 20:07:10

Judging History

This is the latest submission verdict.

  • [2024-05-22 20:07:10]
  • Judged
  • Verdict: AC
  • Time: 377ms
  • Memory: 23768kb
  • [2024-05-22 20:07:09]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,G=3,GI=(mod+1)/3;
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 n,m,jc[200100],ij[200100];
int C(int a,int b){
    return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int L,lb[1<<20];
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);
}
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){
		int Wn=qpow(fl?G:GI,(mod-1)/(o<<1));
		for(int i=0;i<L;i+=(o<<1))for(int j=0,w=1;j<o;j++,w=1ll*w*Wn%mod){
			int x=a[i+j],y=1ll*a[i+j+o]*w%mod;
			a[i+j]=(x+y)%mod,a[i+j+o]=(x-y)%mod;
		}
	}
	if(!fl){
		int I=qpow(L,mod-2);
		for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod; 
	}
}
int fz1[1<<20];
void Inv(int *a,int *b,int n){
	if(n==1){b[0]=qpow(a[0],mod-2);return;}
	int N=(n+1)>>1;Inv(a,b,N);
	init(2*n+5);
	for(int i=0;i<L;i++)fz1[i]=0;
	for(int i=0;i<n;i++)fz1[i]=a[i];
	for(int i=N;i<L;i++)b[i]=0;
	NTT(fz1,1),NTT(b,1);
	for(int i=0;i<L;i++)fz1[i]=1ll*b[i]*(2-1ll*b[i]*fz1[i]%mod)%mod;
	NTT(fz1,0);
	for(int i=0;i<n;i++)b[i]=fz1[i];
}
int ms[201000],f[1<<20],g[1<<20],h[1<<20];
int main(){
    scanf("%d%d",&n,&m);
    jc[0]=1;for(int i=1;i<=n+2;i++)jc[i]=1ll*i*jc[i-1]%mod;
    ij[n+2]=qpow(jc[n+2],mod-2);for(int i=n+2;i;i--)ij[i-1]=1ll*i*ij[i]%mod;
    for(int i=0;i<=n;i++)f[i]=1ll*ij[i+1]*(qpow(m+1,i+1)-1)%mod,g[i]=ij[i+1];
    Inv(g,h,n+1);
    init(n*2);for(int i=n+1;i<L;i++)f[i]=h[i]=0;
    NTT(f,1),NTT(h,1);
    for(int i=0;i<L;i++)f[i]=1ll*f[i]*h[i]%mod;NTT(f,0);
    for(int i=0;i<=n;i++)ms[i]=1ll*jc[i]*f[i]%mod;
    memset(f,0,sizeof(f)),memset(h,0,sizeof(h));
    for(int i=0;i<n;i++)f[i]=((i&1)?-1:1)*ij[i],
    h[i]=1ll*ij[i]*qpow(m,i)%mod*ms[n-i]%mod;
    NTT(f,1),NTT(h,1);
    for(int i=0;i<L;i++)f[i]=1ll*f[i]*h[i]%mod;NTT(f,0);
    int ans=0;
    for(int i=1;i<n;i++){
        int s=1ll*jc[i]*f[i]%mod;
        (ans+=1ll*s*min(i,n-i)%mod*C(n,i)%mod)%=mod;
    }
    printf("%d\n",(ans+mod)%mod);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

3 3

output:

36

result:

ok 1 number(s): "36"

Test #3:

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

input:

1 1

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

1 2

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

1 3

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

2 1

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

3 1

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 6ms
memory: 16656kb

input:

3719 101

output:

78994090

result:

ok 1 number(s): "78994090"

Test #9:

score: 0
Accepted
time: 6ms
memory: 17204kb

input:

2189 1022

output:

149789741

result:

ok 1 number(s): "149789741"

Test #10:

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

input:

2910 382012013

output:

926541722

result:

ok 1 number(s): "926541722"

Test #11:

score: 0
Accepted
time: 365ms
memory: 23256kb

input:

131072 3837829

output:

487765455

result:

ok 1 number(s): "487765455"

Test #12:

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

input:

183092 100000000

output:

231786691

result:

ok 1 number(s): "231786691"

Test #13:

score: 0
Accepted
time: 367ms
memory: 22632kb

input:

197291 937201572

output:

337054675

result:

ok 1 number(s): "337054675"

Test #14:

score: 0
Accepted
time: 374ms
memory: 23768kb

input:

200000 328194672

output:

420979346

result:

ok 1 number(s): "420979346"

Test #15:

score: 0
Accepted
time: 377ms
memory: 23176kb

input:

200000 1000000000

output:

961552572

result:

ok 1 number(s): "961552572"

Extra Test:

score: 0
Extra Test Passed