「HAOI2016」放棋子
这题，一看就很状压\(dp\) 但是\(N\leq 200\)，拿啥压啊...
不会做啊，忍不住去搜题解了。
题目有个很好的性质
任意两个障碍不在同一行，任意两个障碍不在同一列......你放\(N\)个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制
首先，既然每行每列都只有一个障碍，那么显然障碍放哪里对棋子方案数没有影响。
你想在某行换一个障碍位置，那么必定会把另一个障碍换到这一列。这就相当于换了某两行。
因为棋子也满足这个限制，所以换两行是没有影响的。
所以我们直接钦定第\(i\)行的障碍物就在第\(i\)列，因为要放\(N\)个棋子，每一行都要放一个，给放在\(i\)行的棋子编号为\(i\)。
所以编号为\(i\)的棋子不能放在第\(i\)列。
而每一列都有一个棋子，把每列的棋子依次拿出来，编号就对应了一个排列。
根据前面所述，这个排列被称为错排。
即第\(i\)个元素不在第\(i\)位的排列数。
令\(f[i]\)表示\(i\)个元素的错排方法，那么\(f[i]=(i-1)\times (f[i-1]+f[i-2])\)
而\(f[0]=1,f[1]=0\)
什么意思呢？
先假设现在有\(n\)个元素，第\(n\)个元素选择第\(k\)个位置放置，有\(n-1\)种方法。
讨论\(k\)的放法
- \(k\)放在第\(n\)位，即对其他元素没有影响，\(n-2\)个元素错排即可
- \(k\)不放在第\(n\)位，相当于\(k\)就是\(n\)，相当于\(n-1\)个元素错排
所以说，写一个高精乘法和高精加法即可。
由于博主比较垃圾，不会高精乘低精，所以把低精转成了高精来算的......
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n;
const int power = 4, base = 10000;
struct num {
int len, a[520];
num() {
len = 0;
memset(a, 0, sizeof a);
}
void write() {
printf("%d", a[len]);
for (int i = len - 1; i; i--) printf("%0*d", power, a[i]);
putchar('\n');
}
} f[N];
num operator + (const num &p, const num &q) {
num c;
c.len = max(p.len, q.len);
for (int i = 1; i <= c.len; i++) {
c.a[i] += p.a[i] + q.a[i];
c.a[i + 1] += c.a[i] / base;
c.a[i] %= base;
}
while (c.a[c.len + 1]) c.len++;
return c;
}
num rev(int x) {
num t;
t.a[1] = x;
t.len = 1;
return t;
}
num operator * (const num &p, const num &q) {
num c;
c.len = p.len + q.len - 1;
for (int i = 1; i <= p.len; i++)
for (int j = 1; j <= q.len; j++) {
c.a[i + j - 1] += p.a[i] * q.a[j];
c.a[i + j] += c.a[i + j - 1] / base;
c.a[i + j - 1] %= base;
}
while (c.a[c.len + 1]) c.len++;
return c;
}
int main() {
scanf("%d", &n);
f[0].a[1] = 1;
f[0].len = 1;
f[1].len = 1;
for (int i = 2; i <= n; i++) f[i] = rev(i - 1) * (f[i - 1] + f[i - 2]);
f[n].write();
return 0;
}
|