Hdu 5456 Matches Puzzle Game (记忆化搜索) 2015 ACM-ICPC沈阳网赛

Matches Puzzle Game

Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others) Total Submission(s): 310    Accepted Submission(s): 210 Problem 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   Source 2015 ACM/ICPC Asia Regional Shenyang Online

     题意：给n根火柴，用火柴来拼数字，每个数字需要不同的火柴。 问，最多能产生多少个样子为“a - b = c”的式子，其中a、b、c均为正数 

    分析：每个数字都从低位到高位，枚举每一位上的数字，在搜索时递归结束的标志是每一位都不能再添加一位，并且分两种情况：第一，没有火柴，也没有进位；第二，有进位，也恰好剩2个火柴。其他情况都是不合法的情况，所有用dp[n][p][b][c]表示，当前剩余n个火柴，p是否有进位，b数字B是否为最高位，c数字C是否为最高位.按位转移，转移时要记得全部考虑b或c是否为最高位的情况和模M。

#include<iostream> #include<cstdio> #include<sstream> #include<cmath> #include<cstring> #include<string> #include<vector> #include<queue> #include<algorithm> #define INF 1<<27 #define eps 1e-9 #define LD long double #define LL long long #define ULL unsigned long long #define CL(x,v); memset(x,v,sizeof(x)); const int maxn = 500+10; using namespace std; int n,m; LL dp[maxn][2][2][2]; int need[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; LL dfs(int n, int p, int b, int c) { if (n < 0) return 0;//需要的火柴超过给定的火柴数，不符合条件，直接返回0 LL &ans = dp[n][p][b][c]; if (ans != -1) return ans; if (((!n&&!p) || n == need[1] && p) && b&&c) return ans=1; if (n == 0) return 0;//有进位 但没有火柴的情况 返回0 ans = 0; if (!b&&!c) { for (int i = 0; i < 10;i++) for (int j = 0; j < 10; j++) { int x = (i + j + p) / 10, y = (i + j + p) % 10; ans += dfs(n - need[i] - need[j] - need[y], x, 0, 0); if (i) ans += dfs(n - need[i] - need[j] - need[y], x, 1, 0); if (j) ans += dfs(n - need[i] - need[j] - need[y], x, 0, 1); if (i&&j) ans += dfs(n - need[i] - need[j] - need[y], x, 1, 1); ans %= m; } } else if (!b) { for (int i = 0; i < 10; i++) { int x = (i + p) / 10, y = (i + p) % 10; ans += dfs(n - need[i] - need[y], x, 0, 1); if (i) ans += dfs(n - need[i] - need[y], x, 1, 1); ans %= m; } } else if (!c) { for (int j = 0; j < 10; j++) { { int x = (j + p) / 10, y = (j + p) % 10; ans += dfs(n - need[j] - need[y], x, 1, 0); if (j) ans += dfs(n - need[j] - need[y], x, 1, 1); ans %= m; } } } return ans%m; } int main() { #ifdef LOCAL freopen("data.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d%d", &n, &m); CL(dp, -1); printf("Case #%d: %lld\n", kase, dfs(n - 3, 0, 0, 0)); } return 0; }