实在没有思路啊~~~
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<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') #define int long long using 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 ",(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.线性递推的优化方法。