题目描述
总共有n颗糖果，有3个小朋友分别叫做L，Y，K。每个小朋友想拿到至少k颗糖果，但这三个小朋友有一个共同的特点：对3反感。也就是说，如果某个小朋友拿到3颗，13颗，31颗，333颗这样数量的糖果，他就会不开心。（也即它拿到的糖果数量不包含有一位是3）
LYK掌管着这n颗糖果，它想问你有多少种合理的分配方案使得将这n颗糖果全部分给小朋友且没有小朋友不开心。
例如当n=3,k=1时只有1种分配方案，当n=4，k=1时有3种分配方案分别是112,121,211。当n=7,k=2时则不存在任何一种合法的方案。
当然这个答案可能会很大，你只需输出答案对12345647取模后的结果就可以了。
输入格式(candy.in)
第一行两个数表示n,k。
输出格式(candy.out)
一个数表示方案总数。
输入样例
99999 1
输出样例
9521331
对于30%的数据n<=100
对于50%的数据n<=1000。
对于另外30%的数据k=1。
对于100%的数据3<=n<=10^10000,1<=k<=n/3，且n,k不包含前导0。
分析：对于前50%的点，直接暴力枚举+判断就可以了.后50%的点数据和前50%的点数据规模完全不是一个数量级的，肯定要用不同的算法.数字肯定不能在时间复杂度里的，肯定是对数位进行处理，那么就要用到数位dp.
这道题也不是一道特别简单的数位dp,因为要3个数的和等于n,所以我们可以在每一数位的时候枚举3个数上的这一位的值，它们的和与n的第i位相差是≤2的，因为进位最多进两位。同时还有≥k这个限制，所以我们可以设状态f[i][j][kk][l][p]表示前i位，第i+1位要向第i位进j位，kk,l,p表示枚举的3个数是否>k.每次递推的时候就能知道下一个状态，就能够就行转移了.
要求方案数，数字位数又这么多，能想到的算法只有数位dp了，从数字看向数位，是一种很好的思想的转变，如果数位dp有数字大小的限制，那么通用的办法就是加一维表示是否超出限制即可.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int mod = ; char n[], k[];
int len1, len2,a[],b[],f[][][][][],ans; int main()
{
scanf("%s", n + );
len1 = strlen(n + );
scanf("%s", k + );
len2 = strlen(k + );
for (int i = ; i <= len1; i++)
a[i] = n[i] - '';
for (int i = ; i <= len2; i++)
b[i + len1 - len2] = k[i] - '';
f[][][][][] = ;
for (int i = ; i < len1; i++)
for (int j = ; j <= ; j++)
for (int k = ; k <= ; k++)
for (int l = ; l <= ; l++)
for (int p = ; p <= ; p++)
if (f[i][j][k][l][p])
for (int q = ; q <= ; q++)
if (q != )
for (int q2 = ; q2 <= ; q2++)
if (q2 != )
for (int q3 = ; q3 <= ; q3++)
if (q3 != )
{
int ni = i + , nj = j * + a[i + ] - q - q2 - q3;
int nk, nl, np;
if (nj < || nj > )
continue;
if (k == && q < b[ni])
continue;
nk = (k || q > b[ni]);
if (l == && q2 < b[ni])
continue;
nl = (l || q2 > b[ni]);
if (p == && q3 < b[ni])
continue;
np = (p || q3 > b[ni]);
f[ni][nj][nk][nl][np] += f[i][j][k][l][p];
if (f[ni][nj][nk][nl][np] >= mod)
f[ni][nj][nk][nl][np] -= mod;
}
for (int i = ; i <= ; i++) //为什么要枚举0？因为我们排除了<k的情况，0就是=k的情况
for (int j = ; j <= ; j++)
for (int k = ; k <= ; k++)
{
ans += f[len1][][i][j][k];
if (ans >= mod)
ans -= mod;
}
printf("%d\n", ans); return ;
}