题意:给你n个火柴 让你凑成a-b=c的形式,不包括前导0,问总共有多少个方案数(mod上m)。
思路:真的想不出来,太妙了,先把a-b=c变形成a=b+c,然后从低位往高位枚举每位填的数,dp状态定义成f[i][f1][f2][flow] (只剩下i根火柴,b是否填完,c是否填完,是否有进位的方案数),终止条件就是b和c都填完了,看看是否有进位。很妙,每次火柴数量减去要填的数量,a的数字可以算出来,是(flow+i+j)%10。
代码:

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=510;
int stk[10]={
   6,2,5,5,4,5,6,3,7,6};
ll f[N][2][2][2]; //将a-b=c 转化为 a=b+c ,状态含义为只剩下i根火柴 b和c是否枚举完,是否有进位
int n,m;
ll dfs(int num,bool f1,bool f2,bool flow)
{
   
	if(num<0)	return 0;
	ll &v = f[num][f1][f2][flow];
	if(~v)	return f[num][f1][f2][flow];
	if(f1 && f2)	return flow*2==num;
	ll ans=0;
	if(!f1 && f2)
	{
   
		for(int i=0;i<=9;i++)
		{
   
			int cost=stk[i] + stk[(i+flow)%10];
			ans= (ans+dfs(num-cost,f1,f2,(flow+i)/10))%m;
			if(i)
				ans= (ans + dfs(num-cost,1,f2,(flow+i)/10))%m;
		}
	}
	if(f1 && !f2)
	{
   
		for(int i=0;i<=9;i++)
		{
   
			int cost=stk[i] + stk[(i+flow)%10];
			ans=(ans + dfs(num-cost,f1,f2,(flow+i)/10))%m;
			if(i)
				ans= (ans +dfs(num-cost,f1,1,(flow+i)/10))%m;
		}
	}
	if(!f1 && !f2)
	{
   
		for(int i=0;i<=9;i++)
			for(int j=0;j<=9;j++)
			{
   
				int cost=stk[i]+stk[j]+stk[(i+j+flow)%10];
				ans = (ans + dfs(num-cost,f1,f2,(flow+i+j)/10))% m ;
				if(i)
					ans = ( ans + dfs(num-cost,1,f2,(flow+i+j)/10))%m;
				if(j)
					ans = ( ans + dfs(num-cost,f1,1,(flow+i+j)/10))%m;
				if(i&&j)
					ans = (ans + dfs(num-cost,1,1,(flow+i+j)/10)) % m;
			}
	}
	return v = ans;
}
int main()
{
   
	int cnt=0;
	int t;
	cin>>t;
	while(t--)
	{
   
		memset(f,-1,sizeof f);		
		cin>>n>>m;
		cout<<"Case #"<<++cnt<<": "<<dfs(n-3,0,0,0)<<endl;
	}
	return 0;
}