The field is full of frogs
查看原帖
The field is full of frogs
565450
__K2FeO4楼主2024/9/30 15:23

样例过了, 但是 WA 0pts,求调。

#include<bits/stdc++.h>
using namespace std;
const int N=2121212;
typedef long long ll;
const ll mod=998244353,g=3,gi=332748118;
int n,m,lim=1,l,rev[N],ans[N];
ll a[4][N];
char aa[N];
/*
print((a+1)*(a+2)//2*(a+3)//3*(a+4)//4)
*/
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
inline ll qpow(ll x,ll y){
	ll s=1;
	while(y){
		if(y&1)s=s*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return s;
}
void NetEase(ll c[],int type){
    for(int i=0;i<lim;i++)if(i<rev[i])swap(c[i],c[rev[i]]);
    for(int mid=1;mid<lim;mid<<=1){
        ll wn=qpow(type==1?g:gi,(mod-1)/(mid<<1));
        for(int r=mid<<1,j=0;j<lim;j+=r){
            ll w=1;
            for(int k=0;k<mid;k++,w=(w*wn)%mod){
                ll x=c[j+k],y=w*c[j+mid+k]%mod;
                c[j+k]=(x+y)%mod;
                c[j+mid+k]=(x-y+mod)%mod;
            }
        }
    }
}
int main() {
	scanf("%s",aa);
    n=strlen(aa)-1;
    for(int i=0;i<=n;i++)a[0][i]=aa[n-i]-48;
    a[0][0]++,a[1][0]=a[0][0]+1,a[2][0]=a[1][0]+1,a[3][0]=a[2][0]+1;
    while(lim<=n+m)lim<<=1,l++;
    for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    NetEase(a[0],1);
    NetEase(a[1],1);
    NetEase(a[2],1);
    NetEase(a[3],1);
    for(int i=0;i<=lim;i++)a[0][i]=(a[0][i]*a[1][i])%mod;
    for(int i=0;i<=lim;i++)a[0][i]=(a[0][i]*a[2][i])%mod;
    for(int i=0;i<=lim;i++)a[0][i]=(a[0][i]*a[3][i])%mod;
    NetEase(a[0],-1);
	ll inv=qpow(lim,mod-2);
    for(int i=0;i<=n+m;i++)
    ans[i]=a[0][i]*inv%mod;
    int k=n+m+4;
    for(int i=0;i<=k;i++)
    ans[i+1]+=ans[i]/10,ans[i]%=10;
	ll r=0;
	for(int i=k;i>=0;i--){
		ans[i]+=r*10;
		r=ans[i]%24;
		ans[i]/=24;
	}
	while(!ans[k])k--;
	for(int i=k;i>=0;i--)
	printf("%d",ans[i]);
	return 0;
}
2024/9/30 15:23
加载中...