题目链接:http://hihocoder.com/problemset/problem/1259
式子可以化简，并且找到一个f的递推式，递推过程如下：
列出来后手动枚举几个f的值，会发现函数值其实就是把二进制的自变量当成三进制来算一次。
答案求的是异或和，要求将所有余数相同的和异或起来，可以考虑用数位dp了，f(i,j)表示长为i的时候，余数为j。由于从高到低更新，那么f(i,j)=∑f(i-1, j+3^(i-1)*(k==1))，k取值为0或者1。倒着推可以一直用期望的余数减去当前加上某位值后的余数，判断最后到头的时候余数是不是0。
这么交是会TLE的，原因是每次都要clear dp数组。
由于只有5个模数，不放再多加一维，记录各个模下的不同余数个数和。
再预处理一下不同模下的幂取模值就行了。
特别注意下：f(0)不存在，但是dp出来f(0)=0，%k=0，所以在处理的时候要减掉这个值。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 66; 6 const int maxm = 66666; 7 const int mod[5] = {3,5,17,257,65537}; 8 LL n; 9 int k, id; 10 LL dp[6][maxn][maxm]; 11 int mul[6][maxn]; 12 int digit[maxn]; 13 14 LL dfs(int l, int sum, bool flag) { 15 if(l == 0) return sum == 0; 16 if(!flag && ~dp[id][l][sum]) return dp[id][l][sum]; 17 int pos = flag ? digit[l] : 1; 18 LL ret = 0; 19 for(int i = 0; i <= pos; i++) { 20 if(i == 0) ret += dfs(l-1, sum, flag&&(i==pos)); 21 else ret += dfs(l-1, (sum+k-mul[id][l-1])%k, flag&&(i==pos)); 22 } 23 if(!flag) dp[id][l][sum] = ret; 24 return ret; 25 } 26 27 LL f(LL n, int sum) { 28 int pos = 0; 29 while(n) { 30 digit[++pos] = n % 2; 31 n >>= 1; 32 } 33 return dfs(pos, sum, true); 34 } 35 36 int main() { 37 // freopen("in", "r", stdin); 38 int T; 39 scanf("%d", &T); 40 for(int i = 0; i < 5; i++) { 41 mul[i][0] = 1; 42 for(int j = 1; j < maxn; j++) { 43 mul[i][j] = (mul[i][j-1] * 3) % mod[i]; 44 } 45 } 46 memset(dp, -1, sizeof(dp)); 47 while(~scanf("%lld%d",&n,&k)) { 48 id = lower_bound(mod, mod+5, k) - mod; 49 LL ret = 0; 50 for(int i = 0; i < k; i++) ret ^= (f(n, i) - (i == 0)); 51 printf("%lld ", ret); 52 } 53 return 0; 54 }