AtCoderGrandContest012

• 令 \(p = [k] + q\)，则 \(p\) 的递增子序列（可以为空）的数量应为 \(c + 1\)；


• 令 \(p = q + [k]\)，则 \(p\) 的递增子序列（可以为空）的数量应为 \(c \times 2\)。

特别地，空序列的递增子序列（可以为空）的数量为 \(1\)。

令 \(N\) 加上 \(1\)，我们要求即是一个排列 \(p\) 满足递增子序列（可以为空）的数量恰好为 \(N\)。

根据上面的结论，不难想到一个按照 \(N\) 的二进制位从高到低进行递归构造的做法，\(s\) 的长度不超过 \(4 \log_2 n \approx 160\)。

#include
#include
typedef long long LL;
std::vector Solve(LL N) {
if (N == 1) return std::vector();
if (N & 1) {
auto v = Solve(N - 1);
v.insert(v.begin(), (int)v.size() + 1);
return v;
}
auto v = Solve(N / 2);
v.push_back((int)v.size() + 1);
return v;
}
int main() {
LL N;
scanf("%lld", &N);
auto Ans = Solve(N + 1);
printf("%d\n", 2 * (int)Ans.size());
for (int x : Ans) printf("%d ", x);
for (int i = 1; i <= (int)Ans.size(); ++i) printf("%d ", i);
puts("");
return 0;
}


D - Colorful Balls

我们考虑把每个球初始在的位置的下标写在这个球上，那么交换两个球的位置就可以看成交换两个球上的数。

如果两个球可以交换，那么我们在它们之间连边。显然我们只需对每个连通分量分别考虑即可。

对于一个连通分量，考虑它的任意一棵生成树，不难发现仅通过树边上的交换操作就可以到达任意排列所对应的状态。

也就是说对于一个连通分量对应回原序列的下标位置，其任意一个颜色排列均可以被达到。

所以方案数是一个每个颜色的出现次数构成的多重组合数。

朴素的实现的边数是 \(\mathcal O (N^2)\) 的，接下来的问题在于减少边数，使得连通分量的性质仍然保留。

对于每种颜色，按照重量从小到大对这种颜色的所有球排序，记颜色为 \(c\) 的所有球中重量最小的为 \(\min[c]\)。

那么对于同种颜色球之间的连边 \(u \leftrightarrow v\)，如果没有经过 \(\min[c]\)，则转化为 \(u \leftrightarrow \min[c] \leftrightarrow v\) 绝不会更劣。

也就是对于每种颜色 \(c\)，每个非 \(\min[c]\) 的球尝试向 \(\min[c]\) 连边即可。

对于非同种颜色的球之间的连边，令 \(k\) 为 \(\min[c]\) 的重量最小的颜色 \(c\)：

则如果两非颜色 \(k\) 的球 \(u, v\) 之间连边，转化为 \(u \leftrightarrow \min[k] \leftrightarrow v\) 绝不会更劣。

而如果 \(u, v\) 之一的颜色为 \(k\)，令 \(k'\) 为 \(\min[c]\) 的重量次小的颜色 \(c\)：

• 如果 \(u, v\) 的颜色均不为 \(k'\)，转化为 \(u \leftrightarrow \min[k'] \leftrightarrow v\) 绝不会更劣。


• 如果 \(u, v\) 中其一颜色为 \(k\)，另一颜色为 \(k'\)，不妨设 \(u\) 的颜色为 \(k\)，转化为 \(u \leftrightarrow \min[k'] \leftrightarrow \min[k] \leftrightarrow v\) 绝不会更劣。

于是，我们仅需处理出 \(k\) 和 \(k'\)，然后将每个与 \(k\) 或 \(k'\) 不同颜色的球向 \(\min[k]\) 或 \(\min[k']\) 连边即可。

总边数控制在 \(\mathcal O (N)\)，然后运行 DFS 找出这张图的每个连通分量，计算多重组合数贡献给答案即可。

#include
#include
#include
typedef long long LL;
const int Mod = 1000000007;
const int MN = 200005;
inline int qPow(int b, int e) {
int a = 1;
for (; e; e >>= 1, b = (LL)b * b % Mod)
if (e & 1) a = (LL)a * b % Mod;
return a;
}
int Fac[MN], iFac[MN];
inline void Init(int N) {
Fac[0] = 1;
for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
iFac[N] = qPow(Fac[N], Mod - 2);
for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
}
int N, X, Y, p1, p2, C;
std::vector V[MN], G[MN];
int index[MN], col[MN];
inline void Ins(int x, int y) {
G[x].push_back(y);
G[y].push_back(x);
}
int vis[MN], buk[MN], stk[MN], tp;
void DFS(int u) {
vis[u] = 1, ++buk[col[u]], stk[++tp] = u;
for (int v : G[u]) if (!vis[v]) DFS(v);
}
int main() {
scanf("%d%d%d", &N, &X, &Y);
Init(N);
for (int i = 1, x, y; i <= N; ++i) {
scanf("%d%d", &x, &y);
V[x].push_back(y);
}
for (int i = 1; i <= N; ++i) if (!V[i].empty()) {
std::sort(V[i].begin(), V[i].end());
if (!p1) p1 = i;
else {
if (!p2 || V[p2][0] > V[i][0]) p2 = i;
if (V[p1][0] > V[p2][0]) std::swap(p1, p2);
}
int s = V[i].size();
index[i] = C += s;
for (int j = 0; j }
for (int i = 1; i <= N; ++i) if (!V[i].empty()) {
int s = V[i].size(), c = index[i];
for (int j = 1; j if (p1 && i != p1)
for (int j = 0; j if (p2 && i == p1)
for (int j = 1; j }
int Ans = 1;
for (int i = 1; i <= N; ++i) if (!vis[i]) {
DFS(i);
int s = 0;
for (int x = 0; tp; --tp) if (buk[x = col[stk[tp]]])
s += buk[x], Ans = (LL)Ans * iFac[buk[x]] % Mod, buk[x] = 0;
Ans = (LL)Ans * Fac[s] % Mod;
}
printf("%d\n", Ans);
return 0;
}