本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-11 18:48:55

【题目链接】

题意：

给你 $t$ 个整数，让我们求四个数 $a,b,c,d$，并且 $a + b + c + d = n$ 并且 $\gcd(a , b)$ $= \operatorname{lcm(c , d)}$。

题解思路：

我们先输出一个 $n - 3$，然后再输 $3$ 个 $1$，即可，因为 $n - 3 + 1 + 1 + 1 = n - 3 + 3 = n$。

在来看后面的满足，后面要求 $\gcd (a , b) = \lcm (c , d)$，那么由于任何一个数都是 $1$ 的倍数，所以 $\gcd(a , b)$ 一定等于 $1$。

而两个 $1$ 的最小公倍数就是 $1$，$1 = 1$ 所以这种方法可行。

AC Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int T;
int main() {
	cin >> T;
	while (T --) {
		int n;
		cin >> n;
		cout << n - 3 << ' ';\/\/先输出一个n-1
		for (int i = 1; i <= 3; ++ i)
			cout << 1 << ' ';\/\/再输出3个1
		cout << endl;
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-12 18:15:03

【题目链接】

题解思路：

若能找到一个 $(i , j)$ 集合，表示只取 $a_{i,j}$ 时，原矩阵的每个元素的贡献都足 $1$，那么答案就是 $a_{i , j}$ 的异或和，用 $c_{i , j}$ 来表示 $a_{i,j}$ 取不取，取为 $1$，不取为 $0$。

我们第一行随便赋值 $c_{1,i}$，我们统一赋值成 $1$ 然后从第二行开始从上往下扫描，对于当前位置 $(i , j)$，我们的目标是让 $a_{i - 1 , j}$ 的贡献为 $1$ 即：

$$c_{i - 2,j} \oplus c_{i - 1 , j - 1} \oplus c_{i - 1}{j + 1} \oplus c_{i , j} = 1$$

这样就得到了 $c_{i,j}$。

不过现在还要证明 $a_{n,i}$ 的贡献为 $1$。

考虑现在还有一个合法方案 $c_{i , j}$ $'$，我们逐一比较求得的 $c_{1 , j}$ 与 $c_{1,j}$ $'$，如果不一样，则修改 $c_{1 , i}$ $'$，然后一次修改受影响的 $c_{i , j}$ $'(i > 1)$，整个过程保证 $a_{i , j}$ $'$ 的贡献仍然为 $1$。可以发现后两行一定是修改 $(n - 1 , n - i) , (n - 1 , n - i + 2) , (n , n - i + 1)$，则最后一行 $a_{i,j}$ $'$ 的贡献不变

AC Code:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream> 
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N] , c[N][N];
void solve () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i)  
        for (int j = 1; j <= n; ++ j)
            cin >> a[i][j];
    for (int i = 1; i <= n; ++ i) c[1][i] = 1;\/\/先把c[1][i]初始化成1
    for (int i = 1; i <= n; ++ i) c[i][n + 1] = 0;
    for (int i = 2; i <= n; ++ i) 
        for (int j = 1; j <= n; ++ j) {
            c[i][j] = c[i - 2][j] ^ c[i - 1][j - 1] ^ c[i - 1][j + 1] ^ 1;
        }
    int ans = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            if (c[i][j])
                ans ^= a[i][j];
    cout << ans << endl;
}
int main() {
    int T;
    cin >> T;
    while (T --) solve();
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-12 21:22:29

【题目链接】

题解思路：

我们把 $k$ 视为单位一，最后乘上就行。

定义 $f_{i,j}$ 为还剩 $i$ 轮，需要做 $m$ 次加法的结果。有 $f_{i , i} = i$，$f_{i , 0} = 0$。这是边界情况。

另外当 $i > j > 0$ 时： $$f_{n , m} = \min (-x + f_{n - 1 , m - 1} , x + f_{n - 1 , m})(0 \le x \le 1)$$

得

$$\max_{x}f_{n , m} = \frac{f_{n-1 ,m-1}+f_{n - 1 , m}}{2} $$

至此，我们可以 $O(nm)$ 的 DP 解决 D1 的数据。

AC Code:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int Maxn = 2010;
const int N = 2000;
const int mod = 1e9 + 7;
int f[Maxn][Maxn];
ll power (ll a , ll x) {
    ll r = 1;
    a %= mod;
    while (x) {
        if (x & 1) r = r * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return r;
} 
ll inv (ll a) {
    return power (a , mod - 2);
}
void solve () {
    ll n , m , k;
    cin >> n >> m >> k;
    cout << f[m][n] * k % mod << endl;
}
int main() {
    ll i2 = inv (2);
    for (int i = 1; i <= N; ++ i) {
        f[i][i] = i;
        for (int j = i + 1; j <= N; ++ j) 
            f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % mod * i2 % mod;
    }
    int T;
    cin >> T;
    while (T --) {
        solve ();
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-14 20:41:46

题解思路：

有一个很显然的性质：

最后相同的元素一定是 $a_n$。

所以我们每次要尽可能多的去贴数字到前面。

比如：

$4\ 4\ 2\ 4\ 4$ 那么我们一定会把 $4\ 4$ 移过去，因为这样变成相同的元素才能尽可能的多。

AC CODE:

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010;
int a[N];
int main() {
    int T;
    cin >> T;
    while (T --) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++ i)
            cin >> a[i];
        int p = n - 1 , ans = 0;
        while (p > 0) {
            if (a[p] != a[p + 1]) {
                ans ++;
                p -= n - p;
                if (p < 0)
                    break;
                a[p + 1] = a[n];\/\/把元素复制过来
            }else -- p;
        }
        cout << ans << endl;
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-14 21:17:26

题解思路：

有一个很显然的性质：

$x\ n - x$ 的二进制每一位都是相反的。

所以我们可一构造出 $k=0$ 时的情况。

当$k \ne n-1$ 的时候：

我们就可以让 $k$ 和 $n - 1$ 组成一组。

再让 $n - k + 1$ 和 $0$ 构成一组

接下来就是 $k = n-1$ 的情况：

若 $k=n-1$，那我们就不能 $n - 1$ 和 $n - 1$，$0$ 和 $0$ 分成一组。

因为要 $n\ge 4$，即二进制至少有两位。

$(0){10} = (0){2}$， $(1){10} = (1){2}$， $(2){10} = (10){2}$， $(3){10} = (11){2}$。

$(n - 4){10} = ((??????...-1)11){2}$、

$(n - 3){10} = (?????...00){2}$、

$(n - 2){10} = (?????...01){2}$、

$(n - 1){10} = (?????...10){2}$、

$(n){10} = (??????... 11){2}$。

那么我们可以 $n - 2$ 和 $3$。

$n - 4$ 和 $1$。

$n - 1$ 和 $n - 3$。

$2$ 和 $0$。

特殊情况 $n = 4 , k = 3$ 时构造不出来，输出 $-1$，其他情况都有解，把这种情况特判掉就可以了。

AC CODE:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1 << 20;
int a[N];
int main() {
    int T;
    scanf ("%d" , &T);
    while (T --) {
        int n , k;
        scanf ("%d%d" , &n , &k);
        if (n == 4 && k == 2)puts("-1");\/\/无解情况
        else if (k == 0) {\/\/k=0时
            for (int i = 0; i < n \/ 2; ++ i)
                printf ("%d %d\n" , i , n - 1 - i);
        }else if (k != n -1) {\/\/k!=n-1时
            printf ("%d %d\n" , n - 1 , k);
            printf ("%d %d\n" , n - 1 - k , 0);
            for (int i = 1; i < n \/ 2; ++ i)
                if (i != k && i != n - 1 - k)
                    printf ("%d %d\n" , i , n - 1 - i);
        }else {\/\/k=n-1的情况
            printf ("%d %d\n" , n - 2 , 3);
            printf ("%d %d\n" , n - 4 , 1);
            printf ("%d %d\n" , n - 1 , n - 3);
            printf ("%d %d\n" , 2 , 0);
            for (int i = 4; i < n \/ 2; ++ i)
                printf ("%d %d\n" , i , n - i - 1);
        }
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-17 19:10:42

题解思路：

我们就第一行全填上 X， 第二行让 X 联通， 第三行全填 X。

这样我们会发现每 $3$ 个一个周期。

但题目给出了在一个 X 的八个方向上是没有 X 的。

有了这个条件后，那么我们填好后，那么每三个就是一个连通块。

但上下之间没有贯穿。

若原来有 X 就选最少的就可以了，若原来没有 X，那么就随便开出一条就可以了。

注意：最后一行直接打穿上去就行了。

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 510;
int T;
char a[N][N]; 
int main() {
    scanf ("%d" , &T);
    while (T --) {
        int n , m;
        scanf ("%d%d" , &n , &m);
        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < m; ++ j)
				cin >> a[i][j];
		for (int i = 0; i < n; ++ i) {
			bool ok = true;
			for (int j = 0; j < m; ++ j) {
				if (i % 3 == 0) {\/\/是三的倍数的行，就把他填成X 
					a[i][j] = 'X';
					if (ok && a[i - 1][j] == 'X'){\/\/把他从上面连上，变联通 
						a[i - 1][j] = a[i - 2][j] = 'X';
						ok = false;
					}
					if (ok && i > 1 && a[i - 2][j] == 'X') {\/\/同上 
						a[i - 1][j] = a[i - 2][j] = 'X';
						ok = false;
					} 
				}else if (i == n - 1) {
					if (a[i][j] == 'X')\/\/最后一行的情况 
						if (i > 0)
							a[i - 1][j] = 'X';
				}
			}
			if (ok && i % 3 == 0 && i > 0) {\/\/其他地方没有X随便建一条。
				a[i - 1][0] = a[i - 2][0] = 'X'; 
			}
		}
		for (int i = 0; i < n; ++ i) {
			for (int j = 0; j < m; ++ j)
				cout << a[i][j];
			puts("");
		}
	}
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-18 19:08:21

题解思路：

我们先扫描一遍 $s$ 和 $t$，然后如果啊 $s_{i} != t_{i}$，那么在 $t$ 中找到一个 $t_{j}$ 使得 $t_{j} == t_{i}$ 然后交换一下 $t_{j}$ 和 $s_{i}$。

我们看一下样例：

souse 和 houhe

它们按照上述法方只需要 $1$ 次就可以了。这是一种情况。

在看一个：

abc 和 bca

我们发现他第一个就不相等了，但 bca 里没有 $\ge 2$ 个 b，但我们可以：

那么我们就可以把他首字母变成相等，一共用了 $2$ 步。

那我们就可以分两种情况来贪心：

• 1 若他们有一位不相等，并第二个串里有一个与他相等的字母，那么次数加 $1$。
• 2 若他们有一位不相等，而第二串里没有与他相等的字母，但第一个串里有一个跟第二个串里的字母相等的，答案加 $2$。

因为他至多每次都是情况 $2$，那么最多就执行 $n$ 次，所以执行次数一定 $\le 2n$。

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int n;
string s , t;
vector <pair <int , int>> op;
void solve () {
    op.clear();
    scanf ("%d" , &n);
    cin >> s >> t;
	for (int i = 0; i < s.size(); ++ i) {
		if (s[i] != t[i]) {\/\/若他们不相等 
			int flag = 0;
			for (int j = i + 1; j < t.size(); ++ j)
				if (t[j] == t[i]) {\/\/若有与他相等的 
					flag = 1;\/\/代表已经让s[i] == t[i]了 
					op.push_back ({i + 1 , j + 1});\/\/把操作加入到vector里 
					swap (s[i] , t[j]);\/\/交换 
					break;
				} 
			if (flag == 0) {\/\/若t串里没有与t[i]相等的则尝试方案二 
				for (int j = i + 1; j < s.size(); ++ j)
					if (s[j] == t[i]) {\/\/第二种情况 
						flag = 1;
						op.push_back ({j + 1 , t.size()});\/\/按照第二个情况进行操作 
						swap (s[j] , t[t.size() - 1]);
						op.push_back ({i + 1 , t.size()});
						swap (s[i] , t[t.size() - 1]);
					}
			}
			if (!flag) {\/\/如果这两种情况都不行，那么就无解 
				puts("NO");
				return ; 
			} 
		}
	}
	puts("YES");
	cout << op.size() << endl;\/\/一共有多少次操作，vector有一个好处就是可以自己通过size来知道他的长度，而数组就得用一个变量来储存。
	for (int i = 0; i < op.size(); ++ i) 
		cout << op[i].first << ' ' << op[i].second << endl;
}
int main() {
    int T;
    scanf ("%d" , &T);
    while (T --)
    	solve();
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-23 10:36:33

题解思路：

我们看看他有什么性质：

若我们去掉一个数的质因子，那么他就会向下走一格。

还有一个，我们看一下样例：$12$ 到 $2$ 那么我们先去掉一个质因子 $3$，再去掉一个质因子 $2$，或先取掉质因子 $2$，再去掉一个质因子 $3$，那么他们的路径权值是一样的。证明：

假设 $u$ 能走向 $v$，并 $u > v$，因为若从 $u$ 走向 $v$，那么把他质因子分解，既然 $u$ 能走向 $v$，那么 $v$ 一定是 $u$ 的某个因子的因子。所以 $v$ 一定是 $u$ 的因子，因为 $u$ 是在不断去掉质因子才达到 $v$ 的。

我们先把 $u$ 质因子分解：$u = p_1^{a_1} p_2^{a_2} p_3^{a_3} ...\ p_m^{a_m}$，那么你走下去，那么你会去掉一些质因子，就是 $a_1-x_1,a_2-x_2 ...\ a_m-x_m$，有的可能是去掉了零个，那么他的因子数为 $(a_1+1)(a_2+1)...(a_m+1)$，所以 $u$ 的因子数为 $(a_1+1)(a_2+1)...(a_m+1)$，而 $v$ 的因子数为 $(a_1-x_1+1)(a_1-x_2+1)...(a_m-x_m+1)$，那么我们把 $u$ 设为 $x$，那么假设我们先去掉 $p_i$ 的一个因子，就相当去掉一个 $\frac{\mathrm{x}}{\mathrm{a_i}}$，下一个我们去掉一个 $p_k$ 就相当于去掉： $\frac{\mathrm{xa_i}}{\mathrm{(a_i+1)(a_j + 1)}}+\frac{\mathrm{x}}{\mathrm{a_i+1}}$，想乘得 $\frac{\mathrm{a_i+a_j+1}}{\mathrm{(a_i+1)(a_j+1)}}x$，那么 $a_i$ 和 $a_j$ 交换了位置，那么其实不变，在推广到普通情况，也是相同的，证毕。

那么我们从 $x$ 走到 $y$，假设 $x>y$，那么 $x$ 每次去掉质因子，直到 $1$ 那么我们到一个点，比如 $y$ 这个点，那么他这个的最短路就是 $x$ 去因子的这条路，不然的话，你就没有这个更短。

然后若 $y$ 不是 $x$ 的因子，那么我们要选 $\gcd(x,y)$，这样才是最短路。若不选最大公因数的话，那么就会取掉多余的质因子，就不优了。

那么我们怎么算呢，因为他的质因子为 $p_1^{a_1} p_2^{a_2} p_3^{a_3} ...\ p_m^{a_m}$，走到他们的 $\gcd$ 就是：$p_1^{a'_1} p_2^{a'_2} p_3^{a'_3} ...\ p_m^{a'_m}$ 这就是他的过程，那么我们要把某个因子，要去掉一些因子，那么我们可以把他们换一下顺序，这个东西就是多次向系数。

那么我们求一下他们的全排列，但有重复的情况，比如全是相同的数，所以他的全排列有很多种，但都是一样的。

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll D , fac[60] , inv[60];
vector <pair <ll , int>> p;
map <ll , vector<int>>mp;\/\/就相当于质因数分解的系数
vector <int> now;
ll gcd (ll a , ll b) {return b == 0 ? a : gcd (b , a % b);}\/\/求最大公因数
ll power (ll a , ll b) {\/\/快速幂，用来求逆元。
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void dfs (int dep , ll sum) {\/\/暴力构造O(sqrt(n))
	if (dep == p.size()) {
		mp[sum] = now;\/\/取出来，放到一个map里
		return;
	}
	auto x = p[dep];
	now.push_back (0);
	dfs (dep + 1 , sum);
	now.pop_back();
	for (int i = 1; i <= x.second; ++ i) {
		sum *= x.first;
		now.push_back (i);
		dfs (dep + 1 , sum);
		now.pop_back ();
	}
}
void init () {\/\/预处理函数
	fac[0] = fac[1] = 1;
	for (int i = 2; i <= 59; ++ i)
		fac[i] = fac[i - 1] * i % mod;\/\/预处理阶乘
	for (int i = 1; i <= 59; ++ i)
		inv[i] = power (fac[i] , mod - 2);\/\/逆元因为mod是质数，所以可以预处理
	ll d = D;
	for (ll i = 2; i <= d \/ i; ++ i) {\/\/分解质因数.
		if (d % i == 0) {
			int cnt = 0;
			while (d % i == 0) {
				d \/= i;
				++ cnt;
			}
			p.push_back ({i , cnt});
		}
	}
	if (d > 1) p.push_back ({d , 1});
	dfs (0 , 1);\/\/构造
}
int main() {
	cin >> D;
	init();\/\/预处理
	int q;
	cin >> q;
	while (q --){
		ll u , v;
		cin >> u >> v;
		ll x = gcd (u , v);
		vector <int> a , b , c;\/\/把每个数的系数取出来
		a = mp[u] , b = mp[v] , c = mp[x];
		for (int i = 0; i < a.size(); ++ i) {\/\/做差，得出来的数就是答案的系数
			a[i] -= c[i];
			b[i] -= c[i];
		}
		ll sum = 0 , sum2 = 0 , ans = 1 , ans2 = 1;
		for (auto x : a) {\/\/计算
			if (!x) continue;
			sum += x;
			ans = ans * inv[x] % mod;
		}
		ans = ans * fac[sum] % mod;
		for (auto x : b) {\/\/计算
			if (!x) continue;
			sum2 += x;
			ans2 = ans2 * inv[x] % mod;
		}
		ans2 = ans2 * fac[sum2] % mod;
		ans = ans * ans2 % mod;\/\/最后相乘。
		cout << ans << endl;
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-25 22:06:25

题解思路：

我们有 $T$ 轮，只有最后一轮赢了才是赢了，所以前 $T - 1$ 轮，随便就可以了。

状态：

必胜态：上一轮一定要输

必败态：上一轮一定要赢

所以我们知道了 $i - 1$ 的状态，那么我们就可以求出第 $i$ 轮的状态。

那么我们只要维护一个赢得状态值和输的状态值就可以得到结果。

难点就在他们怎么计算：

------------$Win$ 数组分割线------------

$Win_{e,e} = 0$，因为 $e \ge 1$，所以不管 $e \times 2$ 或者 $e + 1$ 都是必败态。

那么我们就可以通过 $Win_{e,e}$ 求出 $Win_{e-1,e}$ 等。

若 $e$ 是奇数：

$Win_{e,e} = 0$

$Win_{e - 1, e} = 1$只能加一转换成必胜态

$Win_{e - 2 , e} = 0$因为他是一个奇数，而奇数只能转移到必胜态，因为两个奇数相加，得偶数；奇数加一，就相当于奇数加奇数。所以只会转移到必胜态，所以他就是必败态。 $$\dots$$ $$\dots$$ 以此类推

$s$ 与 $e$ 奇偶性相同时，就会走向一个必败态，否则就会走向一个必胜态。

若 $e$ 是偶数：

当 $s$ 是偶数，那么 $s \times 2$ 就是必败态，所以当 $\left \lfloor \frac{e}{4} \right \rfloor < s \le \left \lfloor \frac{e}{2} \right \rfloor$，$s \times 2$ 一定是必胜态。

当在 $\left \lfloor \frac{e}{4} \right \rfloor$ 这个点时，他一定是必败态，因为他乘二，就会到 $s$ ~ $\left \lfloor \frac{e}{2} \right \rfloor$，所以一定必败。

那么我们就可以递归去判断： $dfs (s , \frac{e}{4})$。

因为 $\left \lfloor \frac{e}{4} \right \rfloor$ 乘二到这个区间，而比他小的一定超不过这个区间，所以若能到必胜态区间 $\left \lfloor \frac{e}{4} \right \rfloor - 1$ ~ $\left \lfloor \frac{e}{2} \right \rfloor$ 这个区间的数，必定是必败态，当我们可以转到 $\frac{e}{2}$ 就是必胜态。

这就是 $Win$ 数组的求法。

------------$Lost$ 数组分割线------------

也可以类似的分析一下：

$\left \lfloor \frac{e}{2} \right \rfloor < s \le e $ 时，他一定是必胜态，那么对于 $\frac{e}{2}$ 一定是必败态，这就很像我们分析 $Win$ 时 $e$ 是偶数的情况，我们就可以直接让他转移到 $Win$ 的情况就可以了。

这样，Win 和 Lost 数组就都求出来了。

虽然我们前面说过要到着来，但是我们正着来就行了，那么当我们这一轮为先手，那么 Win 和 Lost 只有一个为 $1$，那么它就不能改变结果，若 Win 和 Lost 都是 $1$ 那么想输想赢都可以，这样最后的就可以知道了。

注意：$1 \le s_i,e_i \le 10^{18}$，要开 long long！

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
bool dfs (ll s , ll e) {
	if (e & 1) {\/\/奇偶性是否相同 
		if (s & 1) return false;
		else return true;
	}
	if (s > e \/ 2) {
		if (s & 1) return true; 
		else return false;
	}
	if (s > e \/ 4) return true;\/\/当他大于e\/4时，和偶数为必胜态区间范围，所以返回true 
	return dfs (s , e >> 2);\/\/递归 
}
bool check (ll s , ll e) { 
	if (s > e \/ 2) return true;\/\/奇数里这个区间为必胜态
	return dfs (s , e >> 1);\/\/否则返回和Win的共同部分 
}
int main() {
	int n;
	cin >> n;
	bool cur = false , win , lose;
	for (int i = 0; i < n; ++ i) {
		ll s , e;
		cin >> s >> e;
		win = dfs (s , e);\/\/Win
		lose = check (s , e);\/\/Lost
		win ^= cur;\/\/和是否先手异或一下 
		lose ^= cur;
		if (win == lose) break;\/\/若Lost和Win一样 ，break 
		if (win) cur = 1;\/\/若这一局你赢了，那么下一局你先手 
		else cur = 0;\/\/否则就是后手 
	}
	cout << win << ' ' << lose << endl; 
	return 0;
}

码字不易，求赞！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-26 21:02:13

题解思路：

当 $n$ 是偶数先手必胜。

当 $n$ 是奇数后手必胜。

我们来证明一下：

1. $n$ 是偶数是先手必胜

既然 $n$ 是偶数，那么先手有一个构造方案：

把 $\mod n$ 相等的数放在一起，例如：$(1 , 1) , (1 , n + 1)$。

所以后手拿的数只有 $1 + ... + n$。 他就是 $(1 + n) \times n \div 2$，对于这个值，那么为什么他一定不是 $2n$ 的倍数呢？

$n = 2m$

因为 $n$ 是偶数，而 $n + 1$ 就是个奇数，那这个数是不是 $n$ 的倍数呢？

我们考虑一下：

因为 $n = 2m$ 所以原式就变成了：$(2m + 1) \times m$。

那么我们想让 $(2m + 1) \times m$ 是 $n$ 的倍数，那么我们要有个 $2$，但由于 $2m + 1$ 一定是奇数，所以他一定不是 $n$ 的倍数。
因为他不是 $n$ 的倍数，那他就不可能是 $2n$ 的倍数了。

证毕。

那么为什么 $n$ 是偶数时后手必败呢？我们只要证明当 $n$ 是奇数时后手必胜就可以了。

2. 当 n 为奇数时后手必胜

首先我们证明一个性质：

$(2n + 1) \times n \mod 2n = n$

因为他乘了奇数倍，所以他 $\mod 2n$ 一定是 $n$，因为它比奇数倍还多了一个 $n$。

若我们选 $n$ 个数，定义 $sum$ 为选的 $n$ 个数的和。那么 $sum \mod n = 0$。

那么我们有两种情况 $sum \mod 2n = n$，$sum \mod 2n = 0$。

若 $sum \mod 2n = 0$，那么我们就是答案；若 $sum \mod 2n = n$，那么另外 $n$ 个数就是答案。

那么只要 $\mod n = 0\ 1\ 2\ ......\ n - 1$ 的数各有两个，那么我不管怎么塞，我们去出来这 $n - 1$ 个数。

注意：奇数的情况时要fflush(stdout)，不然会Idleness limit exceeded on test 3，洛谷显示UKE

AC记录

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 1000010;
typedef long long ll; 
int n;
int a[N];
bool vis[N] , vis2[N] , vis3[N];
vector <int> e[N];
vector <int> g[N];
int main() {
	scanf ("%d" , &n);
	if (n & 1) {\/\/奇数的情况 
		puts("Second");
		fflush(stdout);
		for (int i = 1; i <= n * 2; ++ i) {
			scanf ("%d" , &a[i]);\/\/读入 
			e[i % n].push_back (a[i]);
			g[a[i]].push_back (i);
		}
		for (int i = 1; i <= n * 2; ++ i) {
			int root = i % n;
			if (vis[root]) continue; 
			int u = i;
			while (1) {
				vis[u % n] = vis2[u] = 1;\/\/把他标记上 
				int v = -1;
				for (auto x : g[a[u]])
					if (!vis[x % n])
						v = x;
				if (v == -1) break;
				if (v > n) v -= n;\/\/>n 就 -n 
				else v += n;\/\/否则加上n 
				u = v;
			}
		}
		ll ans = 0;
		for (int i = 1; i <= n << 1; ++ i) 
			if (vis2[i]) \/\/统计他们的和 
				ans += i;
		if (ans & 1) {\/\/sum % 2n == n
			bool ok = false;\/\/控制空格，避免后面多输出一个空格，当然加不加都无所谓 
			for (int i = 1; i <= n << 1; ++ i) 
				if (!vis2[i]) {\/\/那么另外的那些就是答案 
					if (ok) printf (" ");
					printf ("%d" , i);
					ok = true;
				}
			puts("");
		}else {\/\/否则 sum % 2n == 0 
			bool ok = false;\/\/ok含义同上 
			for (int i = 1; i <= n << 1; ++ i)
				if (vis2[i]) {\/\/那么就是原来的数 
					if (ok) printf (" ");
					printf ("%d" , i);
					ok = true;
				}
			puts("");
		} 
	}else {
		puts ("First");\/\/偶数的情况，先手必胜 
		for (int i = 1; i <= n << 1; ++ i) {\/\/直接输出 
			printf ("%d" , i % n + 1);\/\/把两个同余的放在一块 
			if (i == n << 1) puts("");
			else printf (" ");
		} 
	}
	return 0;
}

码字不易，求赞！