题解：P11998 哇，这就是 5p

Sweet_2013 · 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;
  }