题解：P11998 哇，这就是 5p

D_chzhh_L · 2025-04-04 22:41:23 · 题解

首先我们可以发现时限两秒，也就是说明 O(nm) 可以通过去，这就为我们实现动态规划这个算法奠定了基础 当然应该有比这个时间复杂度更快的做法。

我们不妨设计一个状态 dp_{i,j}，用来表示做到第 i 道题时，此时的分数除以 m 的余数为 j 的概率为多少。

那此时此刻对于第 i 道题有两种选择：

• 假如这题做对了，那 dp_{i,j} 需要加上 dp_{i-1,(j-a_{i}+m) \mod m} \times p_{i} \mod mod。

• 假如这题没做对，那 dp_{i,j} 需要加上 dp_{i-1,j} \times (1-p_{i}+mod) \mod mod。

所以动态转移方程就是 dp_{i,j} = (dp_{i-1,(j-a_{i}+m) \mod m} \times p_{i} + dp_{i-1,j} \times (1-p_{i}+mod) \mod mod) \mod mod，mod 为 998244853。

注：(1-p_{i}+mod) \mod mod 用来表示 1-p_{i} \mod mod 的结果，就是没做对的概率。以下为推理过程：

• 题目已经说了 p_{i} 一定能够被表示成 \frac{a}{b} 的形式，且 b < 998244853，再根据题目说的有理数取余，则 \frac{a}{b} = a \times b^{mod-2}。现令 mod-2 为 A，则 1-p_{i} 可表示为 \frac{b-a}{b}，所以 1-p_{i} \mod mod 的结果为 b^{A+1} - a \times b^A，根据 费马小定理，b^{A+1} 在模 mod 的情况下就为 1，而 a \times b^A 在模 mod 的情况下就为 p_{i}，在代入回去就可以得到了。

但是这样子数组的空间可能会爆掉，但我们可以发现一个状态的转移只会依赖上一个状态的结果，所以我们就可以用滚动数组来优化。

代码部分：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1,mod=998244853;
int n,m,a[N],p[N],tot,dp[2][1001];
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]%=m;
    for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int tott=tot^1;
        memset(dp[tott],0,sizeof(dp[tott]));
        for(int j=0;j<m;j++)
        {
            dp[tott][j]+=dp[tot][j]*((1-p[i]+mod)%mod)%mod,dp[tott][j]%=mod;
            dp[tott][j]+=dp[tot][(j-a[i]+m)%m]*p[i]%mod,dp[tott][j]%=mod;
        }
        tot=tott;
    }
    printf("%lld",dp[tot][0]);
    return 0;
}