AtCoder Petrozavodsk Contest 001 简要题解

A：

答案是 a a 或者−1−1。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif int x, y; Read(x), Read(y); printf("%d\n", x % y ? x : -1); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

B：

可以求出操作总次数，以及对于 A A 和BB变得相等的最小次数，比较一下。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 10005; int n, a[N], b[N]; LL sum_a, sum_b; int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n); for (int i = 1; i <= n; ++i) { Read(a[i]), sum_a += a[i]; } for (int i = 1; i <= n; ++i) { Read(b[i]), sum_b += b[i]; } if (sum_a > sum_b) { puts("No"); } else { LL t = sum_b - sum_a, x = 0, y = 0; for (int i = 1; i <= n; ++i) { if (a[i] >= b[i]) { y += a[i] - b[i]; } else { x += b[i] - a[i] + 1 >> 1; y += b[i] - a[i] & 1; } } puts(x <= t && y <= t ? "Yes" : "No"); } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

C：

二分答案，根据奇偶性判断。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } inline int Query(int x) { char s[10]; printf("%d\n", x); fflush(stdout); scanf("%s", s); return s[0] == 'V' ? -1 : s[0] == 'F'; } int main() { #ifdef wxh010910 #endif int n, l, r, u, v; Read(n), l = 0, r = n, u = v = Query(0); if (~u) { while (true) { int m = l + r >> 1, t = Query(m); if (!~t) { break; } else if ((m ^ l ^ u ^ t) & 1) { r = m, v = t; } else { l = m, u = t; } } } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

D：

贪心。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 100005; int n, m, a[N], f[N], p[N]; priority_queue <pii> q; vector <int> v[N]; LL ans; inline int F(int x) { while (x != f[x]) { x = f[x] = f[f[x]]; } return x; } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), Read(m); for (int i = 0; i < n; ++i) { Read(a[i]), f[i] = i; } for (int i = 0, x, y; i < m; ++i) { Read(x), Read(y); f[F(x)] = F(y); } int c = 0; for (int i = 0; i < n; ++i) { if (F(i) == i) { ++c; } v[F(i)].pb(i); } if (2 * (c - 1) > n) { puts("Impossible"); } else if (c == 1) { puts("0"); } else { a[n] = 1 << 30; for (int i = 0; i < n; ++i) { if (F(i) == i) { sort(v[i].begin(), v[i].end(), [&](const int &x, const int &y) { return a[x] < a[y]; }); v[i].pb(n), p[i] = 1, ans += a[v[i][0]], q.push(mp(-a[v[i][1]], i)); } } for (c -= 2; c; --c) { pii x = q.top(); q.pop(), ans -= x.X, ++p[x.Y], q.push(mp(-a[v[x.Y][p[x.Y]]], x.Y)); } printf("%lld\n", ans); } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

E：

识别两个点需要在一个距离它们不同的位置设置一个关键点。

就是说删去一个点如果形成了 K K 个连通块，那么其中至多一个连通块没有关键点。

树形DP一下。

#include <bits/stdc .h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 100005; vector <int> adj[N]; int n, r; inline int DFS(int x, int p) { int r = 0, c = 0; for (auto y : adj[x]) { if (y != p) { int v = DFS(y, x); r = v, c = !v; } } return r max(c - 1, 0); } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n); for (int i = 1, x, y; i < n; i) { Read(x), Read(y); adj[x].pb(y), adj[y].pb(x); } for (; r < n && adj[r].size() <= 2; r); if (r == n) { puts("1"); } else { printf("%d\n", DFS(r, -1)); } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

F：

令点权为边权的异或，那么达到最终状态当且仅当所有点权都为00。

一次修改实际只修改了两个点的点权，构造一个 N N 个点的新图，如果进行过一次操作就连一条边，那么最后的每个连通块异或都为00。

类似CERC 2017 K题，贪心匹配，接下来进行一个状压DP即可。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 100005; int n, m, ans, a[N], b[N], c[N], f[N]; int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n); for (int i = 1, x, y, w; i < n; ++i) { Read(x), Read(y), Read(w); a[x] ^= w, a[y] ^= w; } for (int i = 0; i < n; ++i) { ++c[a[i]]; } for (int i = 1; i < 16; ++i) { ans += c[i] >> 1; if (c[i] & 1) { b[m++] = i; } } for (int i = 1; i < 1 << m; ++i) { int s = 0; for (int j = 0; j < m; ++j) { if (i >> j & 1) { s ^= b[j]; } } if (s) { f[i] = m; } else { f[i] = __builtin_popcount(i) - 1; } for (int j = s = i; j; j = j - 1 & s) { CheckMin(f[i], f[j] + f[i ^ j]); } } printf("%d\n", ans + f[(1 << m) - 1]); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

G:

首先连接开头和结尾，认为他们是一段间隔，那么间隔的前驱和后继是固定的，形成了若干个环。

分类讨论一下：

全部覆盖的情况。

N N 是偶数，构造 1,2,1,2,...,2N−1,2N,2N−1,2N1,2,1,2,...,2N−1,2N,2N−1,2N 。

N N 是奇数，无解。N=1N=1 的时候有两个环，而 N N 每次增加一都会导致环个数奇偶性改变。

没有全部覆盖的情况，将 1,11,1 之间的点称作 internal ， 0,0 0 , 0 之间的点称作 external ，其他的叫做 boundary ，将所有极长的连续 1 1 记下来， 记 sumsum 表示 internal 的点个数。

sum s u m 是奇数，无解。因为 internal 必须配对。 sum s u m 是 4 4 的倍数，将一段和另一段的拼起来可以变成全部覆盖， NN 是偶数的情况。只有一段的 internal 个数不为 0 0 ，其他段必须合并，可以转化成全部覆盖， NN 是奇数的情况，无解。否则可以合并两段 internal 个数不为 0 0 的，让 sumsum 减去 2 2 ：比如第一段 1→2→31→2→3 ， 第二段 4→5→6 4 → 5 → 6 ，那么将 2 2 和 55 标同一个号，将它们合并起来即可。 （可以参考原题解的图） #include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 200005; vector <int> a, b, c, d; int n, m, cur, ans[N]; char s[N]; inline int Erase(vector <int> &v, int x) { int p = lower_bound(v.begin(), v.end(), x) - v.begin(); for (int i = p; i < v.size() - 1; ++i) { v[i] = v[i + 1]; } v.pop_back(); } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), scanf("%s", s + 1), s[0] = s[n << 1] = '1'; for (int i = 0; i < n << 1; ++i) { if (s[i] == '0' && s[i + 1] == '0') { a.pb(i); } else if (s[i] == '0' && s[i + 1] == '1') { b.pb(i); } else if (s[i] == '1' && s[i + 1] == '0') { c.pb(i); } else { d.pb(i); } } m = d.size(); if (m & 1) { puts("No"); } else { if (m & 3) { int p, q, r; for (p = 0; p <= n << 1 && s[p] == '1'; ++p); if (p > n << 1) { puts("No"); return 0; } while (true) { for (; p < n << 1 && s[p + 1] == '0'; ++p); if (p >= n << 1) { puts("No"); return 0; } if (p + 2 <= n << 1 && s[p + 2] == '1') { break; } else { p += 2; } } for (q = p + 1; q <= n << 1 && s[q] == '1'; ++q); if (q > n << 1) { puts("No"); return 0; } for (r = 0; r < m && d[r] > p && d[r] < q - 1; ++r); if (r == m) { puts("No"); return 0; } if (d[r] <= p) { for (; r + 1 < m && d[r + 1] < p; ++r); } int x = p, y = q - 1, z = p + 1, w = d[r]; ans[x] = ans[y] = ++cur, Erase(b, x), Erase(c, y); ans[z] = ans[w] = ++cur, Erase(d, z), Erase(d, w); } for (int i = 0; i < b.size(); ++i) { ans[b[i]] = ans[c[i]] = ++cur; } for (int i = 0; i < a.size(); i += 2) { ans[a[i]] = ans[a[i + 1]] = ++cur; } for (int i = 0; i < d.size(); i += 4) { ans[d[i]] = ans[d[i + 2]] = ++cur; ans[d[i + 1]] = ans[d[i + 3]] = ++cur; } puts("Yes"); for (int i = 0; i < n << 1; ++i) { printf("%d%c", ans[i], i == (n << 1) - 1 ? '\n' : ' '); } } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

H：

对于一棵有根树，定义红点是叶子或者只有一个儿子且儿子是红点的点，每次让红点的值变成正确的，之后去掉红点变成子问题。

可以证明红点只有 O(log) O ( log ) 层：考虑对树进行轻重链剖分，每次去掉最下面一层重链，所以只有 O(log) O ( log ) 层。

考虑链的情况怎么做：类似插入排序，每次把根的东西丢到后面已排好序的链里面，操作次数 O(n) O ( n ) 。

在树上，如果根的权值始终是红点的权值，那么和链的做法一样。

考虑根节点权值不是红点权值怎么办， 那么就得把它丢到一个“垃圾桶“里面，将其他东西顶上来。

问题就是放垃圾的位置，那么就只需要把垃圾放在一个深度最深的未排序的地方，而且需要祖先上面有红点权值，一个比较好的办法是均摊掉，尽量让每个节点只被丢一次。

但这个做法还是有问题的，因为可能会把垃圾顶到某个祖先位置，从另外一边的链顶到根，但是发现每个红点只会被放一次，所以均摊下来是 n n 加上红点个数的，就可以过了。

#include <bits/stdc .h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 2005; int n, cnt, a[N], d[N], e[N], p[N], r[N]; vector <int> ans, seq, adj[N]; bool v[N]; inline void Rotate(int x) { int t = a[x]; ans.pb(x), a[x] = a[0]; for (int i = p[x]; ~i; swap(a[i], t), i = p[i]); } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(n), p[0] = -1; for (int i = 1; i < n; i) { Read(p[i]), adj[p[i]].pb(i), d[i] = d[p[i]] 1; } for (int i = 0; i < n; i) { Read(a[i]); } while (cnt < n) { seq.clear(); for (int i = n - 1; ~i; --i) { if (!v[i]) { int t = 0, son = -1; seq.pb(i); for (auto j : adj[i]) { if (!v[j]) { t, son = j; } } if (!t) { r[i] = e[i] = i; } else if (t == 1 && ~r[son]) { r[i] = r[son]; } else { r[i] = -1; } } } sort(seq.begin(), seq.end(), [&](const int &x, const int &y) { return mp(r[x], d[x]) > mp(r[y], d[y]); }); for (int i = 0; i < seq.size(); ) { if (~r[a[0]]) { int x = a[0], y = r[x]; for (; v[y] && a[y] > x; y = p[y]); Rotate(y), y = r[x], v[e[y]] = true, e[y] = p[e[y]], cnt; } else { Rotate(seq[i ]); } for (; i < seq.size() && v[seq[i]]; i); } } for (int i = 0; i < n; i) { assert(a[i] == i); } printf("%d\n", ans.size()); for (auto x : ans) { printf("%d\n", x); } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

I：

考虑两个空白行 ii 和 i+1 i + 1 ，第 1⋯i 1 ⋯ i 行为一部分，另外的行为另一部分，那么注意到同一部分的最短路不会跨过第 i i 行和第 i 1i 1 行，而不同部分的一定跨过一次，那么算完贡献之后就可以把这两行缩起来，认为它们之间边权为 0 0 。

列同理，图被缩成了 O(n)×O(n)O(n)×O(n) 的，接下来跑一个简单的 BFS 就好了。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 65; const int M = 1000005; const int mod = 1e9 + 7; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; int n, r, c, ans, x[N], y[N], cnt_x[M], cnt_y[M], idx_x[M], idx_y[M], siz_x[M], siz_y[M], dis[N][N]; bool vis[N][N]; queue <pii> q; inline void Solve(int *cnt, int *idx, int *siz, int r, int c) { int u = c - cnt[0], d = (1LL * r * c - n - u) % mod; siz[0] = 1; for (int i = 1; i < r; ++i) { idx[i] = idx[i - 1]; if (!cnt[i] && !cnt[i - 1]) { ans = (2LL * u * d + ans) % mod; } else { ++idx[i]; } ++siz[idx[i]]; u = (u + c - cnt[i]) % mod, d = (d + cnt[i] - c + mod) % mod; } } inline int Siz(int x, int y) { return 1LL * siz_x[x] * siz_y[y] % mod; } inline void BFS(int s_x, int s_y) { for (int i = 0; i <= idx_x[r - 1]; ++i) { for (int j = 0; j <= idx_y[c - 1]; ++j) { dis[i][j] = -1; } } dis[s_x][s_y] = 0, q.push(mp(s_x, s_y)); while (!q.empty()) { int x = q.front().X, y = q.front().Y; q.pop(), ans = (1LL * Siz(x, y) * Siz(s_x, s_y) % mod * dis[x][y] + ans) % mod; for (int i = 0; i < 4; ++i) { int u = x + dx[i], v = y + dy[i]; if (u >= 0 && u <= idx_x[r - 1] && v >= 0 && v <= idx_y[c - 1] && !vis[u][v] && !~dis[u][v]) { dis[u][v] = dis[x][y] + 1, q.push(mp(u, v)); } } } } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif Read(r), Read(c), Read(n); for (int i = 0; i < n; ++i) { Read(x[i]), Read(y[i]); ++cnt_x[x[i]], ++cnt_y[y[i]]; } Solve(cnt_x, idx_x, siz_x, r, c); Solve(cnt_y, idx_y, siz_y, c, r); for (int i = 0; i < n; ++i) { vis[idx_x[x[i]]][idx_y[y[i]]] = true; } for (int i = 0; i <= idx_x[r - 1]; ++i) { for (int j = 0; j <= idx_y[c - 1]; ++j) { if (!vis[i][j]) { BFS(i, j); } } } printf("%d\n", 1LL * ans * (mod + 1) / 2 % mod); #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }

J：

首先默认 Amoda=Bmodb=Cmodc=0 A mod a = B mod b = C mod c = 0 。

一维的情况答案就是 a a ， 二维的情况可以发现一定横向对齐或者纵向对齐，容斥一下就好了。

三维的情况也可以通过容斥求出存在某一维对齐的情况，接下来考虑没有任何一维对齐的情况。

对于长方体的一个角 (p,q,r)(p,q,r) ，在 (p+imodA,q+jmodB,r+kmodC) ( p + i mod A , q + j mod B , r + k mod C ) 上填上数 k k ， 记 v(x,y,z)v(x,y,z) 表示 (x,y,z) ( x , y , z ) 这个位置填的数，不难发现 v(x,y,0),v(x,y,1),⋯,v(x,y,C−1) v ( x , y , 0 ) , v ( x , y , 1 ) , ⋯ , v ( x , y , C − 1 ) 是 0,1,2,⋯,c−1,0,1,2,⋯,c−1⋯ 0 , 1 , 2 , ⋯ , c − 1 , 0 , 1 , 2 , ⋯ , c − 1 ⋯ 的一个循环同构串。

记 v(x,y)=v(x,y,0) v ( x , y ) = v ( x , y , 0 ) ，考虑有多少 z=i z = i 的时候每一层有多少种划分，记为 f(i) f ( i ) ， 那么答案就是 ∏c−1i=0f(i)C/c ∏ i = 0 c − 1 f ( i ) C / c 。注意这里每一层的划分只需要划分 v(x,y,i)=0 v ( x , y , i ) = 0 的部分，其他根据之前层确定好的来。

对于一个给定的 layer （即 z z 为一个定值 ii 的平面），定义它是 row-aligned 的当且仅当每行的 v(x,y,i) v ( x , y , i ) 都相等，column-aligned 同理，那么如果它是 row-aligned 或者 column-aligned 的，那它一定会某一维对齐，这种情况不再考虑。

直接考虑划分这一层，这里不再有 0 0 的限制，只要求同一个矩形内数都相等，那么如果所有方法不存在横向对齐或者纵向对齐的，那么总的划分也是对齐的，所以对于每一层的划分方法一定存在一种横纵向都对齐的。注意到它并不是 row-aligned 或者 column-aligned 的，所以这种划分方法唯一，定义这种划分是 standard-partition 。

为了没有任何一维对齐，那么一定存在两个 v(x,y,z)v(x,y,z) 相同的 z z ，满足它的某一部分被横向shift了一遍，纵向同理，就是说存在某个 hh 支配了某些行和列（参见题解的第二张图）。

直接考虑 standard-partition ，可以认为这个 layer 就是 Aa×Bb A a × B b ，假设 h h 支配了恰好 pp 行， q q 列， 不难用容斥算出存在行、列被shift的情况数是 (bp aq−1)C/c−(bp)C/c−(aq)C/c 1(bp aq−1)C/c−(bp)C/c−(aq)C/c 1。

算 (p,q) ( p , q ) 的方案数，是个简单容斥，就不细说了。

#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back #define Debug(...) fprintf(stderr, __VA_ARGS__) typedef long long LL; typedef long double LD; typedef unsigned int uint; typedef pair <int, int> pii; typedef unsigned long long uLL; template <typename T> inline void Read(T &x) { char c = getchar(); bool f = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { f = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (f) { x = -x; } } template <typename T> inline bool CheckMax(T &a, const T &b) { return a < b ? a = b, true : false; } template <typename T> inline bool CheckMin(T &a, const T &b) { return a > b ? a = b, true : false; } const int N = 105; const int mod = 1e9 + 7; inline int Qow(int x, int y) { int r = 1; for (; y; y >>= 1, x = 1LL * x * x % mod) { if (y & 1) { r = 1LL * r * x % mod; } } return r; } inline int Solve(int a, int A) { return a; } inline int Solve(int a, int A, int b, int B) { int ans = 0; ans = (1LL * b * Qow(Solve(a, A), B / b) + ans) % mod; ans = (1LL * a * Qow(Solve(b, B), A / a) + ans) % mod; ans = (ans - a * b + mod) % mod; return ans; } inline int Solve(int a, int A, int b, int B, int c, int C) { static int f[N][N], bin[N][N]; int ans = 0; ans = (1LL * c * Qow(Solve(a, A, b, B), C / c) + ans) % mod; ans = (1LL * b * Qow(Solve(a, A, c, C), B / b) + ans) % mod; ans = (1LL * a * Qow(Solve(b, B, c, C), A / a) + ans) % mod; ans = (ans - 1LL * b * c * Qow(Solve(a, A), B / b * C / c) % mod + mod) % mod; ans = (ans - 1LL * a * c * Qow(Solve(b, B), A / a * C / c) % mod + mod) % mod; ans = (ans - 1LL * a * b * Qow(Solve(c, C), A / a * B / b) % mod + mod) % mod; ans = (ans + a * b * c) % mod; for (int i = 0; i <= max(A / a, B / b); ++i) { bin[i][0] = 1; for (int j = 1; j <= i; ++j) { bin[i][j] = (bin[i - 1][j] + bin[i - 1][j - 1]) % mod; } } for (int i = A / a; i; --i) { for (int j = B / b; j; --j) { f[i][j] = 1LL * bin[A / a][i] * bin[B / b][j] % mod * Qow(c, (A / a - i) * (B / b - j)) % mod; for (int k = i; k <= A / a; ++k) { for (int l = j; l <= B / b; ++l) { if (k != i || l != j) { f[i][j] = (f[i][j] - 1LL * f[k][l] * bin[k][i] % mod * bin[l][j] % mod + mod) % mod; } } } if (i == A / a && j == B / b) { continue; } int tmp = 0; tmp = (tmp + Qow(Qow(b, i) + Qow(a, j) - 1, C / c)) % mod; tmp = (tmp - Qow(Qow(b, i), C / c) + mod) % mod; tmp = (tmp - Qow(Qow(a, j), C / c) + mod) % mod; tmp = (tmp + 1) % mod; tmp = 1LL * tmp * a * b * c % mod; ans = (1LL * f[i][j] * tmp + ans) % mod; } } return ans; } int main() { #ifdef wxh010910 freopen("d.in", "r", stdin); #endif int a, b, c, A, B, C; Read(a), Read(b), Read(c), Read(A), Read(B), Read(C); if (A % a || B % b || C % c) { puts("0"); } else { printf("%d\n", Solve(a, A, b, B, c, C)); } #ifdef wxh010910 Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }