这题不难的…还是自己太菜了
看完后觉得还是很巧妙的.
a-b=c不好判断,变形为a=b+c
所以从低位到高位枚举b,c的取值进行DP
第 一 步 设 计 状 态 \color{Red}第一步设计状态 第一步设计状态
首 先 肯 定 要 保 存 当 前 剩 下 几 根 火 柴 , 还 要 处 理 当 前 是 否 有 进 位 首先肯定要保存当前剩下几根火柴,还要处理当前是否有进位 首先肯定要保存当前剩下几根火柴,还要处理当前是否有进位
然 后 . . . . . 还 要 保 存 b 和 c 是 否 枚 举 完 毕 ! ! 然后.....还要保存b和c是否枚举完毕!! 然后.....还要保存b和c是否枚举完毕!!
为 什 么 有 这 一 维 信 息 ? 因 为 如 果 枚 举 完 毕 , 选 数 字 0 的 代 价 就 是 0 了 ! ! ( 不 花 费 火 柴 ) 为什么有这一维信息?因为如果枚举完毕,选数字0的代价就是0了!!(不花费火柴) 为什么有这一维信息?因为如果枚举完毕,选数字0的代价就是0了!!(不花费火柴)
所 以 定 义 d p [ u s e ] [ f 1 ] [ f 2 ] [ f l o w ] 表 示 还 剩 u s e 根 火 柴 所以定义dp[use][f1][f2][flow]表示还剩use根火柴 所以定义dp[use][f1][f2][flow]表示还剩use根火柴
f 1 , f 2 表 示 是 否 枚 举 完 毕 , f l o w 表 示 是 否 有 进 位 f1,f2表示是否枚举完毕,flow表示是否有进位 f1,f2表示是否枚举完毕,flow表示是否有进位
然后数位DP就几行代码…是不过因为 f 1 , f 2 f1,f2 f1,f2需要分情况而已
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,mod,t;
int a[20]={6,2,5,5,4,5,6,3,7,6};
int dp[509][2][2][2];//枚举到第i位还剩j根火柴
int dfs(int use,int f1,int f2,int flow)
{
if( use<0 ) return 0;
int &now=dp[use][f1][f2][flow];
if( now!=-1 ) return now;
if( f1&&f2 ) return flow*2==use;//进位,需要2根火柴
now=0;
if( !f1&&f2 )//f2枚举完毕
{
for(int i=0;i<=9;i++)
{
int cost=a[i]+a[(i+flow)%10];
now+=dfs( use-cost,f1,f2,(i+flow)/10)%mod;
if( i ) now+=dfs( use-cost,1,f2,(i+flow)/10)%mod;//最高位不是0,那么可以结束了
}
}
else if( f1&&!f2 )
{
for(int i=0;i<=9;i++)
{
int cost=a[i]+a[(i+flow)%10];
now+=dfs( use-cost,f1,f2,(i+flow)/10)%mod;
if( i ) now+=dfs( use-cost,f1,1,(i+flow)/10)%mod;
}
}
else
{
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
{
int cost=a[i]+a[j]+a[(i+j+flow)%10];
now+=dfs( use-cost,f1,f2,(i+j+flow)/10 );
if( i ) now+=dfs( use-cost,1,f2,(i+j+flow)/10 );
if( j ) now+=dfs( use-cost,f1,1,(i+j+flow)/10 );
if( i&&j ) now+=dfs( use-cost,1,1,(i+j+flow)/10 );
}
}
return now%=mod;
}
signed main()
{
cin >> t;
int casenum=0;
while( t-- )
{
cin >> n >> mod;
memset(dp,-1,sizeof(dp));
cout << "Case #" << ++casenum << ": " << dfs(n-3,0,0,0) << endl;
}
}