刷题 数论 组合数

2023.12.7 cf 1907E

解题思路

首先明确，如果这三个数加起来发生了进位，那么必然不是好数（一个位换下一个位总和会有损失）

然后，结果n的每一位就可以拆成几个1，或者说几个小球，用两个隔板往小球的空隙插（注意因为0也有可能，所以小球两边也可插，可插空隙个数为num+2）

然后就可以直接组合数，每一位的结果相乘就是所有可能的种数

代码

注意一下组合数的预处理部分

组合数性质：C_mⁿ=C_m-1ⁿ+C_m-1^n-1

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int c[20][20];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int i=0;i<=15;i++)//预处理 i从0开始，注意一下
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j]+c[i-1][j-1];//这个性质记一下
		}
	}
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(!n)
		{
			cout<<1<<endl;
			continue;
		}
		ll ans=1;
		while(n)
		{
			int temp=n%10;
			ans*=c[temp+2][2];
			n/=10;
		}
		cout<<ans<<endl;
	}
	return 0;
}