bzoj 3329 Xorequ 题解（数位DP，矩阵快速幂）

原题链接： bzoj：点我QωQ

题意简述

给定一个$n$，请在

$[1,n]$中（这一问$不$取膜）$[1,2^n]$中（这一问的答案对$10^9+7$取膜）

求有多少$x$满足$x$^$3x=2x$，其中 ^表示按位异或。

数据

输入

先有一个$T$，表示有$T$组数据。($T<=1000$) 接下来$T$行，每行一个$n(n<=10^{18})$。

输出

对于每个数据，输出两行答案，第一行是$[1,n]$中的解数，第二行是$[1,2^n]$总的解数。第一个$不$取膜，第二个取膜。

样例

输入 1 1 输出 1 2

思路

看起来好像$1$简单，$2$难。但是对于我这个数学很好但是不会数位$DP$的数竟狗，我感觉$2$简单，$1$难。无论如何，现在我是都会了。先讲第一问$⑧$。

part1. 第一问

首先先化简那个式子。同时异或$x$，得 $x$^$2x$=$3x$ $x$^$2x$=$x+2x$ 我们知道，$a+b=a$^$b$+$(a$&$b)<<1$（在写$a+b$的时候要用到这个） 继续推： $x$ ^ $2x$=$x$ ^ $2x$+$(x$&$2x)<<1$ $(x$&$2x)<<1=0$ $x$&$2x=0$ $x$&$(x<<1)=0$ 化简到这里，就相当于$x$没有连续的$1$。（想想，如果有连续的$1$，那么$x$和$x<<1$就会有一个公共位，那么$x$&$(x<<1)$就不会$=0$）

已经能看出来数位$DP$了。设$dp[i][0/1]$为长度为$i$，首位是$0/1$的方案数。 如果第$i$位是$1$，那么$i-1$位一定不能是$1$,只能是$0$。所以$dp[i][1]=dp[i-1][0]$。 如果第$i$位是$0$，那随便了，$dp[i][0]=dp[i-1][0]+dp[i-1][1]$。

然后就是如何拆分的问题。由于是二进制，要稍微简单一点。我们拆分原数，设原数长度为$cnt$，位数存在$d$数里（我是按照网上多数人的写法反着存的，因为正着实在不方便）。考虑两种情况：

位数比原数小，显然是珂取的。此时答案$=dp[1...(cnt-1)][1]$位数$=$原数，而且和原数有一些相同的前缀。这个比较复杂。$i$遍历前缀位置的下一个位置，从$cnt-1$到$1$，就是前缀位置是从$cnt$到$2$。显然，第$i$个位置是珂以取$0$的。当然，如果$d[i]$和$d[i+1]$都是$0$，继续下去就会出错，及时$break$掉。当然，这个是取不到原数的，我们考虑将原数加$1$，计算结束再减回来。

part2. 第二问

身为一个数学竞赛狗，以前做过一些数学竞赛题。见IWYMIC2008 第五题：

一个十位数，其数码只能是2或3，且没有2个3是相邻的，这样的十位数有多少个？

简直和这个题一模一样，只是$0,1$换成了$2,3$而已。如果去看那个题的题解（上百度找），会发现： 这${}^{tm}$就是一斐波那契！！！ 矩阵快速幂就过了！！！

代码：

#include<bits/stdc++.h> using namespace std; namespace Flandle_Scarlet { #define int long long #define mod 1000000007 int t,n; int dp[70][2]; void DP() { dp[0][0]=1; for(int i=1;i<=63;++i) { dp[i][0]=dp[i-1][0]+dp[i-1][1]; dp[i][1]=dp[i-1][0]; } } int Case1()//第一问 { ++n;//先+1 int d[70];int cnt=0; while(n) { d[++cnt]=(n&1); n>>=1; } int ans=0; for(int i=1;i<cnt;++i) { ans+=dp[i][1]; } for(int i=cnt-1;i>=1;--i) { if (d[i]==1) { ans+=dp[i][0]; if (d[i+1]==1) break; } } --n;//再回来 return ans; } class Matrix//square matrix { #define N 5//changeable public: int a[N][N]; //variable list int n;//size //initialization Matrix() { memset(a,0,sizeof(a)); n=0; } Matrix(int _n) { memset(a,0,sizeof(a)); n=_n; } Matrix(int _n,int _x) {_x%=mod; n=_n; for(int i=0;i<N;++i) { for(int j=0;j<N;++j) { a[i][j]=_x; } } } //get value int* operator[](int i) { return *(a+i); } void Put() { for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { printf("%lld ",a[i][j]); }putchar('\n'); } } //set value void Set(int x) {x%=mod; for(int i=0;i<N;++i) { for(int j=0;j<N;++j) { a[i][j]=x; } } } void Identity() { memset(a,0,sizeof(a)); for(int i=0;i<N;++i) { a[i][i]=1; } } #undef N //5 }; Matrix operator*(Matrix x,Matrix y) { Matrix ans(x.n,0); int n=ans.n; for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { for(int k=1;k<=n;++k) { ans[i][j]+=x[i][k]*y[k][j]; ans[i][j]%=mod; } } } return ans; } Matrix operator^(Matrix x,int p) { Matrix ans(x.n,0); ans.Identity(); while(p) { if (p&1) ans=ans*x; x=x*x,p>>=1; } return ans; }//矩阵 int Case2() { if (n==1) return 2; if (n==2) return 3;//特判边界 Matrix Init(2,0); Init[1][1]=Init[1][2]=1; Matrix Trans(2,1); Trans[2][2]=0; Matrix Ans(2,0); Ans=(Trans^(n+1)); Ans=Ans*Init; return Ans[1][2];//斐波那契板子 } void Solve() { printf("%lld\n%lld\n",Case1(),Case2()); } void Main() { if (0) { freopen("","r",stdin); freopen("","w",stdout); } DP(); scanf("%lld",&t); while(t--) { scanf("%lld",&n); Solve(); } } #undef int //long long #undef mod //1000000007 }; main() { Flandle_Scarlet::Main(); return 0; }

回到总题解界面