3329: Xorequ

https://www.lydsy.com/JudgeOnline/problem.php?id=3329

分析：

　　因为a+b = a^b + ((a&b)<<1)

　　所以(x&(2x))<<1是0，就是没有相邻的1。然后计算多少x满足没有相邻的1。

　　第一问：数位dp一下，dp[i][j]到第i位，上一个数是j的方案数。

　　第二问：一共n位数，只有第n位为1，所以这n位没有限制，f[i]表示到第i位，的方案数，f[i]=f[i-1]+f[i-2]。看第i位是不是1。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline LL read() {

     LL x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int mod = 1e9 + ;

 LL dp[][], num[];

 struct Matrix{

     int a[][];

     void Clear() { memset(a, , sizeof(a)); }

     void init() { a[][] = a[][] = a[][] = ; }

     Matrix operator * (const Matrix &A) const {

         Matrix C; C.Clear();

         for (int k=; k<; ++k)

             for (int i=; i<; ++i)

                 for (int j=; j<; ++j)

                     C.a[i][j] = (C.a[i][j] + 1ll * a[i][k] * A.a[k][j]) % mod;

         return C;

     }

 };

 LL dfs(int x,int last,bool lim) {

     if (!x) return ;

     if (!lim && dp[x][last]) return dp[x][last];

     int u = lim ? num[x] : ; // u = lim ? num[x] : 0 !!!

     LL res = ;

     for (int i=; i<=u; ++i)

         if (!last || !i) res += dfs(x - , i, lim && i==u);

     if (!lim) dp[x][last] = res;

     return res;

 }

 LL Calc1(LL n) {

     int tot = ;

     while (n) {

         num[++tot] = n & ;

         n >>= ;

     }

     return dfs(tot, , ) - ;

 }

 LL Calc2(LL n) {

     Matrix A; A.Clear(); A.init();

     Matrix res; res.Clear(); res.a[][] = res.a[][] = ;

     while (n) {

         if (n & ) res = res * A;

         A = A * A;

         n >>= ;

     }

     return (res.a[][] + res.a[][]) % mod;

 }

 int main() {

     int T = read();

     while (T--) {

         LL n = read();

         printf("%lld\n%lld\n", Calc1(n), Calc2(n));

     }

     return ;

 }