的分界线分别为,
对于下一层的纵坐标
称满足上述条件为合法情况，不满足上述条件为不合法情况。
设恰好有层不合法的方案数为，设恰好有i层合法的方案数为。
考虑容斥求，钦定最后层（即到层）不合法，前层合法。（容斥部分感谢ywx的讲解和点化）
那么从钦定最后层不合法和前层合法开始，当前情况数为，此时只钦定了前层和最后层，第层和第层之间的关系并未确定，可能第层和第层仍然构成不合法情况，那么就要把这种情况减去，也就是减掉，同理仍然有第层和第层可能构成不合法情况，但被减去了，所以要加上，一步步下去，可得如下式子
合并后可得
所以对应的生成函数和对应的生成函数之间的关系为 接下来考虑如何求
连续层不合法，那么会使得
设，那么需要相隔至少个数之后才能选，那么可以每选择一个数使得减，即线性变换，因此考虑矩阵
设为输入的个权值
时不需要偏移，所以矩阵为
时偏移为格
时偏移为格
以时的矩阵为例进行解释，之后能选的数是，那么i移动就只能从第三列移动到一列之后才能加，在移动两格的过程中，就没有被选在之后，而选择之后又需要停两次才能选，若不选则仍然停留在立即能选的状态，所以该矩阵的转移就是
写出来就是的矩阵
最后带回原式做一个多项式求逆即可
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
| struct matrix
{
poly a[4][4];
static constexpr int n = 3;
friend matrix operator*(const matrix &u, const matrix &v)
{
matrix ans;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
ans.a[i][j] = ans.a[i][j] + u.a[i][k] * v.a[k][j];
return ans;
}
poly *operator[](const int i)
{
return this->a[i];
}
} s[N];
matrix solve(int l, int r)
{
if (l == r)return s[l];
int m = (l + r) >> 1;
return solve(l, m) * solve(m + 1, r);
}
int main()
{
int p, q, u, v, w, x, y, z, T;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
scanf("%d", &w);
if (i < 16)
s[i][1][1] = poly{1, w};
else if (i < 65536)
s[i][1][1] = s[i][2][1] = poly{1}, s[i][1][2] = poly{0, w};
else
s[i][1][1] = s[i][2][1] = s[i][3][2] = poly{1}, s[i][1][3] = poly{0, w};
}
matrix A = solve(1, m);
poly F = A[1][1] + A[1][2] + A[1][3];
for (int i = 1; i < F.size(); i += 2)
F[i] = mod - F[i];
cout << F.inv(n + 1)[n] << endl;
return 0;
}
|