满意的集合

https://ac.nowcoder.com/acm/contest/11220/E

题意：

有数字 1∼∼9，每个数字的个数分别为 cnt1,cnt2,cnt3,...,cnt9。计算出“满意的集合“的个数。

"满意的集合" 定义：选出的数存在一种排列方式，其拼接起来后表示的十进制整数，能被 3整除，例如集合 {3,3,6} (包含了 2 个数字 3,1 个数字 6 )，可以有排列 {6,3,3} 代表十进制下的整数 633，能被 3 整除。链

两个集合相同，当且仅当集合元素个数相同，且排序后对应数字相同，例如 {3,3,6}和 {3,6,3}是同样的集合。 空集合看作 0 ，是合法的，答案对 1e9+7取模。

思路：

一个十进制数每一位累加是 3 的倍数，那么这个数必然会被 3整除

暴力做法
for (int i=1; i<=9; i++) {
    for (int j=0; j<=cnt[i]; j++) {
        for (int MOD=0; MOD<3; MOD++) {
            dp[i][(j*i+MOD)%3]+=dp[i-1][MOD];
            dp[i][(j*i+MOD)%3]%=mod;
        }
    }
}
由于数据高达 1e9不可行

仔细观察发现，对于一个数 i ，选了 1,4,7,..,3∗x+1个的时候，得到的关于 3 的模数都是相等的，

即1∗i % 3=4∗i % 3=7∗i % 3=...=(3∗x+1)∗i % 3

同理

2∗i % 3=5∗i % 3=8∗i % 3=...=(3∗x+2)∗i % 3

0∗i % 3=3∗i % 3=6∗i % 3=...=(3∗x)∗i % 3

因此只有 3 个可能的模数，复杂度可以优化成 O (9∗3∗3)。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+10;
const int mod=1e9+7;
int a[20];
int dp[10][5];//表示只选择数字 1-i ，累加和 % 3 =j 的方案有多少
/*
for (int i=1; i<=9; i++) {
    for (int j=0; j<=cnt[i]; j++) {
        for (int MOD=0; MOD<3; MOD++) {
            dp[i][(j*i+MOD)%3]+=dp[i-1][MOD];
            dp[i][(j*i+MOD)%3]%=mod;
        }
    }
}
暴力做法


*/
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=9;i++){
        cin>>a[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=9;i++){
        int a1=i%3,a2=i*2%3,a3=i*3%3;
        int b1=(a[i]+2)/3,b2=(a[i]+1)/3,b3=a[i]/3+1;
        for(int k=0;k<3;k++){
            dp[i][(a1+k)%3]+=b1*dp[i-1][k];
            dp[i][(a1+k)%3]%=mod;
            dp[i][(a2+k)%3]+=b2*dp[i-1][k];
            dp[i][(a2+k)%3]%=mod;
            dp[i][(a3+k)%3]+=b3*dp[i-1][k];
            dp[i][(a3+k)%3]%=mod;
        }
    }
    cout<<dp[9][0]<<endl;
	system("pause");

}
/*
一个十进制数每一位累加是 3 的倍数，那么这个数必然会被 3整除。

*/