对于20%的数据：答案不会很大，可以直接枚举B和C。

对于80%的数据：动态规划。
考虑F[i][j][0/1][0/1][0/1]表示用了i根火柴棒，考虑了A,B和C的最低i位。
其中A,B是否已经结束（即是否不会有更高位），以及是否需要进位分别用222的状态表示。
转移的时候枚举最高位的情况，时间复杂度O(n^2)。

对于100%的数据，考虑上述中j所在这一维不要，时间复杂度O(n)。

AC代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define mmt(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define y1 hehe
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
int c[10]={6,2,5,5,4,5,6,3,7,6};
int dp[501][2][2][2],_,n,MOD;
void Main()
{
scanf("%d%d",&n,&MOD);n-=3;
int i,e1,e2,t,a,b;
FOR(i,0,n) FOR(e1,0,1) FOR(e2,0,1) FOR(t,0,1) dp[i][e1][e2][t]=0;
dp[0][0][0][0]=1;
FOR(i,0,n) FOR(e1,0,1) FOR(e2,0,1) FOR(t,0,1)
if ( (!(e1&e2)) && (dp[i][e1][e2][t]!=0) )
{
int x=dp[i][e1][e2][t];
if (e1&&(!e2)) //A has ended
{
FOR(a,0,9)
{
int q=i+c[a]+c[(a+t)%10];
if (q>n) continue;
dp[q][1][0][(a+t)/10]=((uint)dp[q][1][0][(a+t)/10]+(uint)x)%MOD;
if (a>0) dp[q][1][1][(a+t)/10]=((uint)dp[q][1][1][(a+t)/10]+(uint)x)%MOD;
}
}
if (e2&&(!e1)) //B has ended
{
FOR(b,0,9)
{
int q=i+c[b]+c[(b+t)%10];
if (q>n) continue;
dp[q][0][1][(b+t)/10]=((uint)dp[q][0][1][(b+t)/10]+(uint)x)%MOD;
if (b>0) dp[q][1][1][(b+t)/10]=((uint)dp[q][1][1][(b+t)/10]+(uint)x)%MOD;
}
}
if ( (!e1)&&(!e2) )
{
FOR(a,0,9) FOR(b,0,9)
{
int q=i+c[a]+c[b]+c[(a+b+t)%10];
if (q>n) continue;
int t0=(a+b+t)/10;
dp[q][0][0][t0]=((uint)dp[q][0][0][t0]+(uint)x)%MOD;
if (a>0) dp[q][1][0][t0]=((uint)dp[q][1][0][t0]+(uint)x)%MOD;
if (b>0) dp[q][0][1][t0]=((uint)dp[q][0][1][t0]+(uint)x)%MOD;
if (a>0&&b>0) dp[q][1][1][t0]=((uint)dp[q][1][1][t0]+(uint)x)%MOD;
}
}
}
printf("Case #%d: %d\n",_,((uint)dp[n][1][1][0]+(uint)dp[n-2][1][1][1])%MOD);
}
int main()
{
int T;
scanf("%d",&T);
FOR(_,1,T) Main();
return 0;
}

大犇能给个具体解释吗？