主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P11998 哇,这就是 5p
最后更新于 2025-07-31 14:07:31
作者
Sweet_2013
分类
题解
题解
P11998
复制 Markdown
查看原文
删除文章
更新内容
# 思路 这是一道简单的 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$ 里面了嘛! # 代码 ```cpp #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; } ```
正在渲染内容...
点赞
11
收藏
0