题解 P4163 [SCOI2007]排列

强烈谴责只有 125MB 的行为，然后我没删调试是个什么 SB。。。

闲话少说，切入正题——

首先看到取余和数字是可以排列的，我们自然而然的想到了数位 dp，但是很显然这题不是的数位 dp 通常解决的是 \(1\sim k\) 之间符合要求的数这里是恰好符合的。

发现 \(s\) 长度很小，只有 \(15\)，所以考虑状压。

然后这个时候 SX 还没看出来是状压足以见得他是个瞎子了！

如果数据范围很小还是个 dp 一定要考虑状压！！！！！

如果数据范围很小还是个 dp 一定要考虑状压！！！！！

也就 SX 这种带聪明想不到状压了吧/qd

然后就很显然要记录余数，设 \(f_{i, S}\) 为选择状态为 \(S\) 余数为 \(i\) 的方案数。

如果我们要加入一个数字，首先他要不在 \(S\) 内（一直没判这个调了很长时间，所以我是压根不会状压石锤，这种弱智玩意儿都没看出来），然后转移很显然 \(f_{(10i + a_j)\bmod d, S|(1<<j)} += f_{i, S}\)。

重复数字除以它出现次数阶乘即可。

代码：

//SIXIANG

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring>

#define MAXN 1000

#define int long long

#define QWQ cout << "QWQ" << endl;

using namespace std;

int f[MAXN + 10][(1 << 10) + 10], arr[10], t[10], frac[16];

void pre() {

	frac[0] = 1;

	for(int p = 1; p <= 16; p++) frac[p] = frac[p - 1] * p;

}

signed main() {

	pre();

	int T; cin >> T;

	string str; int d;

	while(T--) {

		cin >> str >> d;

		memset(t, 0, sizeof(t));

		memset(arr, 0, sizeof(arr));

		memset(f, 0, sizeof(f));

		int i = 0;

		for(int p = 0; p < str.size(); p++)

			t[str[p] - '0']++, arr[p] = str[p] - '0';

		f[0][0] = 1;

		int len = str.size();

		for(int S = 0; S < (1 << len); S++)

			for(int p = 0; p < len; p++)

				for(int i = 0; i < d; i++)

					if(!((S >> p) & 1))

						f[(10 * i + arr[p]) % d][S | (1 << p)] += f[i][S];

		for(int p = 0; p <= 9; p++)

			f[0][(1 << len) - 1] /= frac[t[p]];

		cout << f[0][(1 << len) - 1] << endl;

	}

}

顺便提一嘴，这里面枚举 S 要放在外层循环。因为显然余数一维不可能作为阶段。

以及 500ms 确实有点卡。

巴特西

题解 P4163 [SCOI2007]排列

最新文章

热门文章