hdu6156

题意

求 \([2, 36]\) 进制下，给定区间内的数是回文数的个数。每存在一个回文数，答案加上该回文数的进制。

分析

10进制下回文数是数位DP 很常见的问题，这道题只需要把在转化数字的时候转化成对应的进制即可。

多开一维数组表示某个进制下的方案数，\(dp\) 数组只需要一次初始化。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[40][60][60]; // 进制，起始位置，长度 （起始位置就是不为 0 的第一个数字）

int digit[60];

int num[60];

ll dfs(int jz, int st, int len, int limit) {

    if(!len) return 1;

    if(!limit && dp[jz][st][len] != -1)

        return dp[jz][st][len];

    ll res = 0;

    int mx = limit ? digit[len] : (jz - 1);

    for(int i = 0; i <= mx; i++) {

        if(st == len && i == 0)

            res += dfs(jz, st - 1, len - 1, limit && i == mx);

        else {

            num[len] = i;

            if((st & 1) == 1) {

                int mid = ((st + 1) >> 1);

                if(len >= mid) {

                    res += dfs(jz, st, len - 1, limit && i == mx);

                } else if(len < mid) {

                    if(num[mid * 2 - len] == i) {

                        res += dfs(jz, st, len - 1, limit && i == mx);

                    }

                }

            } else {

                int mid = (st >> 1) + 1;

                if(len >= mid) {

                    res += dfs(jz, st, len - 1, limit && i == mx);

                } else {

                    if(num[st + 1 - len] == i) {

                        res += dfs(jz, st, len - 1, limit && i == mx);

                    }

                }

            }

        }

    }

    if(!limit) dp[jz][st][len] = res;

    return res;

}

ll f(int jz, int n) { // jz进制下小于等于 n 的回文数字的个数

    int len = 0;

    while(n) {

        digit[++len] = n % jz;

        n /= jz;

    }

    ll res = dfs(jz, len, len, 1);

    return res;

}

int main() {

    memset(dp, -1, sizeof dp);

    int T;

    scanf("%d", &T);

    int Case = 0;

    while(T--) {

        int jz1, jz2;

        int n, m;

        scanf("%d%d%d%d", &n, &m, &jz1, &jz2);

        ll ans = 0;

        for(int i = jz1; i <= jz2; i++) {

            ll num = f(i, m) - f(i, n - 1);

            ans = ans + (1LL * num * i + (m - n + 1 - num));

        }

        printf("Case #%d: %lld\n", ++Case, ans);

    }

    return 0;

}

巴特西

hdu6156

hdu6156

题意

分析

code

最新文章

热门文章