自动搬运

查看原文

来自洛谷，原作者为

	Sweet_2013 今夕是何年？ | 234粉爆我妹的照片，求关 | 互关条件 /training/813543

搬运于2025-08-24 23:11:58，当前版本为作者最后更新于2025-04-27 11:23:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

这是一道简单的 dp。

• 需要定义动态规划的数组 $dp1$ 和 $dp2$，$dp1$ 表示当前状态，$dp2$ 表示下一个状态。
• 对每个 $a_i$ 作取模处理，防止这个 $a_i$ 大于 $m$。
• 计算答案。
  • 每次循环，把 $dp2$ 里的元素初始化为 $0$，这很重要！
  • 如果当前余数 $j$ 的概率为 $0$，跳过这次循环。
  • 选择当前题目 $i$，更新新余数 $(j+a_i)\bmod m$ 的概率。
  • 接着不选择当前题目，保持余数的概率。
  • 将 $dp2$ 的值赋给 $dp1$，开始下一个循环。
• 输出 $dp1_0$，毕竟你的答案已经全在 $dp1$ 里面了嘛！

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244853;
int n, m, a[100005], p[100005], dp1[1005], dp2[1005];//dp1：当前状态。dp2：下一状态。
int main() {
    cin>> n>> m;
    for(int i=0;i<n;i++) {
        cin>> a[i];
        a[i]%=m;//为了让 a[i] 的每一个值都在 0 到 m-1 之间。
        if(a[i]<0) a[i]+=m;
    }
    for(int i=0;i<n;i++) cin>> p[i];
    dp1[0]=1;//示处理0个题目时，分数模 m 为 0 的概率是 1。
    for(int i=0;i<n;i++) {
        memset(dp2, 0, sizeof(dp2));
        for (int j=0;j<m;j++) {
            if (dp1[j]==0) continue;//若当前余数的概率为 0，跳过。
            dp2[(j+a[i])%m]=(dp2[(j+a[i])%m]+1LL*dp1[j]*p[i])%mod;//选择当前题目赋一次值。
            dp2[j]=(dp2[j]+1LL*dp1[j]*(1-p[i]+mod))%mod;//不选择再赋一次。
        }
        memcpy(dp1, dp2, sizeof(dp1));//把 dp2 所有元素的值传给 dp1，为的是处理下一个循环
    }
    cout<<dp1[0];//输出这个表示分数模 m 为 0 的概率。
    return 0;
}