题解：P11998 哇，这就是 5p

首先我们可以发现时限两秒，也就是说明

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}$ ，在代入回去就可以得到了。

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

代码部分：

CPP

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

题解：P11998 哇，这就是 5p

文章操作

相关推荐

评论

题解：P11998 哇，这就是 5p