思路：

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

。

因此，转移方程为：

CPP

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

的倍数的概率。

美丽的代码

CPP

#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;//白白 
}

题解：P11998 哇，这就是 5p

文章操作

思路：