Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-B. Mickey Mouse Constructive · znzryb
## 题目大意
**题目描述**
给定一个数组 $a$,定义 $f(a)$ 为将 $a$ 划分成一个或多个连续子数组的方案数,需满足以下条件:
1. 每个元素恰好属于一个子数组。
1. 所有子数组的元素和都相等。
例如,对于 $a=[1,1]$,$f(a)=2$,因为有两种合法的划分方案:
- $[1,1]$,此时唯一的子数组和为 $2$。
- $[1]+[1]$,此时两个子数组和均为 $1$。
给定两个整数 $x$ 和 $y$。你需要构造一个长度为 $x+y$ 的数组 $a$,其中包含 $x$ 个 $1$ 和 $y$ 个 $-1$。
你需要求出在所有合法的数组 $a$ 中,$f(a)$ 的**最小值**,并将该最小值对 $676767677$ 取模后输出。同时,你需要输出一个能达到该最小值的数组构造方案。
**注意**:你需要最小化的是 $f(a)$ 本身,然后将这个最小值对 $676767677$ 取模,而不是去最小化 $f(a) \bmod 676767677$ 的结果。
**输入格式**
第一行包含一个整数 $t$ ($1 \le t \le 10^4$),表示测试用例的数量。
接下来每个测试用例包含一行,包含两个整数 $x$ 和 $y$ ($0 \le x, y \le 2 \cdot 10^5$),保证 $x+y \ge 1$。
保证所有测试用例中 $x$ 的总和与 $y$ 的总和均不超过 $2 \cdot 10^5$。
**输出格式**
对于每个测试用例,输出两行:
第一行输出 $f(a)$ 的最小值对 $676767677$ 取模的结果。
第二行输出一个达到该最小值的数组 $a$ 的元素(用空格分隔)。
**样例输入**
```
4
2 0
1 1
6 7
1 3
```
**样例输出**
```
2
1 1
1
1 -1
1
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
2
-1 -1 -1 1
```
**样例解释**
在第一个测试用例中,$x=2$ 且 $y=0$。唯一可能的数组是 $a=[1,1]$,正如题目描述中所解释的,此时 $f(a)=2$。
在第二个测试用例中,$x=1$ 且 $y=1$。一个能使 $f(a)$ 最小化的合法数组是 $a=[1,-1]$。此时 $f(a)=1$,因为唯一能使所有子数组和相等的划分方式就是不进行任何分割(即 $[[1,-1]]$,子数组和为 $0$)。
## 思路讲解
```cpp
void Solve() {
ll X, Y;
cin >> X >> Y;
vector<ll> A(X + Y + 2);
for (int i = 1; i <= X; ++i) {
// cout << 1 << " ";
A[i] = 1;
}
for (int i = 1; i <= Y; ++i) {
// cout << -1 << " ";
A[i + X] = -1;
}
ll s = llabs(X - Y);
ll ans = 1;
// 这里要采用求约数个数的方法
if (s != 0) {
ans = 0;
for (ll d = 1; d * d <= s; ++d) {
if (s % d == 0) {
++ans;
if (d * d != s) ++ans;
}
}
}
cout << ans << "\n";
for (int i = 1; i <= X + Y; ++i) {
cout << A[i] << " ";
}
cout << "\n";
// mod
}
```
## AC代码
AC
[https://codeforces.com/contest/2211/submission/368623804](https://codeforces.com/contest/2211/submission/368623804)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: B. Mickey Mouse Constructive
* Contest: Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2211/problem/B
* Created: 2026-03-28 22:48:14
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 676767677;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
void Solve() {
ll X, Y;
cin >> X >> Y;
vector<ll> A(X + Y + 2);
for (int i = 1; i <= X; ++i) {
// cout << 1 << " ";
A[i] = 1;
}
for (int i = 1; i <= Y; ++i) {
// cout << -1 << " ";
A[i + X] = -1;
}
// ll N = X + Y;
// ll sum = X - Y;
// ll cur = 0;
// ll ans = 0;
// for (int i = 1; i <= N; ++i) {
// cur += A[i];
// ll rem = sum - cur;
// #ifdef LOCAL
// debug(cur);
// debug(rem);
// cend;
// #endif
// if (cur == 0) {
// // assert(0);
// if (cur == rem) {
// ++ans;
// ans %= mod;
// }
// continue;
// }
// if ((rem * cur) >= 0 && rem % cur == 0) {
// ++ans;
// ans %= mod;
// }
// }
ll s = llabs(X - Y);
ll ans = 1;
if (s != 0) {
ans = 0;
for (ll d = 1; d * d <= s; ++d) {
if (s % d == 0) {
++ans;
if (d * d != s) ++ans;
}
}
}
cout << ans << "\n";
for (int i = 1; i <= X + Y; ++i) {
cout << A[i] << " ";
}
cout << "\n";
// mod
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
// if (Y != 0) {
// ll N = X + Y;
// ll sum = X;
// ll ans = 1;
// for (ll i = 1; i <= Y; ++i) {
// sum--;
// ll rem = Y - i;
// if (sum < 0) {
// if (rem % abs(sum) == 0 && rem != 0) {
// ans++;
// ans %= mod;
// }
// }
// }
// cout << ans << "\n";
// } else {
// ll ans = 1;
// ll sum = 0;
// for (ll i = 1; i <= X; ++i) {
// sum++;
// ll rem = X - i;
// if (rem % abs(sum) == 0 && rem != 0) {
// ans++;
// ans %= mod;
// }
// }
// cout << ans << "\n";
// }
*/
```
:::
## 心路历程(WA,TLE,MLE……)