牛客练习赛93

发布于 2021-12-11  256 次阅读


B题

题意

一共有m种牌,第i种牌的价值为a_i。打n张牌,获得的价值是每次加上a_i再模k,求最后价值中含有7或9的方案数量。

思路

是一个很经典很基础的dp,很容易想到用dp[i][j]表示打到第 i 张牌价值为 j 的方案数量。然而状态转移的时候出了问题。

赛中我的做法是考虑同余模定理,最后的结果加一起模k和每一步模k是一样的,所以状态转移时不考虑取模,只考虑真实的价值。然后就wa死了。

其实在转移的时候就需要考虑取模。假如不取模,就会转移到真实的价值上,但实际上被取模的价值可能从很多情况转移过来,而这会导致后面转移计算的结果出问题。

这题确实在一定程度上提示了我如何在状态转移的时候取模,同时也可以使用滚动数组的方式压掉一维。

这题的dp思想更接近于用状态转移去翻译题意。

代码

/***********************************
// @Author   :   amcones
// @Problem  :   a.cpp
// @When     :   2021-12-11 10:21:42
***********************************/
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int n, m, k;
int a[51];
int dp[2][51];
int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++)
            dp[i & 1][j] = 0;
        for (int j = 0; j < k; j++)
            for (int l = 1; l <= m; l++)
                (dp[i & 1][(j + a[l]) % k] += dp[(i & 1) ^ 1][j]) %= mod;
    }
    int ans = 0;
    for (int i = 1; i < k; i++) {
        if (i % 10 == 7 || i % 10 == 9)
            (ans += dp[n & 1][i]) %= mod;
    }
    cout << ans << endl;
    return 0;
}

盛夏日落迟 灯火未夜匆匆明