#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> w;
ll dp[70][2][2][1050][13];

ll dfs(int pos, bool lim, int zero, ll res, ll b){
    if(pos == 0) return res == 0;
    if(dp[pos][lim][zero][res][b] != -1) return dp[pos][lim][zero][res][b];
    int upp = (lim? w[pos]: b - 1); ll ans = 0;
    for(int i = 0; i <= upp; i ++){
        if(zero && (!i)) ans += dfs(pos - 1, 0, 1, 0, b);
        else ans += dfs(pos - 1, lim && (i == upp), 0, res ^ (1ll << i), b);
    }
    return dp[pos][lim][zero][res][b] = ans;
}

ll work(ll base, ll x){
    w.assign(1, 0);
    while(x){
        w.push_back(x % base);
        x /= base;
    }
    return dfs(w.size() - 1, true, 1, 0, base);
}

void solve(){
    ll b, l, r;
    cin >> b >> l >> r;
    cout << work(b, r) - work(b, l - 1) << "\n";
}

int main(){

    memset(dp, -1, sizeof dp);
    int t; cin >> t;
    while(t --){
        solve();
    }

    return 0;
}

如果你是这样设计的状态，请注意：lim == true 的状态不可以永久记忆化。因为如果 lim == true 的话，即使状态一样，后面结果也可能不一样。 请重新计算！像这样：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> w;
ll dp[70][2][1050][13];

ll dfs(int pos, bool lim, int zero, ll res, ll b){
    if(pos == 0) return res == 0;
    if(!lim && dp[pos][zero][res][b] != -1) return dp[pos][zero][res][b];
    int upp = (lim? w[pos]: b - 1); ll ans = 0;
    for(int i = 0; i <= upp; i ++){
        if(zero && (!i)) ans += dfs(pos - 1, 0, 1, 0, b);
        else ans += dfs(pos - 1, lim && (i == upp), 0, res ^ (1ll << i), b);
    }
    if(lim) return ans;
    else return dp[pos][zero][res][b] = ans;
}

ll work(ll base, ll x){
    w.assign(1, 0);
    while(x){
        w.push_back(x % base);
        x /= base;
    }
    return dfs(w.size() - 1, true, 1, 0, base);
}

void solve(){
    ll b, l, r;
    cin >> b >> l >> r;
    cout << work(b, r) - work(b, l - 1) << "\n";
}

int main(){

    memset(dp, -1, sizeof dp);
    int t; cin >> t;
    while(t --){
        solve();
    }

    return 0;
}