题解 | #满意的集合#

Problem

Solution

数字1-9分别由cnt1、cnt2、cnt3...cnt9个，集合是由数字1~9的和组成的数字集合，满意的集合为数字集合的子集，且该自己的元素拼接起来能被3整除。
可以用动态规划来做这道题。
分析情况有两种：能被三整除和不能被三整除。
发现还可以细分为三种情况：对3取余为0、1、2.
则状态机为三种 分别为0 1 2;
其中：
f[i][0]表示由前i个数字组成的集合里，余数为0的集合个数
f[i][1]表示由前i个数字组成的集合里，余数为1的集合个数
f[i][2]表示由前i个数字组成的集合里，余数为2的集合个数
分析可得：

		int sum1, sum2, sum3;  // 由i组成的余数为1、2、0的个数
		f[i][0] = f[i - 1][0] * (sum3 + 1) + f[i - 1][1] * sum2 + f[i - 1][2] * sum1;
        f[i][1] = f[i - 1][1] + f[i - 1][0] * sum1 + f[i - 1][1] * sum3 + f[i - 1][2] * sum2;
        f[i][2] = f[i - 1][2] + f[i - 1][2] * sum3 + f[i - 1][1] * sum1 + f[i - 1][0] * sum2;
        

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 11, mod = 1e9 + 7;

ll f[N][3];
ll cnt[N];
int n = 9;

int main()
{
    for (int i = 1; i <= n; i++)
        cin >> cnt[i];
    
    for (int i = 0; i <= n; i++)
        f[i][0] = 1;
    
    for (int i = 1; i <= 9; i++)
    {
        int sum1, sum2, sum3;  // 由i组成的余数为1、2、0的个数
        if (i % 3 == 1)
        {
            sum1 = (cnt[i] + 2) / 3;
            sum2 = (cnt[i] + 1) / 3;
            sum3 = cnt[i] / 3;
        }
        else if (i % 3 == 2)
        {
            sum1 = (cnt[i] + 1) / 3;
            sum2 = (cnt[i] + 2) / 3;
            sum3 = cnt[i] / 3;
        }
        else sum1 = 0, sum2 = 0, sum3 = cnt[i];
        f[i][0] = f[i - 1][0] * (sum3 + 1) + f[i - 1][1] * sum2 + f[i - 1][2] * sum1;
        f[i][1] = f[i - 1][1] + f[i - 1][0] * sum1 + f[i - 1][1] * sum3 + f[i - 1][2] * sum2;
        f[i][2] = f[i - 1][2] + f[i - 1][2] * sum3 + f[i - 1][1] * sum1 + f[i - 1][0] * sum2;
        f[i][0] %= mod;
        f[i][1] %= mod;
        f[i][2] %= mod;
    } 
    
    cout << f[n][0] << endl;
    return 0;
}