题意:https://vijos.org/p/1967

火柴棒等式好难啊..

所以..

我们考虑dp(i,j,k,l)表示:

用了i个火柴棒,第一个数是否用到头了;第二个数是否用到头了;是否有进位

显然,dp(n,1,1,0)是答案(两个数都到头,并且没有进位)

然后转移的话....

就这么转移就是..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int modo;
long long dp[605][2][2][2];
int num[15]={6,2,5,5,4,5,6,3,7,6};
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        printf("Case #%d: ",zu+1);
        int i;
        int n;
        scanf("%d%d",&n,&modo);
        memset(dp,0,sizeof(dp));
        dp[0][0][0][0]=1;
        n-=3;   // - and =
        for (i=0;i<=n;i++)
        {
            dp[i][0][0][0]%=modo;
            dp[i][0][0][1]%=modo;
            dp[i][0][1][0]%=modo;
            dp[i][0][1][1]%=modo;
            dp[i][1][0][0]%=modo;
            dp[i][1][0][1]%=modo;
            dp[i][1][1][0]%=modo;
            dp[i][1][1][1]%=modo;
            int j,k;
            for (j=0;j<10;j++)
            {
                for (k=0;k<10;k++)
                {
                    dp[i+num[j]+num[k]+num[(j+k)%10]][0][0][(j+k)/10]+=dp[i][0][0][0];
                    dp[i+num[j]+num[k]+num[(j+k+1)%10]][0][0][(j+k+1)/10]+=dp[i][0][0][1];
                    if (j==0)
                    {
                        dp[i+num[k]+num[k]][1][0][0]+=dp[i][1][0][0];
                        dp[i+num[k]+num[(k+1)%10]][1][0][(k+1)/10]+=dp[i][1][0][1];
                        if (k!=0)
                        {
                            dp[i+num[k]+num[k]][1][1][0]+=dp[i][1][0][0];
                            dp[i+num[k]+num[(k+1)%10]][1][1][(k+1)/10]+=dp[i][1][0][1];
                        }
                    }
                    else
                    {
                        dp[i+num[j]+num[k]+num[(j+k)%10]][1][0][(j+k)/10]+=dp[i][0][0][0];
                        dp[i+num[j]+num[k]+num[(j+k+1)%10]][1][0][(j+k+1)/10]+=dp[i][0][0][1];
                    }
                    if (k==0)
                    {
                        dp[i+num[j]+num[j]][0][1][0]+=dp[i][0][1][0];
                        dp[i+num[j]+num[(j+1)%10]][0][1][(j+1)/10]+=dp[i][0][1][1];
                        if (j!=0)
                        {
                            dp[i+num[j]+num[j]][1][1][0]+=dp[i][0][1][0];
                            dp[i+num[j]+num[(j+1)%10]][1][1][(j+1)/10]+=dp[i][0][1][1];
                        }
                    }
                    else
                    {
                        dp[i+num[j]+num[k]+num[(j+k)%10]][0][1][(j+k)/10]+=dp[i][0][0][0];
                        dp[i+num[j]+num[k]+num[(j+k+1)%10]][0][1][(j+k+1)/10]+=dp[i][0][0][1];
                    }
                    if ((j!=0)&&(k!=0))
                    {
                        dp[i+num[j]+num[k]+num[(j+k)%10]][1][1][(j+k)/10]+=dp[i][0][0][0];
                        dp[i+num[j]+num[k]+num[(j+k+1)%10]][1][1][(j+k+1)/10]+=dp[i][0][0][1];
                    }
                    if ((j==0)&&(k==0))
                    {
                        dp[i+num[1]][1][1][0]+=dp[i][1][1][1];
                    }
                }
            }
        }
        cout<<dp[n][1][1][0]<<endl;
    }
    return 0;
}