BZOJ2734 [HNOI2012]集合选数

最初感觉好多状态怎么做。

然后发现（其实是瞟了一下题解）如果把一个数分成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", &v);
	ans = 1;
	lans = 0;
	memset(ldis, -1, sizeof(ldis));
	ans = 1;
	for (int i = 1; i <= v; ++ i)
		if (i % 2 && i % 3) {
			if (getDis(v / i))
				ans = _l ans * lans % mod;
			else
				ans = _l ans * (lans = dp()) % mod;
		}
	printf("%d\n", ans);
}