牛客国庆集训派对day5 C.Great Deceiver

题意： 给定$n$和$k$，问在$k$进制和$-k$进制下值相同的数$x$的个数，$x\le n$。 数据范围：$1\le n\le 10^{15},2\le k\le 1000$

题解： 转换成$k$进制考虑下，发现只有当每个奇数位都为$0$，即不会产生负数影响时的数才是合法的数，因此考虑转换成$k$进制进行数位$dp$，限制奇数位为$0$即可。

代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<stack> #include<queue> #include<map> #include<vector> #include<cmath> using namespace std; typedef long long ll; template<typename T> inline T Read(){ T s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();} return s * f; } #define read() Read<int>() #define readl() Read<long long>() ll n; int k; const int N = 70; int bit[70]; ll dp[N]; ll dfs(int u, bool limit) { //到达了最后一个数 if(u == -1) return 1; //当没有到达顶端且这个数之前已经被计算过了 /* 如 n = 3 4 5 当前是 2 x y, 且u在x这个位置 但是之前 1 x y 时，x 和 y的所有合法情况都被考虑过了，因此不需要再次重复计算 故此时直接返回即可 */ if(!limit && dp[u] != -1) return dp[u]; int last = limit ? bit[u] : (k - 1); if(u & 1) last = 0; ll ans = 0; for(int i = 0; i <= last; i++) { ans += dfs(u - 1, limit && i == bit[u]); } /* 如上，这种情况下dp[u]会被多次使用，故记忆此次避免重复计算 */ if(!limit) dp[u] = ans; return ans; } void solve() { n = readl(), k = read(); ll tn = n; int g = 0; while(tn) { bit[g++] = tn % k; tn /= k; } memset(dp, -1, sizeof dp); printf("%lld\n", dfs(g - 1, true)); } int main() { int T = 1; //T = read(); for(int i = 1; i <= T; ++i) { solve(); } return 0; }