Awkward Pairs [CodeChef ProCon 2018 D]

Contest: https://www.codechef.com/PROC2018/problems/PROC18C
Practice: https://www.codechef.com/problems/PROC18C

1≦L≦R≦10^18が与えられる。
以下の条件を満たすペアの組み合わせ数mod(10^9+7)でを答えよ。

ペア(x,y)が以下の条件を満たす

• xもyも[L,R]にある
• xとyのそれぞれの桁の総和を取ったものをxx, yyとするとxxとyyは互いに素

前提知識

• 桁DP

考察過程

1. 桁の総和の最大は9*17位なので小さい
2. [L,R]の中で「総和がiとなる数の個数」を数えれば答えるのは簡単そう
3. よくあるテクで[L,R]の計算ではなく[0,R]-[0,L-1]で計算するようにしよう
4. [0,x]の中で「総和がiとなる数の個数」を数えるにはどうすればいいか
5. 桁DPの典型問題

解法

https://www.codechef.com/viewsolution/19758961

solve関数から説明するが、まずはcnt配列を作る。
cnt[i] := [L,R]の中で桁総和がiとなる数が何通りあるか。
これが分かれば、総和の(i,j)を全探索して、gcd(i,j)=1となるi,jについてcnt[i]*cnt[j]の総和を取れば答え。
　
cnt配列を作る部分が問題である。
[L,R]について考えるのではなく、[0,R]-[0,L-1]と言い換えて、[0,x]で問題を考えるようにする。
f(x) := [0,x]の範囲におけるcnt配列を返す
　
最終的に問題となるのは「[0,x]の中で桁総和がiとなる数が何通りあるか」という問題である。
これは桁DPで解決しよう。
dp[dgt][sm][isless] := dgt桁まで確定していて、桁総和がsm、数xよりも小さいかがislessである数の個数
※ isless = 0でここまでxと上位桁が等しい、=1で既にxより小さいことが確定
遷移はよくある桁DPなので、頑張って書く。

ll L, R;
ll dp[22][250][2]; // dp[dgt][sm][isless]
string S; int N;
//---------------------------------------------------------------------------------------------------
vector<ll> f(ll x) {
    rep(dgt, 0, 22) rep(sm, 0, 250) rep(isless, 0, 2) dp[dgt][sm][isless] = 0;
    dp[0][0][0] = 1;
 
    S = to_string(x);
    N = S.length();
 
    rep(dgt, 0, N) rep(sm, 0, 200) rep(isless, 0, 2) {
        int c = S[dgt] - '0';
        rep(i, 0, 10) {
            if (isless == 0 and c < i) continue;
            if (c == i) dp[dgt + 1][sm + i][isless] += dp[dgt][sm][isless];
            else dp[dgt + 1][sm + i][1] += dp[dgt][sm][isless];
        }
    }
 
    vector<ll> res(200);
    rep(sm, 0, 200) rep(isless, 0, 2) res[sm] += dp[N][sm][isless];
    return res;
}
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> L >> R;
 
    auto a = f(R);
    auto b = f(L - 1);
 
    vector<ll> cnt(200);
    rep(i, 0, 200) cnt[i] = a[i] - b[i];
 
    mint ans = 0;
    rep(i, 1, 200) rep(j, i + 1, 200) if(gcd(i,j) == 1) ans += mint(cnt[i]) * mint(cnt[j]);
    cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}