如果一个排列 \(P\)
满足对于所有的i都有 \(|p_i-i|\ne
k\)，则称排列P为合法的，求合法排列数
考虑错排问题就是 \(k\ = 0\)
的特殊情况，这道题用同样做法来做，设 \(f_i\) 为恰好有 \(i\) 个满足 \(|p_i-i|\ne k\) 的方案数，\(g_i\) 为至少有 \(i\) 个满足 \(|p_i-i|\ne k\) 的方案数，则有
\[
g_i\ =\ \sum_{i\le j}f_j
\] 根据广义容斥
\[
f_i\ =\ \sum_{i\le j}(-1)^{j-i}g_j
\]
考虑如何求出 \(g_i\)，我们利用下标和键值的关系不难看出这是一个二分图匹配问题，那么问题就转化为在一个二分图中选出
\(i\)
条匹配边的方案数，注意到每个点的度数不超过 \(2\)，我们可以把这些链抽出来并在一起，不妨设
\(h_{i,j,k}\) 表示前 \(i\) 个点选出 \(j\) 条匹配边，第 \(i\) 个点与前一个点连边状态为 \(k\)
时的的方案数，转移很简单，不多赘述，最后答案即为 \(g_i\ =\ (h_{2n,i,0}+h_{2n,i,1})(n-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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 4e3+5, P = 924844033;
int n, m;
int cut[N], h[N][N][2], g[N], f[N], fac[N];
int main()
{
n = read(), m = read(); fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = 1ll*fac[i-1]*i%P;
for(int i = 1, p = 1; i <= m; ++i)
{
cut[p] = 1; p += (n-i)/m+1;
cut[p] = 1; p += (n-i)/m+1;
}
for(int i = 0; i <= n<<1; ++i) h[i][0][0] = 1;
for(int i = 1; i <= n<<1; ++i)
for(int j = 1; j <= n; ++j)
{
h[i][j][0] = (h[i-1][j][0]+h[i-1][j][1])%P;
if(!cut[i]) h[i][j][1] = h[i-1][j-1][0];
}
for(int i = 0; i <= n; ++i) g[i] = 1ll*(h[n<<1][i][0]+h[n<<1][i][1])*fac[n-i]%P;
for(int i = 0, w = 1; i <= n; ++i, w = P-w) f[0] = (f[0]+1ll*w*g[i]%P)%P;
printf("%d\n", f[0]);
return 0;
}
|
给定两棵树和起点，两人分别在两棵树上交替移动，相遇后游戏结束，现在
\(A\) 想最大化游戏轮数，\(B\) 想最小化游戏轮数，求游戏轮数
很明显，最终如果游戏不能无限进行则 \(A\) 会最终不移动，那么问题关键就是求出
\(A\)
能移动到点集，我们发现有个很明显的充分条件是起点到这些点的经过点到 \(A\) 的距离小于 \(B\)
到这些点的距离，通过搜索判断可达性即可
如果游戏可以无限进行，则 \(A\)
一定可以达到一条边 \((u,\ v)\) 满足在
\(B\) 上 \(d_{u,v}>2\)，达到这条边后左右跳即可
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 2e5+5;
struct Edge
{
int next, to;
Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N<<2];
int ha[N], hb[N], tot;
void _add(int *h, int x, int y) { edge[++tot] = Edge(h[x], y); h[x] = tot; }
void add(int *h, int x, int y) { _add(h, x, y); _add(h, y, x); }
int fa[N], son[N], size[N], top[N], d[N];
int ans, cir;
void dfs(int x)
{
size[x] = 1;
for(int i = hb[x]; i; i = edge[i].next)
{
int y = edge[i].to; if(y == fa[x]) continue;
d[y] = d[x]+1, fa[y] = x, dfs(y),
size[x] += size[y], son[x] = size[son[x]]>size[y]?son[x]:y;
}
}
int lca(int x, int y)
{
while(top[x] != top[y])
{
if(d[top[x]] < d[top[y]]) swap(x, y);
x = fa[top[x]];
}
return d[x]<d[y]?x:y;
}
int dis(int x, int y) { return d[x]+d[y]-2*d[lca(x, y)]; }
void dfs(int x, int topf)
{
top[x] = topf; if(son[x]) dfs(son[x], topf);
for(int i = hb[x]; i; i = edge[i].next)
{
int y = edge[i].to;
if(y != fa[x]&&y != son[x]) dfs(y, y);
}
}
void escape(int x, int fa, int dep)
{
ans = max(ans, d[x]<<1);
for(int i = ha[x]; i; i = edge[i].next)
{
int y = edge[i].to;
if(dis(x, y) > 2) cir = 1;
if(y == fa||dep+1 >= d[y]) continue;
escape(y, x, dep+1);
}
}
int n, a, b;
int main()
{
n = read(), a = read(), b = read();
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
add(ha, x, y);
}
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
add(hb, x, y);
}
dfs(b); dfs(b, b); escape(a, 0, 0);
printf("%d\n", cir?-1:ans);
return 0;
}
|
给定一棵无根树，定义 \(f(i)\)，对于所有大小为 \(i\)
的点集，求出能够包含它的最小连通块大小之和。对于 \(i=1 \to n\) 的所有 \(i\)，求出 \(f(i)\)
想这道题的过程收获挺多的，首先这道题问的点集，按照套路就是思考每个点对于
\(f(i)\)
的贡献，但没想出来，所以看到联通块，又想到 \(dfs\)
序与联通块的联系，得到一个的做法，简单来说就是枚举每个点对，考虑点对在
\(dfs\)
序的子序列的位置用组合数算下贡献就好了，这个思路想到 \(O(n^3)\) 就想不下去了
再考虑每个点的贡献，其实很好算，设 \(s_i\) 为定根后节点 \(i\) 的子树大小，考虑节点 \(i\) 会被多少个点集算到，得到
\[
f(k)\ =\ \sum_{i=1}^n\binom{n}{k}-\binom{n-s_i}{k}-\sum_{j\in
son_i}\binom{s_j}{k}
\]
化简得到
\[
f(k)\ =\ n\binom{n}{k}-\sum_{i=2}^n\binom{n-s_i}{k}+\binom{s_i}{k}
\]
主要问题是求出后面的式子，设它的生成函数为 \(h\) 则有
\[
h\ =\ \sum_{k}\sum_{i=2}^n[\binom{n-s_i}{k}+\binom{s_i}{k}]x^k
\]
这时候我就被降智了，考虑交换求和序，有
\[
\begin{aligned}
h\ &=\ \sum_{i=2}^n\sum_{k}\binom{n-s_i}{k}x^k+\binom{s_i}{k}x^k\\\\
&=\ \sum_{i=2}^n(1+x)^{s_i}+(1+x)^{n-s_i}
\end{aligned}
\]
开一个桶 \(c\)
记录一下相同的指数，则
\[
h\ =\ \sum_{i=0}^nc_i(1+x)^i
\]
这不就是一个裸的多项式复合函数吗，结果一看多项式复合函数的复杂度，溜了，溜了
接着我发现这就是多项式的平移吗，那就求值完平移再插回去就好了呀，学了半天求值和插值，一发交上去只拿了暴力分
稍微优化一下，改用原根求值，最后直接 \(INTT\) 即可，还是只拿了暴力分
翻了具体数学提高知识水平，发现下降幂可做，但求下降幂又要多点求值自闭
最后重新看这个式子，好像就是一个裸的卷积
\[
\begin{aligned}
h\ &=\ \sum_{k}\sum_{i=0}^nc_i\binom{i}{k}x^k\\\\
&=\ \sum_{k}\frac{1}{k!}\sum_{i=0}^n(c_i\times
i!)(\frac{1}{(i-k)!})x^k
\end{aligned}
\]
后面稍微转置一下就是卷积了
同时，我们惊喜地发现多项式线性变换同样是一个简单的卷积
常数巨大的 \(AC\) 代码
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 2e5+5, P = 924844033;
struct Edge
{
int next, to;
Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N<<1];
int tot, head[N];
void _add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; }
void add(int x, int y) { _add(x, y), _add(y, x); }
int n, s[N];
void dfs(int x, int fa)
{
s[x] = 1;
for(int i = head[x]; i; i = edge[i].next)
{
int y = edge[i].to; if(y == fa) continue;
dfs(y, x); s[x] += s[y];
}
}
int64 qpow(int64 a, int b)
{
int64 ret = 1;
for( ; b; b >>= 1, a = a*a%P) if(b&1) ret = a*ret%P;
return ret;
}
int64 fac[N], inv[N<<2], ifac[N];
int64 C(int n, int m) { return n < m?0:fac[n]*ifac[m]%P*ifac[n-m]%P; }
struct Poly
{
vector<int> _;
inline int& operator [] (int i) { return _[i]; }
inline int ti() { return _.size()-1; }
inline void set(int ti) { _.resize(ti+1); }
inline void rev() { reverse(_.begin(), _.end()); }
};
int lim;
int64 w[2][N<<2];
void prepare(int ti)
{
for(lim = 1; lim <= ti; lim <<= 1);
w[0][0] = w[1][0] = w[0][lim] = w[1][lim] = 1;
int64 g = qpow(5, (P-1)/lim);
for(int i = 1; i < lim; ++i) w[1][lim-i] = w[0][i] = w[0][i-1]*g%P;
}
void NTT(Poly &A, int t)
{
if(!t) A.set(lim-1);
for(int i = 0, j = 0; i < lim; ++i)
{
if(i > j) A[i] ^= A[j] ^= A[i] ^= A[j];
for(int k = lim>>1; (j ^= k) < k; k >>= 1);
}
for(int mid = 1; mid < lim; mid <<= 1)
for(int len = mid<<1, j = 0; j < lim; j += len)
for(int k = 0, p = 0, q = lim/len; k < mid; ++k, p += q)
{
int64 x = A[j+k], y = w[t][p]*A[j+k+mid]%P;
A[j+k] = x+y<P?x+y:x+y-P;
A[j+k+mid] = x-y<0?x-y+P:x-y;
}
if(!t) return; int64 v = inv[lim];
for(int i = 0; i < lim; ++i) A[i] = A[i]*v%P;
}
Poly operator * (Poly A, Poly B)
{
int n = A.ti(), m = B.ti();
if(n <= 128||m <= 128)
{
Poly C; C.set(n+m);
int *c = &C[0], *a = &A[0], *b = &B[0];
for(int i = 0; i <= n; ++i)
{
int *f = c+i; int64 x = a[i];
for(int j = 0; j <= m; ++j) f[j] = (f[j]+x*b[j]%P)%P;
}
return C;
}
prepare(n+m), NTT(A, 0), NTT(B, 0);
for(int i = 0; i < lim; ++i) A[i] = 1ll*A[i]*B[i]%P;
NTT(A, 1); A.set(n+m);
return A;
}
Poly F, G;
int px[N<<1], py[N<<1];
int main()
{
for(int i = 1; i <= N<<2; i <<= 1) inv[i] = qpow(i, P-2);
n = read(), fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
add(x, y);
}
dfs(1, 0); F.set(n), G.set(n);
for(int i = 2; i <= n; ++i)
{
inv[i] = (P-P/i)*inv[P%i]%P,
fac[i] = i*fac[i-1]%P,
ifac[i] = inv[i]*ifac[i-1]%P;
++F[s[i]], ++F[n-s[i]];
}
for(int i = 0; i <= n; ++i) F[i] = F[i]*fac[i]%P, G[i] = ifac[i]%P;
F.rev(), F = F*G, F.set(n), F.rev();
for(int i = 1; i <= n; ++i) printf("%lld\n", (n*C(n, i)%P-F[i]*ifac[i]%P+P)%P);
return 0;
}
|