题目
Source
http://acm.hdu.edu.cn/showproblem.php?pid=5456
Description
As an exciting puzzle game for kids and girlfriends, the Matches Puzzle Game asks the player to find the number of possible equations A−B=C with exactly n (5≤n≤500) matches (or sticks).
In these equations, A,B and C are positive integers. The equality sign needs two matches and the sign of subtraction needs just one. Leading zeros are not allowed.
Please answer the number, modulo a given integer m (3≤m≤2×109).
Input
The input contains several test cases. The first line of the input is a single integer t which is the number of test cases. Then t (1≤t≤30) test cases follow.
Each test case contains one line with two integers n (5≤n≤500) and m (3≤m≤2×109).
Output
For each test case, you should output the answer modulo m.
Sample Input
4
12 1000000007
17 1000000007
20 1000000007
147 1000000007
Sample Output
Case #1: 1
Case #2: 5
Case #3: 38
Case #4: 815630825
分析
题目求用N根火柴棒拼成A-B=C这种等式的方案数。
化成加法形式B+C=A,这样比较好写。
类似加法竖式的样子,从低位到高位,考虑DP:
- dp[n][0/1][0/1][0/1]表示,还剩下的火柴棒数为n,是否向下一位进位,B最高位是否已确定,C最高位是否已确定
按字面意思转移。。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long d[555][2][2][2];
int cost[10]={6,2,5,5,4,5,6,3,7,6};
int main(){
int t,n;
long long m;
scanf("%d",&t);
for(int cse=1; cse<=t; ++cse){
scanf("%d%I64d",&n,&m);
n-=3;
memset(d,0,sizeof(d));
d[n][0][0][0]=1;
for(int len=n; len>0; --len){
for(int i=0; i<=9; ++i){
for(int j=0; j<=9; ++j){
if(cost[i]+cost[j]>len) continue; int tmp0=len-cost[i]-cost[j]-cost[(i+j)%10];
int tmp1=len-cost[i]-cost[j]-cost[(i+j+1)%10]; if(tmp0>=0) d[tmp0][i+j>9][0][0]+=d[len][0][0][0],d[tmp0][i+j>9][0][0]%=m;
if(tmp1>=0) d[tmp1][i+j+1>9][0][0]+=d[len][1][0][0],d[tmp1][i+j+1>9][0][0]%=m; if(i){
if(tmp0>=0) d[tmp0][i+j>9][1][0]+=d[len][0][0][0],d[tmp0][i+j>9][1][0]%=m;
if(tmp1>=0) d[tmp1][i+j+1>9][1][0]+=d[len][1][0][0],d[tmp1][i+j+1>9][1][0]%=m;
}
if(j){
if(tmp0>=0) d[tmp0][i+j>9][0][1]+=d[len][0][0][0],d[tmp0][i+j>9][0][1]%=m;
if(tmp1>=0) d[tmp1][i+j+1>9][0][1]+=d[len][1][0][0],d[tmp1][i+j+1>9][0][1]%=m;
}
if(i&&j){
if(tmp0>=0) d[tmp0][i+j>9][1][1]+=d[len][0][0][0],d[tmp0][i+j>9][1][1]%=m;
if(tmp1>=0) d[tmp1][i+j+1>9][1][1]+=d[len][1][0][0],d[tmp1][i+j+1>9][1][1]%=m;
}
}
}
for(int i=0; i<=9; ++i){
int tmp0=len-cost[i]-cost[i];
int tmp1=len-cost[i]-cost[(i+1)%10]; if(tmp0>=0) d[tmp0][0][0][1]+=d[len][0][0][1],d[tmp0][0][0][1]%=m;
if(tmp1>=0) d[tmp1][i+1>9][0][1]+=d[len][1][0][1],d[tmp1][i+1>9][0][1]%=m; if(tmp0>=0) d[tmp0][0][1][0]+=d[len][0][1][0],d[tmp0][0][1][0]%=m;
if(tmp1>=0) d[tmp1][i+1>9][1][0]+=d[len][1][1][0],d[tmp1][i+1>9][1][0]%=m; if(i){
if(tmp0>=0) d[tmp0][0][1][1]+=d[len][0][0][1],d[tmp0][0][1][1]%=m;
if(tmp1>=0) d[tmp1][i+1>9][1][1]+=d[len][1][0][1],d[tmp1][i+1>9][1][1]%=m; if(tmp0>=0) d[tmp0][0][1][1]+=d[len][0][1][0],d[tmp0][0][1][1]%=m;
if(tmp1>=0) d[tmp1][i+1>9][1][1]+=d[len][1][1][0],d[tmp1][i+1>9][1][1]%=m;
}
}
}
long long res=(d[0][0][1][1]+d[cost[1]][1][1][1])%m;
printf("Case #%d: %I64d\n",cse,res);
}
return 0;
}