QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#417612 | #8715. 放苹果 | grass8cow# | AC ✓ | 377ms | 23768kb | C++17 | 2.1kb | 2024-05-22 20:07:09 | 2024-05-22 20:07:10 |
Judging History
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