[數位DP] hihoCoder#1033 交錯和

hihoCoder#1033

描述

給定一個數 x，設它十進制展從高位到低位上的數位依次是 a0, a1, ..., an - 1，定義交錯和函數：

f(x) = a0 - a1 + a2 - ... + ( - 1)n - 1an - 1

例如：

f(3214567) = 3 - 2 + 1 - 4 + 5 - 6 + 7 = 4

給定 

輸入

輸入資料僅一行包含三個整數，l, r, k(0 ≤ l ≤ r ≤ 1018, |k| ≤ 100)。

輸出

輸出一行一個整數表示結果，考慮到答案可能很大，輸出結果模 109 + 7。

解法

數位DP。 DP[i][j][k] 表示目前處理到i位，目前交錯和為j-100，k表示下一個符号是正還是負。所有交錯和+100是為了避免負數爆數組。依然使用模闆進行記憶化搜尋。 因為是求和，是以把DP開成結構體了，以前都是求個數，現在求和也不難。 知道目前的pos位置，也知道目前位置放的哪個數，有多少個數含有這個數，利用同餘關系就可以求和了。

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const ll mod = 1e9+7;
ll a, b, K;
ll fac[25];
int num[25];
struct node{
    ll n, sum;
    node(){ n = sum = 0; }
}dp[25][800][2][2];
bool cg(int x){
    return x > 0;
}
node dfs(int pos, int k, int flag, int zr, int f){ // k為目前交錯和 flag為正負号 zr控制前導0,這題需要考慮前導零
    if(pos < 1){
        node tmp;
        if(k == 100) tmp.n = 1;
        return tmp;
    }
    if(!f && dp[pos][k][cg(flag)][zr].sum != -1) return dp[pos][k][cg(flag)][zr];
    node res, tmp;
    int end = f? num[pos] : 9;
    for(int i = 0; i <= end; ++i){
        if(i == 0){
            if(zr) tmp = dfs(pos-1, k, flag, zr, f && i == end);
            else tmp = dfs(pos-1, k, -flag, zr, f && i == end);
        }
        else tmp = dfs(pos-1, k+flag*i, -flag, 0, f && i == end);
        res.n += tmp.n;
        res.sum += tmp.sum + fac[pos]*i*tmp.n;
        if(res.n >= mod) res.n %= mod;
        if(res.sum >= mod) res.sum %= mod;
    }
    if(!f) dp[pos][k][cg(flag)][zr] = res;
    return res;
}
ll solve(ll n){
    memset(dp, -1, sizeof(dp));
    int len = 0;
    while(n){
        num[++len] = n%10;
        n /= 10;
    }
    return dfs(len, K+100, -1, 1, 1).sum;
}
void init(){
    fac[1] = 1;
    for(int i = 2; i <= 20; ++i) fac[i] = (fac[i-1]*10)%mod;
}
int main(){
    init();
    scanf("%lld%lld%lld", &a, &b, &K);
    printf("%lld\n", (solve(b)-solve(a-1)+mod)%mod);
}