题解：P11998 哇，这就是 5p

· · 题解

思路：

1. 动态规划：

我们需要计算所有可能的得分情况中，满足总分是 m 的倍数的概率总和。由于 m 的范围较小 (m\le1000)，可以使用动态规划来处理模 m 的余数。

2. 状态定义：

设 dp^{ij} 表示考虑前 i 道题目时，总得分模 m 等于 j 的概率。初始状态 dp_{00}=1（0 道题目时得分为 0 的概率为 1）。

3. 状态转移：

对于第 i 道题目，有两种选择：

做对：概率为 p_i，得分增加 a_i，所以新的余数为 (j+a_i)\bmod m。

做错：概率为 (1-p_i)，得分不变，余数仍为 j。

因此，转移方程为：

dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][(j-a[i])%m]*p[i]

4. 模运算处理：

由于所有运算都要在模 998244853 下进行，需要注意负数的模处理：(j-a_i)\bmod m 可能为负，需要调整为非负。

概率的乘法逆元：题目中给出的 p_i 已经是模 998244853 后的值，可以直接使用。

5. 最终结果：

考虑完所有 n 道题目后，dp_{n0} 就是总分是 m 的倍数的概率。

美丽的代码

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244853;
const int MAXM=1010;
int n,m;
int a[100010];
int p[100010];
int dp[2][1010];//使用滚动数组优化空间 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>p[i];//初始化 
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int cnt=i%2;
        int ps=1-cnt;
        memset(dp[cnt],0,sizeof(dp[cnt]));
        for (int j=0;j<m;j++)
        {
            int nj=(j+a[i])%m;
            if(nj<0)//处理负数 
                nj+=m;
            dp[cnt][nj]=(dp[cnt][nj]+1LL*dp[ps][j]*p[i]%MOD)%MOD;
            dp[cnt][j]=(dp[cnt][j]+1LL*dp[ps][j]*(1-p[i]+MOD)%MOD)%MOD;
        }
    }
    cout<<dp[n%2][0];
    return 0;//白白 
}