NC231999. 满意的集合
描述
有数字 ，每个数字的个数分别为
。计算出“满意的集合“的个数。
"满意的集合" 定义：选出的数存在一种排列方式，其拼接起来后表示的十进制整数，能被 整除，例如集合
包含了
个数字
个数字
，可以有排列
代表十进制下的整数
，能被
整除。
两个集合相同，当且仅当集合元素个数相同，且排序后对应数字相同，例如 和
是同样的集合。
空集合看作 ，是合法的，答案对
取模。
输入描述
输入一行，包括个整数
，分别表示数字
的个数，
。
输出描述
输出一行，表示”满意的集合”的个数，答案对取模。
示例1
输入:
1 1 1 0 0 0 0 0 0
输出:
4
说明:
全部的数字集合Python3 解法, 执行用时: 29ms, 内存消耗: 4616K, 提交时间: 2022-02-09 09:42:35
P=1000000007
cnt=list(map(int,input().split()))
cnt.insert(0,0)
f=[[0 for i in range (15)] for i in range (15)]
f[0][0]=1
for i in range(1,10):
t0=(cnt[i]+3)//3
t1=(cnt[i]+2)//3
t2=(cnt[i]+1)//3
for j in range(3):
f[i][(i+j)%3]+=t1*f[i-1][j]
f[i][(2*i+j)%3]+=t2*f[i-1][j]
f[i][(3*i+j)%3]+=t0*f[i-1][j]
print(f[9][0]%P)
C++ 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2022-01-14 01:40:54
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 1000000007
int i,j,k,n,m,t;
ll f[99][99],sb;
int main() {
ios::sync_with_stdio(0);
f[0][0]=1;
for(i=1;i<=9;i++){
cin>>sb;
for(j=0;j<3;j++){
for(k=0;k<3;k++){
f[i][(j+k*i)%3]+=f[i-1][j]*(sb/3+((sb%3)>=k));
f[i][(j+k*i)%3]%=M;
}
}
}
cout<<f[9][0];
}