2022牛客寒假训练营1-A(01背包同余)

2022牛客寒假训练营1-A(01背包同余),第1张

2022牛客寒假训练营1-A(01背包/同余) 题目思路:

首先有个结论:一个数的数字根是它对 9 9 9 取模的余数,特别的,如果余数为 0 0 0,则树根为 9 9 9。

于是问题就转化为,求这 n n n 个数不同余数的方案数,用01背包即可。

需要注意的有两点:

    因为是余数,所以根据同余的性质,直接让 a[i] 对 9 9 9 取模,缩小数据规模,方便后续转移;因为初始状态 dp[0][0] = 1 表示当前方案可行,所以要在最后计算 dp[n][0] 时减去 1 1 1。
参考代码:
#include 
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int dp[maxn][10];
int a[maxn];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 9;
    }
    dp[0][0] = 1;	//表示当前方案可行
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 8; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j < a[i]) dp[i][j] = (dp[i][j] % mod + dp[i - 1][j + 9 - a[i]] % mod) % mod;
            else dp[i][j] = (dp[i][j] % mod + dp[i - 1][j - a[i]] % mod) % mod;
        }
    }
    for (int i = 1; i <= 8; i++) {
        cout << dp[n][i] << " ";
    }
    cout << dp[n][0] - 1 << 'n';
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5713768.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存