问用n根火柴棍来组成等式A-B=C有多少种方案,其中减号占一个,等号占两个,所有数为正数且不含前导零,结果模以m?
我的做法是减去必要的三根之后,转化成A=B+C来做,枚举B,C的数位的话,A的数位是确定的,枚举数位的时候有两种情况:
1:B增加一个数位i,C增加一个数位j
2:B增加一个数位i,C停止增加,或者C增加B停止
对应两种情况,可以分别设dp1[num][is][f1][f2]表示还剩num根火柴,is表示前一位是否有进位,f1,f2,分别表示B,C是否有前导零。
dp2[num][is][f]表示剩num个,是否进位is,以及前导零标志f。
然后一位一位递推就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
#include<vector>
#include<list>
#include<bitset>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3fb
int cnt[10]={6,2,5,5,4,5,6,3,7,6};
int n,m;
ll dp[2][505][2][2][2];
ll dp2[2][505][2][2];
ll dfs2(int pis,int num,int is,int f)
{
if(num==0&&!is) return !f;
else if(is&&num==cnt[is]) return !f;
if(dp2[pis][num][is][f]!=-1) return dp2[pis][num][is][f];
ll ret=0;
for(int i=0;i<=9;i++)
{
int r=cnt[i]+cnt[(i+is)%10];
if(num>=r) ret+=dfs2(1,num-r,(i+is)/10,i==0),ret%=m;
}
return dp2[pis][num][is][f]=ret;
}
ll dfs(int pis,int num,int is,int f1,int f2)
{
if(num==0&&!is) return (!f1&&!f2);
else if(is&&num==cnt[is]) return (!f1&&!f2);
if(dp[pis][num][is][f1][f2]!=-1) return dp[pis][num][is][f1][f2];
ll ret=0;
if(!f1&&pis)
{
ret+=dfs2(1,num,is,f2);ret%=m;
}
if(!f2&&pis)
{
ret+=dfs2(1,num,is,f1);ret%=m;
}
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
{
int r=cnt[i]+cnt[j]+cnt[(i+j+is)%10];
if(num>=r) ret+=dfs(1,num-r,(i+j+is)/10,i==0,j==0),ret%=m;
}
return dp[pis][num][is][f1][f2]=ret;
}
int main()
{
int t,tt=0;
scanf("%d",&t);
while(t--)
{
memset(dp,-1,sizeof dp);
memset(dp2,-1,sizeof dp2);
scanf("%d%d",&n,&m);
int ans=dfs(0,n-3,0,0,0);
printf("Case #%d: %d\n",++tt,ans);
}
return 0;
}