第七场

F. Sumire

思路

• 记录状态 \(dp_{rem,pre}\) 剩余 \(rem\) 位，前面有 \(pre\) 个数位 d。
• 转移的时候不能枚举 B 个数，发现只有数位 = d 的时候对 pre 有更新，所以直接讨论就好了。

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
typedef double db;
#define re _read
#define ALL(x) (x).begin(),(x).end()
#define SZ(v) ((int)v.size())
#define fi first
#define se second
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
using namespace std;
mt19937 mrand(random_device{}()); 
int rnd(int x) { return mrand() % x;}
template<class T>
inline void _read(T& x) {
    static T ans;
    static unsigned int c;
    static bool p;
    for (c = getchar(); c != '-' && (c < '0' || c > '9'); c = getchar());
    if (c == '-') p = false, c = getchar(); else p = true;
    for (ans = 0; c <= '9' && c >= '0'; c = getchar()) ans = ans * 10 + c - '0';
    x = p ? ans : -ans;
}
/*----------------------------------------------------------------------------------------------------*/
const int mod = 1e9 + 7;

ll qmi(ll a, ll k, int mod) {
    ll res = 1;
    if (a == 0 && k == 0) return 0;
    while (k) {
            if (k & 1)
                    res = res * a % mod;
            a = a * a % mod;
            k >>= 1;
    }
    return res;
}

ll k, B, D, l, r;
ll dp[70][70];

ll dfs(int rem, int pre) {
    ll& ans = dp[rem][pre];
    if (ans != -1) return ans;
    ans = 0;
    if (!rem) return ans = qmi(pre, k, mod);
    ans = dfs(rem - 1, pre + 1) + (B - 1) * dfs(rem - 1, pre) % mod;
    if (ans >= mod) ans -= mod;
    return ans;
}

ll solve(ll x) {
    x ++;
    vector<int> d;
    while (x) {
        d.pb(x % B);
        x /= B;
    }
    reverse(ALL(d));
    int m = d.size();
    ll ans = 0;
    for (int i = 1; i < m; i++) {
        ans += (B - 2) * dfs(i - 1, 0) % mod;
        if (ans >= mod) ans -= mod;
        ans += dfs(i - 1, D != 0);
        if (ans >= mod) ans -= mod;
    }
    int pre = 0;
    for (int i = 0; i < m; i++) {
        if (i == 0) {
            if (!D) {
                ans += (d[i] - 1) * dfs(m - i - 1, pre) % mod;
            }
            else {
                if (d[i] > D) ans += (dfs(m - i - 1, pre + 1) + (d[i] - 2) * dfs(m - i - 1, pre) % mod) % mod;
                else ans += (d[i] - 1) * dfs(m - i - 1, pre) % mod;
            }
            if (ans >= mod) ans -= mod;
        }
        else {
            if (d[i] > D) ans += (dfs(m - i - 1, pre + 1) + (d[i] - 1) * dfs(m - i - 1, pre) % mod) % mod;
            else ans += d[i] * dfs(m - i - 1, pre) % mod;
            if (ans >= mod) ans -= mod;
        }
        if (d[i] == D) pre++;
    }
    return ans;
}

int main() {
    int T;
    re(T);
    while (T--) {
        memset(dp, -1, sizeof dp);
        re(k), re(B), re(D), re(l), re(r);
        printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);
    }
    return 0;
}