BZOJ 3329 Xorequ 数位DP+矩阵乘法

题目大意：给定n，求[1,n]以内以及[1,2^n]以内有多少x满足x^3x=2x

x^3x=2x等价于x^2x = 3x

而3x=x+2x 且2x=x<<1

故x满足条件当且仅当x&(x<<1)=0

故x的二进制拆分中任意两个1不相邻

令f[i]为i位数中最高位为0的满足条件的数的数量

g[i]为i位数中最高位为1的满足条件的数的数量

则显然有

f[i+1]=f[i]+g[i]

g[i+1]=f[i]

于是第一问数位DP 第二问矩阵乘法即可

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define MOD 1000000007 using namespace std; typedef long long ll; struct Matrix{ ll xx[2][2]; Matrix(ll _,ll __,ll ___,ll ____) { xx[0][0]=_; xx[0][1]=__; xx[1][0]=___; xx[1][1]=____; } ll* operator [] (int x) { return xx[x]; } }; ll f[70],g[70]; void operator *= (Matrix &x,Matrix &y) { int i,j,k; Matrix z(0,0,0,0); for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) z[i][j]+=x[i][k]*y[k][j],z[i][j]%=MOD; x=z; } ll Digital_DP(ll x) { int i,temp=0; long long re=0; for(i=0;1ll<
      
       >=1; } return (a[0][1]+a[1][1])%MOD; } int main() { int T,i;ll x; f[0]=1; for(i=1;i<=63;i++) f[i]=f[i-1]+g[i-1],g[i]=f[i-1]; for(cin>>T;T;T--) { scanf("%lld",&x); printf("%lld\n", Digital_DP(x+1) ); printf("%lld\n", Matrix_Mutiplication(x) ); } }