題干：

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=CA?B=C?with exactly?n?(5≤n≤500)n?(5≤n≤500)?matches (or sticks).?

In these equations,?A,BA,B?and?CC?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)m?(3≤m≤2×109).?

Input

The input contains several test cases. The first line of the input is a single integer?tt?which is the number of test cases. Then?t?(1≤t≤30)t?(1≤t≤30)?test cases follow.?

Each test case contains one line with two integers?n?(5≤n≤500)n?(5≤n≤500)?and?m?(3≤m≤2×109)m?(3≤m≤2×109).

Output

For each test case, you should output the answer modulo?mm.?

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

解題報告：

? ?一眼上來就是搜索，誰能想到是數位dp、、太難了太難了、、

首先去掉3根火柴棒來湊成減號和等號，然后問題就變成了將剩下的火柴棒拼成B+C=A的形式。然后同時對ABC這三個數的同一個數位進行dp，注意這題dp的時候不是跟一般的數位dp一樣是從高位到低位進行dp的，而是從低位像高位進行dp，因為這樣方便記錄前導零的問題。

參考題解，用dp[n][a][b][c]來表示剩余n根火柴棒時，從最低位開始的放法總數，a表示當前位是否有來自低一位的進位，b表示是否已停止放B這個數，c表示是否已停止放C這個數，則最終我們所求的結果就是dp[n-3][0][0][0]。

代碼邏輯是這樣的：

num[i]代表要湊出i這個數字需要的火柴個數。

每次檢查當前剩余多少根火柴，如果<0直接return 0，然后如果b和c都已經停止了，那么直接進入出口，當然，出口中返回0或者1要檢查是否合法：如果當前沒有來自低一位的進位（又因為B和C已經停止了），所以你當前位也肯定是啥都沒有，也就是要檢查cnt是否=0；如果有來自低一位的進位，那么當前位一定是1，也就是看cnt是否==num[1]就行了。

然后就是枚舉中間過程，注意這里只是用了數位dp的思想，所以不需要設置limit啥之類的東西，并且之類的res需要設置成longlong不然就爆int了。

然后就是分b和c這幾種情況進行討論，如果B和C都還沒確定，那么就枚舉他們分別取值是什么，然后通過B和C的取值就得到A對應位的取值（不難證明 一定是(B+C)%10，并且如果有進位，那么進位一定是1，可以通過小學學習的加法豎式簡單證明）。

枚舉好B和C之后，就有幾種選擇，可以讓B停止，可以讓C停止，也可以讓B和C都停止，分別進行討論就行了。注意B能停止的話，一定要保證i>0，同理C能停止的話，一定要保證j>0，因為不然就會出現前導零的情況使得這樣就會出現前導零的情況，所以我們要避免這種情況發生，所以我沒要特判一下i是否等于0，來進行下一步判斷就可以了，其他的情況同理，就不再說了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 555 + 5; int t,iCase,n; const int num[]= {6,2,5,5,4,5,6,3,7,6}; ll mod; ll dp[555][2][2][2]; ll dfs(int cnt,int a,int b,int c) {if(cnt<0)return 0;if(~dp[cnt][a][b][c])return dp[cnt][a][b][c];if(b&&c) {if((a&&cnt==num[1])||(!a&&!cnt))return 1;else return 0;}ll res = 0;if(!b&&!c) {for(int i=0; i<=9; ++i)for(int j=0; j<=9; ++j) {res+=dfs(cnt-(num[i]+num[j]+num[(i+j+a)%10]),(i+j+a)/10,0,0);if(i)res+=dfs(cnt-(num[i]+num[j]+num[(i+j+a)%10]),(i+j+a)/10,1,0);if(j)res+=dfs(cnt-(num[i]+num[j]+num[(i+j+a)%10]),(i+j+a)/10,0,1);if(i&&j)res+=dfs(cnt-(num[i]+num[j]+num[(i+j+a)%10]),(i+j+a)/10,1,1);}} else if(!b) {for(int i=0; i<=9; ++i) {res+=dfs(cnt-(num[i]+num[(i+a)%10]),(i+a)/10,0,1);if(i)res+=dfs(cnt-(num[i]+num[(i+a)%10]),(i+a)/10,1,1);}} else if(!c) {for(int i=0; i<=9; ++i) {res+=dfs(cnt-(num[i]+num[(i+a)%10]),(i+a)/10,1,0);if(i)res+=dfs(cnt-(num[i]+num[(i+a)%10]),(i+a)/10,1,1);}}dp[cnt][a][b][c] = res % mod;return dp[cnt][a][b][c]; } int main() {cin>>t;while(t--) {memset(dp,-1,sizeof dp);scanf("%d%lld",&n,&mod);ll ans = dfs(n-3,0,0,0)%mod;ans = (ans+mod)%mod;printf("Case #%d: %lld\n",++iCase,ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 5456】Matches Puzzle Game（数位dp，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。