代码

#include<cstdio>
#include<cstring>
#define ll long long
#define mod 998244353
using namespace std;

int n, k;
ll p, f[1010][1010], g[2][1010], pw[1010], npw[1010], a[1010];

ll K(ll x,ll y=mod-2){
  ll t=1;
  for (;y;y>>=1, x=x*x%mod)
    if (y&1) t=t*x%mod;
  return t;
}

inline void U(ll &x,ll y){
  x+=y; if (x>=mod) x-=mod;
}
const ll mo2=(ll)mod*mod;
inline void U2(ll &x,ll y){
  x+=y; if (x>=mo2) x-=mo2;
}

namespace f__k{
  int n, m;

  void mul(ll *c,ll *u,ll *v){
    static ll d[2020];
    memset(d,0,sizeof d);
    for (int i=0;i<m;++i)
      for (int j=0;j<m;++j)
        U2(d[i+j],u[i]*v[j]);
    for (int i=m*2;i>=m;--i){
      d[i]%=mod;
      for (int j=1;j<=m;++j)
        U2(d[i-j],d[i]*a[j]);
      d[i]=0;
    }
    for (int i=0;i<=2*m;++i) c[i]=d[i]%mod;
  }
  
  ll gao(int n_,int m_){
    n=n_; m=m_;
    static ll b[1010], x[2020], t[2020];
    memset(b,0,sizeof b); b[0]=1;
    for (int i=1;i<=m;++i)
      for (int j=1;j<=i&&j<=m;++j)
    U(b[i],b[i-j]*a[j]%mod);
    
    //reverse(a,a+m+1); a[m]=1;
    //for (int i=0;i<m;++i) a[i]=(mod-a[i])%mod;

    memset(x,0,sizeof x); x[1]=1;
    memset(t,0,sizeof t); t[0]=1;
    for (int y=n;y;y>>=1, mul(x,x,x))
      if (y&1) mul(t,t,x);
    ll res=0;
    for (int i=0;i<m;++i)
      U(res,t[i]*b[i]%mod);
    return res;
  }
}

ll realmain(int k_){ k=k_;
  if (k<0) return 0;
  if (k==0) return K(npw[1],n);
  memset(f,0,sizeof f);
  for (int c=1;c<=k+1;++c) f[c][0]=1;
  for (int c=k;c>=1;--c){
    memset(g,0,sizeof g); g[1][0]=1;
    int m=k/c;
    for (int i=0;i<m;++i){
      U(g[1][i+1],(g[0][i]+g[1][i])*npw[1]%mod);
      for (int j=1;i+j<=m;++j)
    U(g[0][i+j],g[1][i]*f[c+1][j]%mod);
    }
    for (int i=1;i<=m;++i)
      f[c][i]=(g[0][i]+g[1][i])*pw[i]%mod;
  }
  memset(a,0,sizeof a);
  for (int i=1;i<=k+1;++i) a[i]=f[1][i-1]*npw[1]%mod;

  ll res=f__k::gao(n+1,k+1);
  return res*K(npw[1])%mod;
}

int main(){
  int k_, x, y;
  //cin>>n>>k_>>x>>y;
  scanf("%d%d%d%d",&n,&k_,&x,&y);
  p=x*K(y)%mod;
  pw[0]=npw[0]=1;
  for (int i=1;i<=k_+5;++i){
    pw[i]=pw[i-1]*p%mod;
    npw[i]=npw[i-1]*(1-p+mod)%mod;
  }
  ll ans=realmain(k_)-realmain(k_-1);
  printf("%lld\n",(ans%mod+mod)%mod);
}

评测结果