QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427924#8715. 放苹果NaCly_FishAC ✓208ms30604kbC++143.2kb2024-06-01 16:29:282024-06-01 16:29:30

Judging History

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

  • [2024-06-01 16:29:30]
  • 评测
  • 测评结果:AC
  • 用时:208ms
  • 内存:30604kb
  • [2024-06-01 16:29:28]
  • 提交

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,我给组数据试试?

詳細信息

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