題目鏈接

BZOJ4197

題解

兩個(gè)人選的數(shù)都互質(zhì)，意味著兩個(gè)人選擇了沒(méi)有交集的質(zhì)因子集合
容易想到將兩個(gè)人所選的質(zhì)因子集合作為狀態(tài)\(dp\)

\(n\)以?xún)?nèi)質(zhì)數(shù)很多，但容易發(fā)現(xiàn)\(\sqrt{n} \approx 22.3\)，這里邊的質(zhì)數(shù)只有\(8\)個(gè)，而大于\(\sqrt{n}\)的質(zhì)因子只會(huì)出現(xiàn)一次，可以特殊討論
我們先將所有數(shù)按最大質(zhì)因子排序，如果最大質(zhì)因子在那\(8\)個(gè)質(zhì)數(shù)里邊，就記為\(1\)
我們?cè)O(shè)\(f[i][s1][s2]\)表示選了前\(i\)個(gè)數(shù)，兩人的質(zhì)因子集合分別為\(s1\)和\(s2\)的方案數(shù)
那么顯然
\[ans = \sum\limits_{s1 \cap s2 = \emptyset} f[n][s1][s2]\]

對(duì)于最大質(zhì)因子不超過(guò)\(sqrt{n}\)的那些數(shù)，我們可以枚舉加入\(s1\)或\(s2\)進(jìn)行轉(zhuǎn)移
對(duì)于同一組最大質(zhì)因數(shù)為\(x\)的數(shù)，我們先將\(f\)拷貝到\(g\)中，令\(g[0|1][i][s1][s2]\)表示該最大質(zhì)因數(shù)加入誰(shuí)中，選了前\(i\)個(gè)數(shù)，質(zhì)因子集合為\(s1\)，\(s2\)的方案數(shù)
求完后令\(f[i][s1][s2] = g[0][i][s1][s2] + g[1][i][s1][s2] - f[i][s1][s2]\)，因?yàn)樵瓉?lái)的\(f\)是不包含這一組數(shù)的方案，而兩個(gè)\(g\)都包含了不包含這一組數(shù)的方案數(shù)，要減去一個(gè)

由于空間問(wèn)題，\(f\)和\(g\)都要通過(guò)逆序轉(zhuǎn)移壓掉\(i\)那一維

然后就做完了

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<map> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define mp(a,b) make_pair<int,int>(a,b) #define cls(s) memset(s,0,sizeof(s)) #define cp pair<int,int> #define LL long long int using namespace std; const int maxn = 505,maxm = 1 << 8,INF = 1000000000; inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag; } int f[maxm][maxm],g[2][maxm][maxm]; int n,P,a[maxn]; int p[] = {2,3,5,7,11,13,17,19}; struct node{int x,p; }e[maxn]; inline bool operator <(const node& a,const node& b){return a.p < b.p; } int getp(int x){for (int i = 0; i < 8; i++)if (x % p[i] == 0) while (x % p[i] == 0) x /= p[i];return x; } void init(){for (int i = 2; i <= n; i++)for (int k = 0; k < 8; k++)if (i % p[k] == 0)a[i] |= (1 << k); } int main(){n = read(); P = read(); init();for (int i = 2; i <= n; i++) e[i].x = i,e[i].p = getp(i);sort(e + 2,e + 1 + n);f[0][0] = 1;for (int i = 2; i <= n; i++){int x = e[i].x,s = a[x];if (e[i].p == 1){for (int j = maxm - 1; ~j; j--){for (int k = maxm - 1; ~k; k--){int t = f[j][k];f[j][k | s] = (f[j][k | s] + t) % P;f[j | s][k] = (f[j | s][k] + t) % P;}}}else {for (int j = 0; j < maxm; j++)for (int k = 0; k < maxm; k++)g[0][j][k] = g[1][j][k] = f[j][k];int nxt = i;while (nxt < n && e[nxt + 1].p == e[i].p) nxt++;for (int l = 0; l <= nxt - i; l++){x = e[l + i].x,s = a[x];for (int j = maxm - 1; ~j; j--){for (int k = maxm - 1; ~k; k--){g[0][j | s][k] = (g[0][j | s][k] + g[0][j][k]) % P;g[1][j][k | s] = (g[1][j][k | s] + g[1][j][k]) % P;}}}i = nxt;for (int j = 0; j < maxm; j++)for (int k = 0; k < maxm; k++)f[j][k] = (((g[1][j][k] + g[0][j][k]) % P - f[j][k]) % P + P) % P;}}int ans = 0;for (int j = 0; j < maxm; j++)for (int k = 0; k < maxm; k++)if (!(j & k)) ans = (ans + f[j][k]) % P;printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/9157134.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ4197 [Noi2015]寿司晚宴 【状压dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。