BZOJ2734 [HNOI2012]集合选数

			    <div class="post_brief"><p>
最初感觉好多状态怎么做。</p>

然后发现（其实是瞟了一下题解）如果把一个数分成2^a*3^b*c，那么c只影响上界。2^a*3^b中a最大是16，b最大是10，列一张17*11的表出来，然后发现右下方还有很多空东西。于是直接像插头一样状压一下轮廓线呗。反正对一个数有影响的只有它的上面和左边。最近写插头写得有点疯啊。其实它的很多思想都是可以推广出来用的。比如最小表示啥的。

于是如果直接这样写的话大概要跑30000多次dp，还是比较悬。然后再想想发现只有表里能取的数的形状发生改变的时候才会改变dp的答案。表里面的数很少所以改变次数也应该很少。所以记一下上一次的形状是什么然后比较相不相同，相同就直接沿用。

然后跑得飞快。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define _l (long long int)
#define pow2(x) (1<<(x))
const int maxn = 19;
const int maxm = 15;
const int maxv = 100000;
const int maxst = pow2(11) + 9;
const int mod = 1e9 + 1;
int f[2][maxst], vl[maxn][maxm], n, m, v;
int dis[maxn], ldis[maxn], lans, ans;
void pre() {
for (int i = 0; i < maxn; ++ i) {
vl[i][0] = (1 << i);
if (vl[i][0] > maxv)
vl[i][0] = -1;
for (int j = 1; j < maxm; ++ j)
if (vl[i][j - 1] > -1) {
vl[i][j] = vl[i][j - 1] * 3;
if (vl[i][j] > maxv)
vl[i][j] = -1;
}
else
vl[i][j] = -1;
}
}
bool getDis(int x) {
memset(dis, 0, sizeof(dis));
for (int i = 0; i < maxn; ++ i)
while (vl[i][dis[i]] > -1 && x >= vl[i][dis[i]])
++ dis[i];
bool eq(1);
for (int i = 0; i < maxn && eq; ++ i)
if (dis[i] != ldis[i])
eq = 0;
if (!eq)
memcpy(ldis, dis, sizeof(dis));
return eq;
}
inline void incm(int& a, int b) {
a += b;
if (a >= mod)
a -= mod;
}
int dp() {
int prv(1), cur(0), m(dis[0]), e(pow2(m));
memset(f, 0, sizeof(f));
f[cur][0] = 1;
for (int i = 0; dis[i]; ++ i)
for (int j = 0; j < dis[i]; ++ j) {
swap(cur, prv);
memset(f[cur], 0, sizeof(f[cur]));
for (int k = 0; k < e; ++ k)
if (f[prv][k]) {
if (!(k & pow2(j)) && (!j || !(k & pow2(j - 1))))
incm(f[cur][k | pow2(j)], f[prv][k]);
incm(f[cur][k & (~pow2(j))], f[prv][k]);
}
}
int ans(0);
for (int i = 0; i < e; ++ i)
incm(ans, f[cur][i]);
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif
pre();
scanf("%d", &amp;v);
ans = 1;
lans = 0;
memset(ldis, -1, sizeof(ldis));
ans = 1;
for (int i = 1; i &lt;= v; ++ i)
	if (i % 2 &amp;&amp; i % 3) {
		if (getDis(v / i))
			ans = _l ans * lans % mod;
		else
			ans = _l ans * (lans = dp()) % mod;
	}
printf("%d\n", ans);

}

Comments