【题解】[NOI2017] 泳池 常系数齐次线性递推 LuoguP3824 —Qiuly

“ 恰好” 不好处理，考虑转化为” 小于等于 $k$ “ 的减去” 小于 $k$ “ 的。

定义 $dp_{i,j}$ 表示默认一个宽为 $i$ ，高为 $j$ 的矩形是一定安全的。其他格子的概率。

转移的话就是考虑：

• 从上一行推来，因为 $dp_{i,j+1}$ 默认第 $j+1$ 行全部是安全的，但是到了 $dp_{i,j}$ 就不保证了，所以转移时乘上一个概率。
• 考虑上一行被破坏的情况，枚举 $k$ 表示上一行第一个危险的格子，然后左边就是 $dp_{k-1,j+1}$ ，右边就是 $dp_{i-k,j}$ ，危险格子的概率是 $1-p$ ，然后因为不默认 $k-1$ 列的最上面一行的格子是安全的，同样的转移也要带个概率。

显而易见的如果 $i\cdot j>k$ 就么必要管这个状态了，所以有效状态其实不多。

考虑令 $F_i$ 表示前 $i$ 列的答案，转移就是从之前的某一列 $j$ 转移过来。因为矩阵大小不超过 $k$ ，所以最终的形状一定是最底下的危险格子之间的安全格子个数不超过 $k$ ，否则不满足题目要求。

对于 $F_i$ 的转移枚举上一次危险格子出现的位置 $j$ ，然后之前的概率是 $F_{j-1}$ ，危险格子的概率是 $1-p$ ，然后从 $j+1$ 到 $i$ 列一定最下面一行是安全的，状态就是 $dp_{i-j,1}$ ，同样的还要乘上一个默认格子的概率。

因为 $F_i$ 的转移只跟前 $k$ 项有关，将后面的概率乘起来后会发现是一个经典的常系数齐次线性递推，这一部分时间复杂度 $O(k\log k\log n)$ ，足已通过所有数据。

Code：

由于加上板子和 $\rm{Poly}$ 代码超过了 $200$ 行，因此只贴核心代码。

const int M=1e3+15;
int n,x,y,p,f[M],g[M],dp[M][M];

inline int solve(int K) {
    int lim=1001;
    CLEAR(dp),CLEAR(f),CLEAR(g);

    for(int i=0;i<=lim+1;++i) dp[0][i]=1;
    for(int i=1;i<=lim;++i) for(int j=lim;j>=0;--j) if(i*j<=K) {
        dp[i][j]=mul(dp[i][j+1],modpow(p,i));
        for(int k=1;k<=i;++k)
            pls(dp[i][j],mul(mul(dp[k-1][j+1],dp[i-k][j]),mul(dec(1,p),modpow(p,k-1))));
    }

    for(int i=0;i<=K;++i) f[i]=dp[i][0];
    for(int i=0;i<=K;++i) g[i+1]=mul(dp[i][1],mul(dec(1,p),modpow(p,i)));
    return calc(n,K+1,f,g); /*常系数齐次线性递推*/
}

int k;
int main() {
    #ifndef ONLINE_JUDGE
        freopen("code.in","r",stdin);
        // freopen("code.out","w",stdout);
    #endif
    Poly::init_w();

    IN(n,k,x,y),p=mul(x,modpow(y,mod-2));
    printf("%d\n",dec(solve(k),solve(k-1)));
    return 0;
}