P3226 HNOI2012 集合選數 狀壓DP

2022-09-22 21:55:06 字數 714 閱讀 4157

題面

我們發現每個數 \(n\) 是否被選,只與 \(\frac,\frac,2n,3n\) 有關,那麼我們考慮建一張表,表上每一行按照 \(\times 3\) 的方式遞增,每一列按照 \(\times 2\) 的方式遞增,那麼對於同一張表,任意上下左右相鄰的數都是不能選的,那麼這樣的表一共有 \(n-\frac-\frac+\frac\) 種,每一張表的轉移是 \(\log_2 n\times 2^\) 雖然理論複雜度達到了 \(5e10\) 但是實際跑下來十分優秀,可能因為後來的表變的極小,轉移的複雜度大幅降低

#includeusing namespace std;

namespace zzc

while(isdigit(ch))

return x*f; }

const int maxn = 1e5+5;

const int maxm = 5005;

const int mod = 1e9+1;

int n,r,sta[maxm],num[20],f[20][maxm];

long long ans=1,sum;

bool vis[maxn];

void update(int x)

}} for(int i=0;i<(1

void work() }

int main()

題解 P3226 HNOI2012 集合選數

一道非常妙的構造題 qwq 要 2x , 3x 都不在集合內,但直接處理貌似非常不好,所以我們需要構造出一個與原命題等價的命題。 貌似是這個...