BZOJ 3329 Xorequ (數位DP、矩陣乘法)

手動博客搬家: 本文發表于20181105 23:18:54, 原地址https://blog.csdn.net/suncongbo/article/details/83758728

題目鏈接

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

思路分析：

這道題完全是兩道題拼在了一起。。
我們首先觀察一下這個等式:
我們不妨可以把它移項變成\(x\ xor\ (2x)=3x\)
然后我們發現，\(3x=x+2x\), 也就是\(x\ xor\ (2x)=x+2x\).
并且顯然有不等式\(|x-y|\le x\ and\ y\le x \ xor\ y\le x \ or\ y\le x+y\), 故有\(x\ or\ 2x=x+2x\), 也即\(x\ and\ 2x = 0\).
這意味著什么？我們考慮一個\(x\):

x = 00110111001010111010100111011 2x = 01101110010101110101001110110 x^2x = 01011001011111001111101001101

觀察可得，\(x\ xor\ 2x\)相當于將二進制表示作了異或差分。同時，所有相鄰的\(1\)只會保留最后一個和第一個的前一個，而中間這一部分都會被變成\(0\). 因此，題目中的等式成立等價于\(x\)的二進制表示下不存在相鄰的\(1\).
另一種理解方式是：異或相當于二進制不進位加法，而既然是不進位加法，那么一旦進了位就會對數值有損失，當且僅當\(x+2x\)不進位的時候它才等于\(x\ xor\ 2x\). 而\(2x\)相當于把\(x\)的二進制表示左移一位，進位發生當且僅當\(x\)與\(2x\)在同一位置上都為\(1\)，也即\(x\)有連續的至少兩個\(1\).
完成了這一步轉化之后，問題就相當于求\(n\)或者\(2^n\)內有多少數的二進制表示下不存在兩個連續的\(1\).
第二問
\([0,2^n-1]\)之內的數對應長度為\(n\)的\(01\)序列，不能有連續兩個\(1\), 這顯然是斐波那契數列。（因為有一種進制叫斐波那契進制，有一個定理是任何一個整數都可以被唯一地劃分成若干不連續的斐波那契數之和）嚴謹一些的證明是，設\(F(n)\)表示長度為\(n\)的滿足條件的\(01\)序列有多少個，則\(F(n)\)如果第一位為\(1\), 那么第二位必然為\(0\), 后面\(n-2\)位方案數\(F(n-2)\); 如果第一位為\(0\), 那么后面的位任選，方案數\(F(n-1)\). 因此\(F(n)=F(n-1)+F(n-2)\).
但是我們剛才討論的是\([0,2^n-1]\), 但題目要求的是\([1,2^n]\), 顯然\(0\)必定滿足條件，\(2^n\)也必定滿足條件，因此答案為\(F(n)-1+1=F(n)\).
用矩快速冪遞推即可，時間復雜度\(O(\log n)\), \(8\)倍常數。
第一問
這一問對\(n\)有更細致的要求，每一位都有要求，因此采取數位\(dp\).
設\(dp[i][j=0/1][k=0/1]\)表示有多少個\(i\)位數 (\([0,2^i-1]\))滿足條件，且第\(i\)位是否必須選\(0\) (即如果\(j\)為\(1\)則必須選\(0\), 否則選\(0,1\)均可)，\(k\)表示是否卡上界?？紤]轉移，這一位能夠選\(1\)的條件是，\(j\)是\(false\), 并且選了\(1\)之后不會超過\(n\)的限制。超過\(n\)的限制的充要條件是，當前卡上界，且\(n\)這一位為\(0\). 這一位選\(0\)無條件轉移。于是就可以成功DP了，時間復雜度\(O(\log n)\), 常數\(4\)倍。
（但是由于蒟蒻太傻，寫代碼的時候用了大量的(!(n&(1<<(pos-1))))來判斷\(n\)這一位是否為\(0\), 因此代碼十分丑陋，有的地方\(7\)層括號套起來。。希望讀者見諒）

代碼實現

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define llong long long #define ldouble long double #define uint unsigned int #define ullong unsigned long long #define udouble unsigned double #define uldouble unsigned long double #define modinc(x) {if(x>=P) x-=P;} #define pii pair<int,int> #define piii pair<pair<int,int>,int> #define piiii pair<pair<int,int>,pair<int,int> > #define pli pair<llong,int> #define pll pair<llong,llong> #define Memset(a,x) {memset(a,x,sizeof(a));} using namespace std;llong n;namespace Subtask1 {const int N = 60;llong dp[N+2][2][2];llong dfs(int pos,bool f,bool t){ // printf("DFS %d %d %d %lld\n",pos,(int)f,(int)t,dp[pos][f][t]);if(pos==1) return dp[pos][f][t] = 1ll+(f==false && (!(t&&(!(n&(1ll<<(pos-1)))))));if(dp[pos][f][t]) return dp[pos][f][t];llong cur = dfs(pos-1,false,(t&&(!(n&(1ll<<(pos-1))))));if(f==false && (!(t&&(!(n&(1ll<<(pos-1))))))) cur += dfs(pos-1,true,t); // printf("dfs %d %d %d %lld\n",pos,(int)f,(int)t,cur);return dp[pos][f][t] = cur;}void solve(){memset(dp,0,sizeof(dp));llong ans = dfs(N,false,true);printf("%lld\n",ans-1);} }namespace Subtask2 {const int N = 3;const int P = 1e9+7;struct Matrix{llong a[N+2][N+2];int sz1,sz2;Matrix() {}Matrix(int _sz){sz1 = sz2 = _sz;for(int i=1; i<=sz1; i++){a[i][i] = 1ll;for(int j=1; j<=sz2; j++){if(i!=j) a[i][j] = 0ll;}}}void clear(){for(int i=1; i<=sz1; i++) for(int j=1; j<=sz2; j++) a[i][j] = 0ll;}void setsz(int _sz) {sz1 = sz2 = _sz; clear();}void setsz2(int _sz1,int _sz2) {sz1 = _sz1,sz2 = _sz2; clear();}};Matrix operator *(Matrix m1,Matrix m2){Matrix ret; ret.setsz2(m1.sz1,m2.sz2);for(int i=1; i<=m1.sz1; i++){for(int j=1; j<=m2.sz2; j++){ret.a[i][j] = 0ll;for(int k=1; k<=m1.sz2; k++){ret.a[i][j] += m1.a[i][k]*m2.a[k][j];}ret.a[i][j] %= P;}} return ret;}Matrix mquickpow(Matrix x,llong y){Matrix cur = x,ret = Matrix(x.sz1);for(int i=0; y; i++){if(y&(1ll<<i)) {ret = ret*cur; y-=(1ll<<i);}cur = cur*cur;} return ret;}void solve(){Matrix fib; fib.setsz(2); fib.a[1][1] = fib.a[1][2] = fib.a[2][1] = 1ll; fib.a[2][2] = 0ll;Matrix ori; ori.setsz2(1,2); ori.a[1][1] = ori.a[1][2] = 1ll;Matrix gg = ori*fib;Matrix fibn = ori*mquickpow(fib,n); llong ans = fibn.a[1][1];printf("%lld\n",ans);} }int main() {int T; scanf("%d",&T);while(T--){scanf("%lld",&n);Subtask1::solve();Subtask2::solve();}return 0; } 發表于 2019-01-22 19:53 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部

總結

以上是生活随笔為你收集整理的BZOJ 3329 Xorequ (数位DP、矩阵乘法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。