HDU 5456メモリ検索

トランスファゲート
标题:マッチをn個あげて、A-B=Cの式をいくつかつづることができます
考え方:ビットB+C=Aを変換することができて、この問題は先頭ゼロがあることを許さないで、0のこの数もだめで、私達はビットから同時にB、Cに対して捜索を行って、満たすかどうかを見ます
ステータス表示はdp[n][B][C][carry]:マッチがまだn個残っているか、Bが継続しているか、Cが継続しているか、この人が前進しているかを示す.

#include
using namespace std;
typedef long long ll;
const int N=510;
int m;
ll dp[N][2][2][2], cost[]={6,2,5,5,4,5,6,3,7,6};

inline void add(ll &x, ll y){
    x+=y; x%=m; return;
}

ll dfs(int n, bool B, bool C, bool carry){
    ll &ret=dp[n][B][C][carry];
    if(~ret) return ret;
    if(n==0){
        if(!B&&!C&&!carry)
            return ret=1;
        else
            return ret=0;
    }

    ret=0;
    if(B&&C){
        for(int i=0; i<=9; i++)
        for(int j=0; j<=9; j++){
            int sum=cost[i]+cost[j]+cost[(i+j+carry)%10];
            if(sum>n) continue;
            add(ret, dfs(n-sum, B, C, (i+j+carry)/10));
            if(i) add(ret, dfs(n-sum, 0, C, (i+j+carry)/10));
            if(j) add(ret, dfs(n-sum, B, 0, (i+j+carry)/10));
            if(i&&j)  add(ret, dfs(n-sum, 0, 0, (i+j+carry)/10));
        }
    }
    else if(B&&!C){
        for(int i=0; i<=9; i++){
            int sum=cost[i]+cost[(i+carry)%10];
            if(sum>n) continue;
            add(ret, dfs(n-sum, B, 0, (i+carry)/10));
            if(i) add(ret, dfs(n-sum, 0, 0, (i+carry)/10));
        }
    }
    else if(!B&&C){
        for(int i=0; i<=9;  i++){
            int sum=cost[i]+cost[(i+carry)%10];
            if(sum>n) continue;
            add(ret, dfs(n-sum, 0, C, (i+carry)/10));
            if(i) add(ret, dfs(n-sum, 0, 0, (i+carry)/10));
        }
    }
    else{
        if(carry)
            ret=(n==cost[1]);
        else
            ret=(n==0);
    }
    return ret%=m;
}

int main(){
    int T, n, Cas=0;

    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        n-=3;
        memset(dp, -1, sizeof dp);
        printf("Case #%d: %lld
", ++Cas, dfs(n, 1, 1, 0));
    }

    return 0;
}