牛客小白月赛43_E题满意的集合

题目链接
题解链接

思路

• 十进制数字各位之和$\mathrm{\%}3=0\backslash \%3=0$, 则是一种可行的方案
• $dp[i][j]dp[i][j]$: 表示从1-i数字中选，十进制数字各位之和$\mathrm{\%}3=j\backslash \%3=j$的方案个数，则dp数组第二维只要开3即可。最后答案为dp[9][0]
• 可以看到，数字$ii$选择1个、4个、7、...个，最终的十进制数各位之和$\mathrm{\%}3\backslash \%3$的结果不变，同样，数字$ii$选择2、5、8、...个以及0、3、6、9、...个之后，十进制数字各位之和$\mathrm{\%}3\backslash \%3$的结果不变
• 现在假设dp[i-1][0]、dp[i-1][1]、dp[i-1][2]已知，数字$ii$有$cnt[i]cnt[i]$个，那么，往现有的1-(i-1)的数字集合中加入$3\ast x+13*x+1$个$ii$，可以得到一个余数，再加入$3\ast x+23*x+2$、$3\ast x+33*x+3$个$ii$，可以得到0-2这三个余数。只要计算出$cnt[i]cnt[i]$中$3\ast x+13*x+1$、入$3\ast x+23*x+2$、$3\ast x+33*x+3$的数字的个数$su{m}_1\mathrm{、}su{m}_2\mathrm{、}su{m}_{3}sum\_1、sum\_2、sum\_3$，就可以计算出从数字1-i中选的dp数组了。注意计算$cnt[i]cnt[i]$中$3\ast x+33*x+3$的个数时要包括0

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 20, mod = 1e9 + 7;
int cnt[N];
ll dp[N][3];
int main()
{
    for (int i = 1; i <= 9; i++)
    {
        cin >> cnt[i];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= 9; i++)
    {
        int mod1 = 1 * i % 3, mod2 = 2 * i % 3, mod3 = 3 * i % 3;
        int sum1 = (cnt[i] + 2) / 3, sum2 = (cnt[i] + 1) / 3, sum3 = cnt[i] / 3 + 1;
        for (int MOD = 0; MOD < 3; MOD++)
        {
            dp[i][(MOD + mod1) % 3] = dp[i][(MOD + mod1) % 3] + sum1 * dp[i - 1][MOD];
            dp[i][(MOD + mod2) % 3] = dp[i][(MOD + mod2) % 3] + sum2 * dp[i - 1][MOD];
            dp[i][(MOD + mod3) % 3] = dp[i][(MOD + mod3) % 3] + sum3 * dp[i - 1][MOD];
            dp[i][(MOD + mod1) % 3] %= mod;
            dp[i][(MOD + mod2) % 3] %= mod;
            dp[i][(MOD + mod3) % 3] %= mod;
        }
    }
    cout << dp[9][0];
    return 0;
}