题目链接：https://vjudge.net/problem/UVALive-7271
题意：Stan is crazy about math. One day, he was confronted with an interesting integer function defined on positive integers, which satisfies f(1) = 1 and for every positive integer n, 3 × f(n) × f(2n + 1) = f(2n) × (1 + 3f(n)), f(2n) < 6 × f(n). He wanted to know, in the range of 1 to n, for a given k, what are f(i) mod k like. For simplicity, you could just calculate the number of i which satisfies f(i) mod k = t for every t in range of 0 to k–1 as g(t), and tell Stan what is all g(x) xor up is.
定义了一个f函数，我们不难发现f[i] 就是i的二进制下为1的位的3的幂次方的和，g（x）函数就是f(1) ~ f(n) 中mod k = x的个数。
由于n范围1e18， 我们考虑用数位DP来求解，dp[i][j] 表示第i位，余数为j的个数，那么我们就在二进制上进行数位DP就可以了。
这道题uva好像数据有问题，可以到这里交打开链接
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[65][70000], p[65]; //dp[i][j]表示第i位余数为j的答案 int a[65], k; void init() { ll ret = 1; p[0] = 1; for(int i = 1; i <= 61; ++i) { ret = ret * 3 % k; p[i] = ret; } } ll dfs(int pos, int sum, int limit) { if(pos == -1) return sum == 0; //为0的话说明可以模数为0 if(!limit && dp[pos][sum] != -1) return dp[pos][sum]; int up = limit ? a[pos] : 1; //二进制最大为1 ll ret = 0; for(int i = 0; i <= up; ++i) { ll tmp = sum; if(i) tmp = (tmp - p[pos] + k) % k; //该位为1的话就减去该位权 ret += dfs(pos - 1, tmp, limit && (i == up)); } if(!limit) dp[pos][sum] = ret; return ret; } int main() { int t; scanf("%d", &t); while(t--) { memset(dp, -1, sizeof(dp)); ll n; scanf("%lld%d", &n, &k); init(); ll tmp = 0; int tot = 0; ll x = n; while(x) //拆分成二进制存储 { a[tot++] = x & 1; x >>= 1; } for(int i = 0; i < k; ++i) { ll ans = dfs(tot - 1, i, 1); if(i == 0) ans--; //算的是[0, i]的区间，所以要减去1 tmp ^= ans; } printf("%lld\n", tmp); } return 0; }
