P4882 lty loves 96！
题目背景
众所周知，(lty)非常喜欢(96)这两个数字（想歪的现在马上面壁去），更甚于复读（人本复）！
题目描述
由于爱屋及乌，因此，(lty)对于那些含有(96)的数也非常喜欢，而这里的含有不是一般的含有，而是具有以下性质的含有（三条都需要满足）：
这个数为一个(N)位数，且没有前置零
这个数中至少要出现(M)次(9)和(6)（例：(986996)中出现了(5)次，(9)出现了(3)次，(6)出现了(2)次，共计(5)次）
这个数存在任意连续的从高到低三位(A,B,C)，满足下面任意一条
(A+B+C)为(9)或(6)
((A^2+B^2)\%C)为(9)或(6)，如果(C)为(0)，则该条件视为不满足
输入输出格式
输入格式：
一行，两个数(N),(M)
输出格式：
一个数，表示这样的数的个数
说明
对于10%的数据，(N<=6)
对于40%的数据，(N<=18)
对于100%的数据，(N<=50,0<=M<=N)
人生第一道数位DP
(dp_{i,j,k,l,q})从高到低前(i)位第(i)位为(j)，第(i-1)位为(k),一共有(l)个(6)或(9)，是否已经满足条件的方案数
注意前导0，注意要压位高精。
Code:
#include <cstdio>
#include <cstring>
int max(int x,int y){return x>y?x:y;}
struct node
{
int num[20];
node()
{
memset(num,0,sizeof(num));
num[0]=1;
}
node(int i)
{
memset(num,0,sizeof(num));
num[0]=1,num[1]=i;
}
node friend operator +(node n1,node n2)
{
int len=max(n1.num[0],n2.num[0]);
node n3;
n3.num[0]=len;
for(int i=1;i<=len;i++)
{
n3.num[i]+=n1.num[i]+n2.num[i];
n3.num[i+1]=n3.num[i]/10000;
n3.num[i]%=10000;
}
if(n3.num[len+1]) ++n3.num[0];
return n3;
}
}dp[51][10][10][51][2];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=9;i++)
for(int j=1;j<=9;j++)
{
if((i==6||i==9)&&(j==6||j==9))
dp[2][i][j][2][0]=node(1);
else if(i==6||i==9)
dp[2][i][j][1][0]=node(1);
else if(j==6||j==9)
dp[2][i][j][1][0]=node(1);
else
dp[2][i][j][0][0]=node(1);
}
for(int i=3;i<=n;i++)
for(int l3=0;l3<=9;l3++)
for(int l2=0;l2<=9;l2++)
for(int l1=0;l1<=9;l1++)
{
int s1=l1+l2+l3,s2=l1?(l3*l3+l2*l2)%l1:0;
for(int j=0;j<=i;j++)
{
if(s1==6||s1==9||s2==6||s2==9)
{
if(l1==6||l1==9)
{
if(!j) continue;
dp[i][l1][l2][j][1]=dp[i][l1][l2][j][1]
+dp[i-1][l2][l3][j-1][1]
+dp[i-1][l2][l3][j-1][0];
}
else
{
dp[i][l1][l2][j][1]=dp[i][l1][l2][j][1]
+dp[i-1][l2][l3][j][1]
+dp[i-1][l2][l3][j][0];
}
}
else
{
if(l1==6||l1==9)
{
if(!j) continue;
dp[i][l1][l2][j][0]=dp[i][l1][l2][j][0]
+dp[i-1][l2][l3][j-1][0];
dp[i][l1][l2][j][1]=dp[i][l1][l2][j][1]
+dp[i-1][l2][l3][j-1][1];
}
else
{
dp[i][l1][l2][j][0]=dp[i][l1][l2][j][0]
+dp[i-1][l2][l3][j][0];
dp[i][l1][l2][j][1]=dp[i][l1][l2][j][1]
+dp[i-1][l2][l3][j][1];
}
}
}
}
node ans=node(0);
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
for(int l=m;l<=n;l++)
ans=ans+dp[n][i][j][l][1];
printf("%d",ans.num[ans.num[0]]);
for(int i=ans.num[0]-1;i;i--)
{
if(ans.num[i]<1000) printf("0");
if(ans.num[i]<100) printf("0");
if(ans.num[i]<10) printf("0");
printf("%d",ans.num[i]);
}
return 0;
}
2018.9.9