2 条题解
-
8
思路
这就是一个类似于01背包的问题。对于每头牛都有取和不取两种选择。 用h[i][j]表示在前$i$头牛中选择，所选数之和$mod F$结果为$j$的方案数。 $\\$（1）若不取$i$，则应在前$i−1$头牛中取来若干和为$j$的数，方案数即为$h[i−1][j]$。 $\\$（2）若取$i$，则应在前$i−1$头牛中取来若干和为$j−r[i]$的数，这样加上$r[i]$后，和才能等于$j$，即$h[i−1][j−r[i]]$。 $\\$所以$h[i][j]=h[i][j]+h[i−1][j]+h[i−1][j−r[i]]$。 $\\$这里还有一个关于取模的问题要解决。我们要用到的只是$r[i] mod F$的余数，所以输入时就先将$r[i]$对$F$取模。 $\\$还有就是$j−r[i]$可能为负数，这时就得写成$(j-r[i]+F)%F$，就为正了。 初始化$h[i][r[i]]$为$1$。代码
#include<iostream> using namespace std; int n,F; int f[2003][2003],r[2003]; const int mod=1e8; int main() { cin>>n>>F; for(int i=1;i<=n;i++) { cin>>r[i]; r[i]%=F; } for(int i=1;i<=n;i++) { f[i][r[i]]=1; } for(int i=1;i<=n;i++) for(int j=0;j<F;j++) f[i][j]=((f[i][j]+f[i-1][j])%mod+f[i-1][(j-r[i]+F)%F])%mod; cout<<f[n][0]; return 0; } -
6
hetao1394742
LV 10
@ 2024-3-16 13:33:19
P1102题解
思路
- 首先输入，不再赘述
- 创建一个二维数组 dp，其中 dp[i][j] 表示选取前 i 只奶牛，总能力模 F 的余数为 j 的队伍组合数。
- 初始化 dp[0][0] 为 1，表示前 0 只奶牛，总能力为 0 的队伍组合数为 1。
- 对于每一头奶牛，遍历每种可能的总能力模 F 的余数 j，并更新 dp[i+1][(j + cow[i]) % F] 和 dp[i+1][j]。
- 如果选择第 i+1 头奶牛，则更新 dp[i+1][(j + cow[i]) % F] += dp[i][j]。
- 如果不选择第 i+1 头奶牛，则更新 dp[i+1][j] += dp[i][j]。
- 最后，输出符合要求的队伍组合数对10的八次方取模的值，即 dp[N][0] - 1 的结果（减去只选择一只奶牛的情况）。
AC代码
#include <iostream> #include <vector> using namespace std; const int MOD = 1e8; // 对10的八次方取模的值 int main() { int N, F; cin >> N >> F; vector<int> cow(N); for (int i = 0; i < N; i++) { cin >> cow[i]; } // 定义一个二维数组 dp，dp[i][j] 表示选取前 i 只奶牛，总能力模 F 的余数为 j 的队伍组合数 vector<vector<int>> dp(N + 1, vector<int>(F, 0)); dp[0][0] = 1; // 前 0 只奶牛，总能力为 0 的队伍组合数为 1 for (int i = 0; i < N; i++) { for (int j = 0; j < F; j++) { dp[i + 1][(j + cow[i]) % F] += dp[i][j]; // 选取第 i+1 只奶牛 dp[i + 1][(j + cow[i]) % F] %= MOD; dp[i + 1][j] += dp[i][j]; // 不选第 i+1 只奶牛 dp[i + 1][j] %= MOD; } } cout << (dp[N][0] - 1 + MOD) % MOD << endl; // 减去只选择一只奶牛的情况 return 0; }AC证明
yiyun
LV 3
MOD
@ 2023-8-3 16:16:56
- 1