hiho1259 A Math Problem (数位dp)

题目链接：http://hihocoder.com/problemset/problem/1259

题目大意：g(t)=(f(i)%k=t)的f(i)的个数　求所有的(0-k-1)的g(i)的异或总值

思路：首先推出公式3*f(n)*f(2n+1)=f(2n)*(1+3f(n))

3f(n)和3f(n)+1相邻的两个数肯定是互质的所以解出f(2n)=3*f(n) f(2n+1)=3*f(n)+1

相当于是n表示成2进制但是每位的权值为3 然后就是数位dp的过程了

dp[k][i][j] k表示在模哪一个数 i表示数位 j表示模数减掉当前剩余的

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 long long dp[6][66][65540];
 7 int  mod,k;
 8 int dig[70];
 9 long long tmp[70];
10 int solve(long long n){
11     int len=0;
12     while(n>0){
13         dig[len++]=n&1;
14         n>>=1;
15     }
16     return len;
17 }
18 void init(int len){
19     tmp[0]=1;
20     for(int i=1;i<=len+1;i++){
21         tmp[i]=tmp[i-1]*3%mod;
22     }
23 }
24 inline long long dfs(int pos,int val,int limit){
25     if(pos<0) {
26         return val==0;
27     }
28     if(!limit && dp[k][pos][val]!= -1)
29         return dp[k][pos][val];
30     int end_=limit?dig[pos]:1;
31     long long ret=0;
32     for(int i=0;i<=end_;i++){
33         ret+=dfs(pos-1,(val-i*tmp[pos]+mod)%mod,limit&&(i==dig[pos]));
34     }
35     if(!limit) dp[k][pos][val]=ret;
36     return ret;
37 }
38 int main(){
39     int T;
40     scanf("%d",&T);
41     long long n,ans=0;
42     memset(dp,-1,sizeof(dp));
43     while(T--){
44         scanf("%lld%d",&n,&mod);
45         if(mod==3) k=0;
46         else if(mod==5) k=1;
47         else if(mod==17) k=2;
48         else if(mod==257) k=3;
49         else if(mod==65537) k=4;
50         int len=solve(n);
51         init(len);
52         ans=0;
53         for(int i=0;i<mod;i++){
54             ans^=(dfs(len-1,i,1)-(i==0));
55         }
56         printf("%lld
",ans);
57     }
58     return 0;
59 }