SPOJ BALNUM Balanced Numbers （數位dp）

題意:

求[l,r]區間中數滿足,奇數數字有偶數個,偶數數字有奇數個,的個數

分析:

三進制壓縮−−sta[0→9]:=0沒有出現,1出現奇數次,2出現偶數次

把sta三進制壓縮,dp[i][s]:=i位,狀态s,(s≤310=59049)

轉移什麼的都很顯然,同樣注意前導0,1019爆LL了,開ULL

代碼:

//
//  Created by TaoSama on 2015-10-21
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include <climits>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N =  + , INF = , MOD =  + ;

typedef unsigned long long ULL;

ULL dp[][]; //3^10 = 59049
int digit[], sta[], vis[][], kase;
//0 for none, 1 for odd, 2 for even

int encode() {
    int s = ;
    for(int i = ; i < ; ++i) s = s *  + sta[i];
    return s;
}

void decode(int s) {
    for(int i = ; ~i; --i, s /= ) sta[i] = s % ;
}

void print() {
    for(int i = ; i < ; ++i) cout << sta[i] << ' '; cout << endl;
}

bool check(int s) {
    decode(s);
    for(int i = ; i < ; ++i) {
        if((i & ) && sta[i] == ) return false;
        if(!(i & ) && sta[i] == ) return false;
    }
    return true;
}

int trans(int s, int d) {
    decode(s);
    if(sta[d] == ) sta[d] = ;
    else sta[d] =  - sta[d];
    return encode();
}

ULL dfs(int i, int s, bool first, bool e) {
    if(!i) return check(s);
    if(!e && vis[i][s] == kase) return dp[i][s];
    int to = e ? digit[i] : ;
    ULL ret = ;
    for(int d = ; d <= to; ++d)
        ret += dfs(i - , first && !d ? s : trans(s, d),
                   first && !d, e && d == to);
    if(!e) vis[i][s] = kase, dp[i][s] = ret;
    return ret;
}

ULL calc(ULL x) {
    int cnt = ;
    for(; x; x /= ) digit[++cnt] = x % ;
    return dfs(cnt, , , );
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    int t; scanf("%d", &t);
    while(t--) {
        ULL l, r; scanf("%llu%llu", &l, &r);
        ++kase;
        printf("%llu\n", calc(r) - calc(l - ));
    }
    return ;
}