• 欢迎光临~

题解 P4163 [SCOI2007]排列

开发技术 开发技术 2022-08-02 次浏览

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

闲话少说,切入正题——


首先看到取余和数字是可以排列的,我们自然而然的想到了数位 dp,但是很显然这题不是的数位 dp 通常解决的是 (1sim 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]排列
喜欢 (0)