題目鏈接

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

題解

嗯早就想寫的題，昨天因為某些不可告人的原因（大霧）把這題寫了，今天再來寫題解
神仙題，做法大概就是，構造一個矩陣，左上角是\(1\), 往下每個數都是上面的\(3\)倍，往右每個數都是左面的\(2\)倍，然后在上面跑狀壓DP，求有多少種選法使得沒有兩個被選的位置有公共邊
然后把左上角改成\(5,7,11...\)分別做一遍，答案相乘即可

嗯，時間復雜度……玄學？
下面給出我的分析:
考慮對一個\(r\)行\(c\)列(\(r<c\))的矩陣進行狀壓DP，長度為\(r\)的沒有連續兩個\(1\)的01序列個數是\(Fib(r)=O(1.618^r)\), 故狀壓DP的復雜度為\[O((1.618^2)^r\times c)=O(2.618^rc)\]
對于一個左上角是\(i\)的矩陣，行數為\(O(\log_3{\frac{n}{i}})\), 列數為\(O(\log_2{\frac{n}{i}})\), 故進行狀壓DP的復雜度為\[O(2.618^{\log_3{\frac{n}{i}}}\log_2\frac{n}{i})=O((\frac{n}{i})^{0.876}\log n)\]
而我們要做的就是對\(i=1,5,7,11...\)求和，那么不妨放縮成對\(i=1,2,...,n\)求和，\[\sum^{n}_{i=1}(\frac{n}{i})^{0.876}\log n=n^{0.876}\log n\int^{n}_{0}x^{-0.876}\textze8trgl8bvbqx=O(n\log n)\]

代碼

#include<cstdio> #include<cstdlib> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 1e5; const int P = 1e9+1; const int lg2N = 17; const int lg3N = 11; int cnt[N+3]; llong dp[lg2N+2][(1<<lg3N)+3]; int n; llong ans;bool isok(int x) {return (x&(x>>1))==0 && (x&(x<<1))==0;} void updsum(llong &x,llong y) {x = (x+y)%P;}void solve(int x) {llong ret = 0ll; int x0 = x;for(int i=1; x<=n; i++,x*=2){int xx = x; cnt[i] = 0;for(; xx<=n; cnt[i]++,xx*=3);for(int j=0; j<(1<<cnt[i]); j++){if(isok(j)){if(i==1) {dp[i][j] = 1ll;}else{int jj = ((1<<cnt[i-1])-1)^j;for(int k=jj; k>=0; k=(k==0?-1:((k-1)&jj))){updsum(dp[i][j],dp[i-1][k]);}}if(x*2>n) {updsum(ret,dp[i][j]);}}}}ans = ans*ret%P;x = x0;for(int i=1; x<=n; i++,x*=2){int xx = x,nn = 1;for(int j=0; j<(1<<cnt[i]); j++){dp[i][j] = 0ll;}cnt[i] = 0;} }int main() {scanf("%d",&n); ans = 1ll;for(int i=1; i<=n;){solve(i);if(i%6==1) i+=4;else i+=2;}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 2734 [HNOI2012]集合选数 (状压DP、时间复杂度分析)的全部內容，希望文章能夠幫你解決所遇到的問題。

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