实在没有思路啊~~~

1.差分，转化成至多k的概率减去至多k-1的概率。这样就不用记录“有没有出现k”这个信息了

2.n是1e9，感觉要递推然后利用数列的加速技巧

f[n]表示宽度为n的值，然后枚举最后一个连续高度至少为1的块，dp数组辅助

神仙dp：dp[i][j]表示宽度为i，j的高度出现限制，任意矩形不大于k的概率

设计确实巧妙：宽度利于转移给f，高度利于自己的转移

dp数组转移：枚举第一个到达j的限制的位置，这样，前面部分限制至少是j+1，后面至少是j，中间概率是P^(j-1)*(1-P)

　　　　并且，若i*j<=k,那么新增的就是中间的i*j的矩形，两边都满足的情况下，现在也一定满足

　　后缀和优化，限制j的范围，调和级数可以证明状态实际上只有klogk个，转移O(k)

边界：f[0]=1,dp[0][*]=1，注意，*是0~k+2

3.我们现在得到了f的递推式

先递推找到f的前几项

 

k范围限制不能矩乘

利用

可以倍增加多项式取模

k<=1000可以暴力取模

发现，模数的最高项是1，所以不用逆元！

O(k^2(logn+logk))

 

代码：

#include
     
      #define reg register int#define il inline#define numb (ch^'0')#define int long longusing namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1005;const int mod=998244353;ll a[2*N],b[2*N],f[2*N],yu[2*N],ret[2*N];ll dp[2*N][2*N];ll mi[2*N];ll n,k,x,y;ll P;ll ans;ll qm(ll x,ll y){    ll ret=1;    while(y){        if(y&1) ret=ret*x%mod;        x=x*x%mod;        y>>=1;    }    return ret;}void mul(ll *f,ll *g,ll *mo,int n){    memset(b,0,sizeof b);    for(reg i=0;i<=n;++i){        for(reg j=0;j<=n;++j){            b[i+j]=(b[i+j]+f[i]*g[j]%mod)%mod;        }    }    for(reg i=2*n;i>=n;--i){        if(b[i])            for(reg j=0;j<=n;++j) b[i+j-n]=(b[i+j-n]+mod-b[i]*mo[j]%mod)%mod;    }    for(reg i=0;i<=n;++i) f[i]=b[i],b[i]=0;    for(reg i=n+1;i<=2*n;++i) f[i]=0,b[i]=0;}ll calc(int k){    memset(dp,0,sizeof dp);    for(reg i=1;i<=k+2;++i) dp[0][i]=1;    for(reg i=1;i<=k;++i){        for(reg j=k/i+1;j>=2;--j){            for(reg l=1;l<=i;++l){                dp[i][j]=(dp[i][j]+dp[l-1][j+1]*dp[i-l][j]%mod*(1+mod-P)%mod*mi[j-1]%mod)%mod;            }            dp[i][j]=(dp[i][j+1]+dp[i][j])%mod;        }    }    for(reg i=0;i<=k;++i) a[k-i]=(mod-dp[i][2]*(1+mod-P)%mod)%mod;    a[k+1]=1;    memset(f,0,sizeof f);    f[0]=1;    for(reg l=1;l<=2*k;++l){        for(reg i=0;i<=l;++i){            if(l-i-1>=0) f[l]=(f[l]+f[l-i-1]*dp[i][2]%mod*(1+mod-P)%mod)%mod;            else f[l]=(f[l]+dp[i][2])%mod;        }    }    if(n<=2*k) return f[n];    int y=n;    memset(ret,0,sizeof ret);    memset(yu,0,sizeof yu);    ret[0]=1;    yu[1]=1;    while(y){        if(y&1) mul(ret,yu,a,k+1);        mul(yu,yu,a,k+1);        y>>=1;    }    ll bac=0;    for(reg i=0;i<=k;++i){        bac=(bac+ret[i]*f[i]%mod)%mod;    }    return bac;}int main(){    scanf("%lld%lld%lld%lld",&n,&k,&x,&y);    P=x*qm(y,mod-2)%mod;    int lp=k;    mi[0]=1;    for(reg i=1;i<=k;++i) mi[i]=mi[i-1]*P%mod;    printf("%lld\n",(calc(lp)-calc(lp-1)+mod)%mod);    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/2/25 16:31:18*/
     

总结：

1.DP还是有一点套路可循的，f是枚举最后连续的段，dp是枚举第一个限制到j的位置

2.线性递推的优化方法。