QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#427924 | #8715. 放苹果 | NaCly_Fish | AC ✓ | 208ms | 30604kb | C++14 | 3.2kb | 2024-06-01 16:29:28 | 2024-06-01 16:29:30 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 524292
#define ll long long
#define p 998244353
using namespace std;
inline int add(const int& x,const int& y){ return x+y>=p?x+y-p:x+y; }
inline int dec(const int& x,const int& y){ return x<y?x-y+p:x-y; }
inline int power(int a,int t){
int res = 1;
while(t){
if(t&1) res = (ll)res*a%p;
a = (ll)a*a%p;
t >>= 1;
}
return res;
}
int siz;
int rev[N],rt[N],inv[N],fac[N],ifac[N];
void init(int n){
int lim = 1;
while(lim<=n) lim <<= 1,++siz;
for(int i=0;i!=lim;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(siz-1));
int w = power(3,(p-1)>>siz);
fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = rt[lim>>1] = 1;
for(int i=(lim>>1)+1;i!=lim;++i) rt[i] = (ll)rt[i-1]*w%p;
for(int i=(lim>>1)-1;i;--i) rt[i] = rt[i<<1];
for(int i=2;i<=n;++i) inv[i] = (ll)(p-p/i)*inv[p%i]%p;
for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
ifac[n] = power(fac[n],p-2);
for(int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
}
inline void dft(int *f,int n){
static unsigned long long a[N];
int x,shift = siz-__builtin_ctz(n);
for(int i=0;i!=n;++i) a[rev[i]>>shift] = f[i];
for(int mid=1;mid!=n;mid<<=1)
for(int j=0;j!=n;j+=(mid<<1))
for(int k=0;k!=mid;++k){
x = a[j|k|mid]*rt[mid|k]%p;
a[j|k|mid] = a[j|k]+p-x;
a[j|k] += x;
}
for(int i=0;i!=n;++i) f[i] = a[i]%p;
}
inline void idft(int *f,int n){
reverse(f+1,f+n);
dft(f,n);
int x = p-((p-1)>>__builtin_ctz(n));
for(int i=0;i!=n;++i) f[i] = (ll)f[i]*x%p;
}
inline int getlen(int n){
return 1<<(32-__builtin_clz(n));
}
inline void inverse(const int *f,int n,int *r){
static int g[N],h[N],st[30];
memset(g,0,getlen(n<<1)<<2);
int lim = 1,top = 0;
while(n){
st[++top] = n;
n >>= 1;
}
g[0] = 1;
while(top--){
n = st[top+1];
while(lim<=(n<<1)) lim <<= 1;
memcpy(h,f,(n+1)<<2);
memset(h+n+1,0,(lim-n)<<2);
dft(g,lim),dft(h,lim);
for(int i=0;i!=lim;++i) g[i] = g[i]*(2-(ll)g[i]*h[i]%p+p)%p;
idft(g,lim);
memset(g+n+1,0,(lim-n)<<2);
}
memcpy(r,g,(n+1)<<2);
}
inline int binom(int n,int m){
if(n<m) return 0;
return (ll)fac[n]*ifac[m]%p*ifac[n-m]%p;
}
int n,m,lim;
int f[N],g[N],a[N],b[N];
int main(){
scanf("%d%d",&n,&m);
init(n<<1|1);
for(int i=0;i<=n;++i){
f[i] = (ll)binom(n,i)*min(i,n-i)%p*fac[i]%p;
g[n-i] = (i&1)?p-ifac[i]:ifac[i];
}
lim = getlen(n<<1);
dft(f,lim),dft(g,lim);
for(int i=0;i!=lim;++i) f[i] = (ll)f[i]*g[i]%p;
idft(f,lim);
for(int i=0;i<=n;++i){
b[i] = ifac[i+1];
a[i] = (ll)power(m+1,i+1)*ifac[i+1]%p;
}
inverse(b,n,b);
dft(a,lim),dft(b,lim);
for(int i=0;i!=lim;++i) a[i] = (ll)a[i]*b[i]%p;
idft(a,lim);
for(int i=0;i<=n;++i) a[i] = (ll)a[i]*fac[i]%p;
a[0]--;
int ans = 0;
for(int i=0;i<=n;++i) ans = (ans + (ll)power(m,i)*f[n+i]%p*a[n-i]%p*ifac[i])%p;
printf("%d",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22356kb
input:
2 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 22416kb
input:
3 3
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 0ms
memory: 22420kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 22376kb
input:
1 2
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 22416kb
input:
1 3
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 3ms
memory: 22420kb
input:
2 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 22232kb
input:
3 1
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 6ms
memory: 22332kb
input:
3719 101
output:
78994090
result:
ok 1 number(s): "78994090"
Test #9:
score: 0
Accepted
time: 0ms
memory: 22464kb
input:
2189 1022
output:
149789741
result:
ok 1 number(s): "149789741"
Test #10:
score: 0
Accepted
time: 3ms
memory: 22372kb
input:
2910 382012013
output:
926541722
result:
ok 1 number(s): "926541722"
Test #11:
score: 0
Accepted
time: 177ms
memory: 30468kb
input:
131072 3837829
output:
487765455
result:
ok 1 number(s): "487765455"
Test #12:
score: 0
Accepted
time: 186ms
memory: 30600kb
input:
183092 100000000
output:
231786691
result:
ok 1 number(s): "231786691"
Test #13:
score: 0
Accepted
time: 198ms
memory: 30564kb
input:
197291 937201572
output:
337054675
result:
ok 1 number(s): "337054675"
Test #14:
score: 0
Accepted
time: 208ms
memory: 30604kb
input:
200000 328194672
output:
420979346
result:
ok 1 number(s): "420979346"
Test #15:
score: 0
Accepted
time: 193ms
memory: 30492kb
input:
200000 1000000000
output:
961552572
result:
ok 1 number(s): "961552572"
Extra Test:
score: 0
Extra Test Passed