Znzryb's Blog

CF-1075-D2. Little String (Hard Version)（进行更加细致的分类讨论）（对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的）

Posted on 2026-01-25 Edited on 2026-04-06

题目大意

1. 题目定义

给定一个长度为 $n$ 的字符串 $s$ （由 0、1、? 组成）和一个正整数 $c$ 。

函数 $f(w)$ 的定义：

对于一个仅含 0 和 1 的字符串 $w$ ，其值 $f(w)$ 表示满足以下条件的 $[0, 1, \dots, n-1]$ 全排列 $p$ 的总数：

对于 $1 \le i \le n$ ，如果 $w_i = 1$ ，则排列 $p$ 中必须存在至少一个连续子段，其 MEX 值为 $i$ 。
对于 $1 \le i \le n$ ，如果 $w_i = 0$ ，则排列 $p$ 中不得存在任何连续子段的 MEX 值为 $i$ 。

注：MEX（Minimum Excluded）指集合中未出现的最小非负整数。

2. 目标任务

通过将 $s$ 中的所有 ? 替换为 0 或 1 来构造字符串 $w$ 。在所有满足 $f(w)$ 不能被 $c$ 整除的字符串 $w$ 中，计算 $f(w)$ 的最小值。

3. 输出要求

输出该最小值对 $10^9 + 7$ 取模的结果。
若不存在满足条件的 $w$ ，则输出 $-1$ 。

4. 样例解释辅助理解

样例 3 ( $n=4, c=100, s=1001$ )：
字符串固定为 $1001$ 。此时 $f(1001) = 4$ ，满足条件的排列包括 $[0,2,3,1], [0,3,2,1], [1,2,3,0], [1,3,2,0]$ 。由于 $4$ 不能被 $100$ 整除，答案为 $4$ 。
样例 7 ( $n=5, c=8, s=100?1$ )：
若将 ? 替换为 0 得到 $w=10001$ ，经计算 $f(w) = 12$ 。由于 $12$ 不能被 $8$ 整除，且经比较这是所有可能替换中的最小值，故输出 $12$ 。
样例 2 ( $n=3, c=1, s=???$ )：
无论如何替换 ?，任何整数 $f(w)$ 都能被 $1$ 整除。因此不存在满足 “不能被 $c$ 整除” 条件的 $w$ ，输出 $-1$ 。

CF-1075-D1. Little String (Easy Version)（把序列生成的过程看成不断插入数字的过程）（插入过程可以写为一个循环，应该多少范围就多少范围，特判写在循环里面）

Untitled

思路讲解

那么是这样子的，这道题目如果把这个序列生成的这个过程看成从 $0\sim n-1$ 不断插入的过程，那么如果 $w_i=0$ ，那么 $i$ 就插入在原来 $0\sim i-1$ 之间的空当中。 $w_i=1$ ，只能插入在 $0\sim i-1$ 的两段。

D1 当中，我们采用如上方法得到答案。

这道题目，其实想让我们求的是在不被 $c$ 整除的前提下，能够得到的最小值。

那其实说白了，想让值比较小，那就除了首位，结尾，全部填 1 就完了（遇到？），不过现在就是这个不能被 $c$ 整除比较烦。

当然，除了首位，当 $i-1$ 为偶数的时候，也应该填写这个 ‘1’，因为反正都要引入 $2$ ，那不如就引入一个 $2$ 。

不过这道题目，其实就是一个分类讨论：

对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的。因此，采用这个我们之前说的策略：

那就除了首位，结尾，全部填 1 就完了（遇到？时）

那么对于 2 的幂次，先不断填 2 进去，发现不行了，我们就回退，乘以 $i-1$ ，注意逆序遍历。

// 对于 2 的幂次来说，能不引入 2 自然最好
for (int i=N-1;i>=1;--i) {
    if (W[i]=='?') {
        ll ans_c_backup=ans_c,ans_backup=ans;
        ans_c*=2;
        ans_c%=C;
        ans*=2;
        ans%=mod;
        if (ans_c==0) {  // 发现不对，回退乘以 2，乘以 i-1
            ans_c=ans_c_backup;
            ans=ans_backup;
            ans*=(i-1);
            ans%=mod;
            ans_c*=i-1;
            ans_c%=C;
        }
    }
}

不过是对于什么进行分类讨论呢？

我们上面有一些地方，加上原本的串，都已经确定了一些，把这一部分的值计算出来，我们记作 $ans$ 。那么我们知道， $ans$ 与 $C$ 的因子的交集就是 $\gcd(ans,C)$ （可以用该式子计算： $\gcd(ans,C)= \gcd(ans\mod C,C)$ ）。那么 $C$ 当中还没有被消掉的因子的集合就是：

\frac{C}{\gcd(ans,C)}

我们就是对还未被消掉的因子集合进行分类讨论。

AC代码

https://codeforces.com/contest/2189/submission/360006878

源代码

/**
 * Problem: D2. Little String (Hard Version)
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/D2
 * Created: 2026-01-25 14:54:48
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ull N,C;
    cin >> N >> C;
    string W;
    cin>>W;
    W.insert(W.begin(),'#');
    if (W[1]=='?') {
        W[1]='1';
    }
    if (W[N]=='?') {
        W[N]='1';
    }
    if (W[1]!='1' || W[N]!='1') {
        cout<<-1<<"\n";
        return;
    }
    if (W[2]=='?') {
        W[2]='0';
    }
    for (int i=1;i<=N-1;++i) {
        if (W[i]=='?') {
            if ((i-1)%2==0) {
                W[i]='1';
            }
        }
    }
    ll ans=1,ans_c=1;
    for (int i=1;i<=N-1;++i) {
        if (W[i]=='?') {
            continue;
        }
        // 尝试往这个序列中插入 i
        if (W[i]=='1') {
            ans*=2;
            ans%=mod;
            ans_c*=2;
            ans_c%=C;
        }else {
            // 要破坏这个计划
            ans*=(i-1);
            ans%=mod;
            ans_c*=i-1;
            ans_c%=C;
        }
    }
    if (ans_c==0) {
        cout<<-1<<"\n";
        return;
    }
    ull rem_C=C/gcd(ans_c,(ll)C);
    if (has_single_bit(rem_C)) {
        // 对于 2 的幂次来说，能不引入 2 自然最好
        for (int i=N-1;i>=1;--i) {
            if (W[i]=='?') {
                ll ans_c_backup=ans_c,ans_backup=ans;
                ans_c*=2;
                ans_c%=C;
                ans*=2;
                ans%=mod;
                if (ans_c==0) {
                    ans_c=ans_c_backup;
                    ans=ans_backup;
                    ans*=(i-1);
                    ans%=mod;
                    ans_c*=i-1;
                    ans_c%=C;
                }
            }
        }
        if (ans_c==0) {
            cout<<-1<<"\n";
            return;
        }
        cout<<ans<<"\n";
    }else {
        // 对于非 2 的幂次，不额外引入任何奇数素因子，总是最好的
        for (int i=1;i<=N-1;++i) {
            if (W[i]=='?') {
                ans*=2;
                ans%=mod;
                ans_c*=2;
                ans_c%=C;
            }
        }
        if (ans_c==0) {
            cout<<-1<<"\n";
            return;
        }
        cout<<ans<<"\n";
    }

    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
1
3 3
???

1
20 253034496
10001100011000??????

AC
https://codeforces.com/contest/2189/submission/360006878

*/

心路历程（WA，TLE，MLE……）

CF-1075-D1. Little String (Easy Version)（把序列生成的过程看成不断插入数字的过程）（插入过程可以写为一个循环，应该多少范围就多少范围，特判写在循环里面）

Posted on 2026-01-24 Edited on 2026-04-06

题目大意

题目总结：Little String (Easy Version)

核心定义

对于一个长度为 $n$ 的 01 字符串 $w$ 和集合 $\{0, 1, \dots, n-1\}$ 的全排列 $p$ ，定义 $f(w)$ 为满足以下所有条件的排列 $p$ 的总数：

若 $w_i = 1$ ：排列 $p$ 中必须存在至少一个连续子段 $[p_l, \dots, p_r]$ ，使得该子段的 MEX 等于 $i$ 。
若 $w_i = 0$ ：排列 $p$ 中不存在任何连续子段的 MEX 等于 $i$ 。
MEX 定义： 集合中未出现的最小非负整数。例如 $\text{mex}([0, 1, 3]) = 2$ ， $\text{mex}([1, 2]) = 0$ 。

任务要求

输入： 长度为 $n$ 的字符串 $s$ （在本简单版本中不含问号，即 $w = s$ ）和一个正整数 $c$ 。
目标： 计算 $f(s)$ 。
- 如果 $f(s)$ 不能被 $c$ 整除，输出 $f(s) \pmod{10^9 + 7}$ 。
- 如果 $f(s)$ 能被 $c$ 整除，或者不存在满足条件的字符串（针对含问号版本），则输出 $-1$ 。

样例解释对照

样例输入	n	s	c	f(s) 计算与结果	解释
样例 3	4	`1001`	100	输出：4	满足条件的排列有 $[0,2,3,1], [0,3,2,1], \\ [1,2,3,0], [1,3,2,0]$ 。 $f(s)=4$ 不被 100 整除。
样例 6	5	`10001`	8	输出：12	$f(s)=12$ 。其中一个合法排列为 $[0,4,3,2,1]$ 。 $12$ 不被 8 整除。
样例 9	3	`101`	4	输出：2	合法排列为 $[0,2,1], [1,2,0]$ 。 $f(s)=2$ 不被 4 整除。
样例 2	3	`111`	1	输出：-1	无论 $f(s)$ 为多少，任何整数都能被 $c=1$ 整除，故输出 $-1$ 。

思路讲解

题目中的条件，具体来说就是如上图所示， $w_i=0$ ，就是 $i$ 把 $0～i-1$ 分隔开， $w_i=1$ ，就是 $i$ 位于 $0～i-1$ 的左边或者右边。

那么是这样子的，这道题目如果把这个序列生成的这个过程看成从 $0～n-1$ 不断插入的过程，那么如果 $w_i=0$ ，那么 $i$ 就插入在原来 $0～i-1$ 之间的空当中。 $w_i=1$ ，只能插入在 $0～i-1$ 的两段。

for (int i=1;i<=N-1;++i) {
    // 尝试往这个序列中插入 i
    if (W[i]=='1') {  //  插入在两端
        ans*=2;
        ans%=mod;
        ans_c*=2;
        ans_c%=C;
    }else {  // 插入在空当中
        // 要破坏这个计划
        ans*=(i-1);
        ans%=mod;
        ans_c*=i-1;
        ans_c%=C;
    }
}

然后这道题目就解决了。

AC代码

https://codeforces.com/contest/2189/submission/359662289

源代码

/**
 * Problem: D1. Little String (Easy Version)
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/D1
 * Created: 2026-01-25 10:37:10
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)2e5+10, INF = (1ll<<61)-1;
static constexpr ll mod = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N,C;
    cin >> N >> C;
    string W;
    cin>>W;
    W.insert(W.begin(),'#');
    if (W[1]!='1' || W[N]!='1') {
        cout<<-1<<"\n";
        return;
    }
    ll ans=1,ans_c=1;
    // auto divide_c=[&](ll x) {
    //     while (x!=minp[x]) {
    //         x/=minp[x];
    //         if (opC%minp[x]==0) {
    //             opC/=minp[x];
    //         }
    //     }
    //     if (opC%minp[x]==0) {
    //         opC/=minp[x];
    //     }
    // };
    for (int i=1;i<=N-1;++i) {
        // 尝试往这个序列中插入 i
        if (W[i]=='1') {
            ans*=2;
            ans%=mod;
            ans_c*=2;
            ans_c%=C;
        }else {
            // 要破坏这个计划
            ans*=(i-1);
            ans%=mod;
            ans_c*=i-1;
            ans_c%=C;
        }
    }
    if (ans_c==0) {
        cout<<-1<<"\n";
        return;
    }
    ans%=mod;
    if (ans<0) ans+=mod;
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
1
3 1
111

*/

心路历程（WA，TLE，MLE……）

CF-1075-B. The Curse of the Frog（遇到一个值，可以直接减掉的话最好，避免后续处理）

Posted on 2026-01-24 Edited on 2026-04-06

题目大意：B. The Curse of the Frog

一只青蛙位于数轴的 $0$ 点，目标是到达坐标 $x$ 。青蛙掌握 $n$ 种跳跃技能，每种技能 $i$ 包含三个参数：

$a_i$ ：最大跳跃距离。单次跳跃可从 $k$ 移动到 $[k, k + a_i]$ 范围内的任意整数点。
$b_i$ ：回滚周期。每当第 $b_i, 2b_i, 3b_i \dots$ 次使用该技能时，会触发诅咒。
$c_i$ ：回滚距离。触发诅咒时，青蛙会先从当前位置 $k$ 后退到 $k - c_i$ ，然后再进行跳跃，最终落点范围为 $[k - c_i, k - c_i + a_i]$ 。

目标： 计算到达 $x$ 点所需经历的最小回滚总次数。如果无法到达，则输出 $-1$ 。

样例解释

样例 1

输入： $x=1$ , 技能： $a=3, b=3, c=3$ 。
过程： 第一次使用技能，不触发回滚（因为 $1 < b=3$ ）。直接从 $0$ 跳到 $1$ 。
结果： $0$ 次回滚。

样例 4

输入： $x=8$ , 拥有 $5$ 种技能。其中包含 $(12, 1, 11)$ 和 $(10, 1, 4)$ 等。
过程：
1. 使用第 $1$ 种技能（ $b=1$ ）：触发回滚，从 $0$ 退到 $-11$ ，跳到 $1$ 。
2. 使用第 $4$ 种技能（ $b=2$ ）：这是该技能第 $1$ 次使用，不回滚，从 $1$ 跳到 $2$ 。
3. 使用第 $2$ 种技能（ $b=1$ ）：触发回滚，从 $2$ 退到 $-2$ ，跳到 $8$ 。
结果： 总计 $2$ 次回滚。

样例 6

输入： $x=10$ , 技能： $a=2, b=2, c=1$ 。
过程：
- 第 $1$ 次跳：不回滚， $0 \to 2$ 。
- 第 $2$ 次跳：回滚（第 $b=2$ 次）， $2 \to 1 \to 3$ 。
- 第 $3$ 次跳：不回滚， $3 \to 5$ 。
- 第 $4$ 次跳：回滚（第 $2b=4$ 次）， $5 \to 4 \to 6$ 。
- 以此类推，通过交替回滚逐步前进。
结果： 总计 $3$ 次回滚。

思路讲解

starsilk 的代码。不需要的值，我们其实可以减掉。会清爽一些。

然后最后的这个向上取整除法，可以这样子想，没消耗一个回滚，可以前行多少距离？ $w\gets a\times b-c$ 。这个可以这么看，你先回滚 $-c$ （因为前面的免费步已经用完了），然后可以走 $b$ 步，每步 $a$ 的长度。

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T;
	long long n,x,i,a,b,c,w;
	for(cin>>T;T>0;T--)
	{
		cin>>n>>x;
		w=0;
		for(i=0;i<n;i++)
		{
			cin>>a>>b>>c;
			x-=(b-1)*a;
			w=max(w,a*b-c);
		}
		if(x<=0)cout<<"0\n";
		else if(w==0)cout<<"-1\n";
		else cout<<(x+w-1)/w<<'\n';
	}
	return 0;
}

AC代码

https://codeforces.com/contest/2189/submission/359582687

源代码

/**
 * Problem: B. The Curse of the Frog
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/B
 * Created: 2026-01-23 22:41:09
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
struct Abc {
    ll a,b,c;
};
void Solve() {
    ll N,X;
    cin >> N >> X;
    vector<Abc> abc_vec(N);
    ll mx_w=0;
    for (int i=0;i<N;++i) {
        ll a,b,c;
        cin>>a>>b>>c;
        abc_vec[i]={a,b,c};
        X-=a*(b-1);
        ll w=a*b-c;
        mx_w=max(mx_w,w);
    }
    if (X<=0) {
        cout<<0<<"\n";
        return;
    }
    if (mx_w==0)  {
        cout << -1 << "\n";
        return;
    }
    cout<<(X+mx_w-1)/mx_w<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2189/submission/359582687

*/

心路历程（WA，TLE，MLE……）

CF-1075-C2. XOR-convenience (Hard Version)（打表，错误的时候可以输出错误的地方）（如果说已经构造出来了简单版，复杂版可能也只需要微调）

Posted on 2026-01-24 Edited on 2026-04-06

题目大意

题目总结

问题描述

给定一个正整数 $n$ （ $3 \le n \le 2 \cdot 10^5$ ）。你需要构造一个长度为 $n$ 的排列 $p$ （包含 $1$ 到 $n$ 的所有整数各一次），使得对于每一个 $i$ （ $1 \le i \le n-1$ ），都能在索引范围 $[i, n]$ 中找到一个下标 $j$ （即 $i \le j \le n$ ），满足以下异或条件：

p_i = p_j \oplus i

如果不存在满足条件的排列，则输出 $-1$ 。

输入输出

输入：测试用例数量 $t$ ，每个案例包含一个整数 $n$ 。
输出：若存在，输出 $n$ 个整数表示排列 $p$ ；否则输出 $-1$ 。

样例解释

以 $n=3$ 为例，输出为 2 1 3：

当 $i=1$ 时：需要存在 $j \in \{1, 2, 3\}$ 使得 $p_1 = p_j \oplus 1$ 。
已知 $p_1=2$ ，若取 $j=3$ ，则 $p_3 \oplus 1 = 3 \oplus 1 = 2$ 。满足条件。
当 $i=2$ 时：需要存在 $j \in \{2, 3\}$ 使得 $p_2 = p_j \oplus 2$ 。
已知 $p_2=1$ ，若取 $j=3$ ，则 $p_3 \oplus 2 = 3 \oplus 2 = 1$ 。满足条件。
所有 $i \in [1, 2]$ 均满足条件，故 2 1 3 是合法解。

以 $n=4$ 为例：

不存在任何长度为 $4$ 的排列能满足上述所有约束，故输出 $-1$ 。

思路讲解

这道题目，一种方法是打表找规律，比较神秘，呃，也比较费时间，只不过由于我 C1 是打表打出来的，C2 也这样子尝试了，由于选取的规律比较奇怪，在某些情况下会出现问题，后需要与下标 $\text{lowbit}(n)$ 交换啊什么的，在这里就不介绍了。

不过可以总结一下，就是这种打表找规律的话，首先要确定没有答案的条件，其次就是写的检查器尽量报出更多的信息（在错误时），比如说这道题目，如果你构造出来的序列是错的，你写的检查器最好要报出来哪一位错了，有哪些位构造错误？这一位你填了什么值？反正信息越多越好。

那么构造方法如何解决 C1 呢？那么由于是要求 $p_i = p_j \oplus i$ ，不妨就令 $p_i=i\oplus 1$ ，把 1 放在最后就可以了，最后这样子生成的序列第一位可能有点问题，这个特判一下就行。

那么如果你会解决 C1 的话，其实只需要增加一行代码：

if (N%2==0) {
    ans_ls[1]=N;
    swap(ans_ls[1],ans_ls[lowbit(N)]);
}else {
    ans_ls[1]=N-1;
}

即 swap(ans_ls[1],ans_ls[lowbit(N)]); 这一行代码。首先 $\text{lowbit}(n)\oplus 1$ 肯定不愁找不到满足的 $j$ ，因为他都处于第一个位置了。那么对于 $n$ 呢？那么由于 $n≥n\oplus \text{lowbit}(n)≥\text{lowbit}(n)+2$ （ $n$ 是偶数），所以说也不用愁找不到 $j$ 。

当然，注意， $n$ 是 2 的幂次的时候是没有答案的，这也很容易理解，因为这个时候 $n$ 无论异或上 $[1,n]$ 中的任何一个数字，其结果都超过了 $[1,n]$ 的范围。

AC代码

AC
https://codeforces.com/contest/2189/submission/359568527

源代码（构造）

/**
 * Problem: C2. XOR-convenience (Hard Version)
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/C2
 * Created: 2026-01-24 14:18:16
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
ll lowbit(ll x) {
    return x&-x;
}

void Solve() {
    ll N;
    cin >> N;
    if (has_single_bit((unsigned)N)) {
        cout<<-1<<"\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    for (int i=2;i<=N-1;++i) {
        ans_ls[i]=i^1;
    }
    ans_ls[N]=1;
    if (N%2==0) {
        ans_ls[1]=N;
        swap(ans_ls[1],ans_ls[lowbit(N)]);
    }else {
        ans_ls[1]=N-1;
    }

    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2189/submission/359568527

*/

AC
https://codeforces.com/contest/2189/submission/359512601

源代码（打表找规律）

/**
 * Problem: C2. XOR-convenience (Hard Version)
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/C2
 * Created: 2026-01-24 14:37:06
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
ll lowbit(ll x) {
    return x&-x;
}

void Solve() {
    ll N;
    cin >> N;
    if (has_single_bit((unsigned)N)) {
        cout<<-1<<"\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    if (N&1) {
        ans_ls[1]=N-1;
        ans_ls[N]=1;
        queue<ll> q_ji,q_ou;
        for (int i=2;i<=N-2;++i) {
            if (i&1) {
                q_ji.push(i);
            }else {
                q_ou.push(i);
            }
        }
        q_ji.push(N);
        for (int i=2;i<=N-1;++i) {
            if (i&1) {
                ll num=q_ou.front();
                q_ou.pop();
                ans_ls[i]=num;
            }else {
                ll num=q_ji.front();
                q_ji.pop();
                ans_ls[i]=num;
            }
        }
    }else {
        /*
        4 1 5 | 2 6 3
        6 一共输出了 1 个序列
        */
        // if (N==6) {
        //     cout<<"4 1 5 2 6 3\n";
        //     return;
        // }
        auto mirror_assign=[&](ll i) {
            ans_ls[N+1-i]=N+1-ans_ls[i];
        };
        if (N%4!=0) {
            ans_ls[1]=N-2;
            ans_ls[N]=3;
            ans_ls[N-1]=N;
            ans_ls[2]=1;
            ans_ls[3]=N-1;
            ans_ls[N-2]=N+1-ans_ls[3];
            ll cnt=1;
            vector<array<ll,2>> num_ls(N/2+2);
            ll idx=1;
            for (int i=4;i<=N;i+=2) {
                num_ls[idx]={i,i+1};
                ++idx;
            }
            for (int i=4;i<=N/2;i+=2) {
                if (cnt&1) {
                    ans_ls[i]=num_ls[cnt+1][0];
                    ans_ls[i+1]=num_ls[cnt+1][1];
                }else{
                    ans_ls[i]=num_ls[cnt-1][0];
                    ans_ls[i+1]=num_ls[cnt-1][1];
                }
                mirror_assign(i);
                mirror_assign(i+1);
                ++cnt;
            }
        }else {
            /*
            10 5 4 12 2 7 | 6 11 1 9 8 3
            12 一共输出了 2 个序列
            18 5 4 20 2 7 6 9 8 11 | 10 13 12 15 14 19 1 17 16 3
            26 5 4 28 2 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 27 1 25 24 3
         WA:22 5 4 24 2 7 6 9 8 11 10 13 | 12 15 14 17 16 19 18 23 1 21 20 3
             */
            ans_ls[1]=N-2;
            mirror_assign(1);
            ans_ls[2]=5;
            mirror_assign(2);
            ans_ls[3]=4;
            mirror_assign(3);
            ans_ls[4]=N;
            mirror_assign(4);
            ans_ls[5]=2;
            mirror_assign(5);
            ans_ls[6]=7;
            mirror_assign(6);
            ll cnt=6;
            for (int i=7;i<=N/2;i+=2) {
                ans_ls[i]=cnt;
                mirror_assign(i);
                ans_ls[i+1]=cnt+3;
                mirror_assign(i+1);
                cnt+=2;
            }
            ll lb=lowbit(N);
            if (lb>=8) {
                swap(ans_ls[4],ans_ls[8]);
            }
            if (lb>8) {
                swap(ans_ls[8],ans_ls[lb]);
            }
        }

    }
    // #undef LOCAL
#ifndef LOCAL
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
#else
    bool ok_zong=true;
    for (int i=1;i<=N-1;++i) {
        bool ok=false;
        for (int j=i;j<=N;++j) {
            if ((ans_ls[j]^(i))==ans_ls[i]) {
                ok=true;
                break;
            }
        }
        if (!ok) {
            ok_zong=false;
            break;
        }
    }
    if (ok_zong) {
        for (int i=1;i<=N;++i) {
            cout<<ans_ls[i]<<" ";
        }
        cout<<"\n";
        return;
    }
    cout<<"WA:";
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
        if (i==N/2) {
            cout<<"| ";
        }
    }
    cout<<"\n";
#endif
    
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2189/submission/359512601

*/

打表程序

/**
 * Problem: ${PROBLEM_NAME}
 * Contest: ${PROBLEM_GROUP_NAME}
 * Judge: ${ONLINE_JUDGE_NAME}
 * URL: ${PROBLEM_URL}
 * Created: 2026-01-24 10:48:47
 * Author: Gospel_rock
 */

#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

void Solve() {
    ll N;
    cin >> N;
    vector<char> used(N+2);
    vector<ll> P(N+2);
    ll cnt=0;
    auto dfs=[&](auto && self,ll idx) {
        if (idx==N) {
            ++cnt;
            P[N]=3;
            for (int i=1;i<=N;++i) {
                cout<<P[i]<<" ";
                if (i==N/2) cout<<"| ";
            }
            cout<<"\n";
            return;
        }
        if (idx<=N/2) {
            for (int v=1;v<=N;++v) {
                if (idx==1 && v!=N-2) continue;
                // if (idx>N/2 && v!=N+1-P[N+1-idx]) continue;
                if (used[v]) continue;
                ll target=v^idx;
                if (target>=1 && target<=N && !used[target]) {
                    used[v]=true;
                    P[idx]=v;
                    self(self,idx+1);
                    used[v]=false;
                }
            }
        }else {
            for (int v=N+1-P[N+1-idx];v<=N+1-P[N+1-idx];++v) {
                if (used[v]) continue;
                ll target=v^idx;
                if (target>=1 && target<=N && !used[target]) {
                    used[v]=true;
                    P[idx]=v;
                    self(self,idx+1);
                    used[v]=false;
                }
            }
        }

    };
    dfs(dfs,1);
    cout<<N<<" "<<"一共输出了 "<<cnt<<" 个序列\n";
    cout<<"\n---------------------------------\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）

CF-1073-F. Prufer Vertex（对于零散的图，计数可以从联通块角度考虑）（使用概率来计数）

Posted on 2026-01-22 Edited on 2026-04-06

题目大意

题目总结：F. Prufer Vertex

1. Prufer 顶点 $P(T)$ 的定义

对于一棵拥有 $n \ge 2$ 个节点的树 $T$ ，按照以下标准过程生成 Prufer 序列：

重复寻找当前树中编号最小的叶子节点并将其删除。
直到树中只剩下最后 2 个节点。
已知节点 $n$ 必然是最后剩下的两个节点之一，设另一个剩下的节点为 $v$ ，则定义该树的 Prufer 顶点 $P(T) = v$ 。

2. 问题描述

给定一个含有 $n$ 个顶点和 $m$ 条边的森林。假设该森林有 $k$ 个连通块，其大小分别为 $s_1, s_2, \dots, s_k$ 。

已知将该森林添加 $k-1$ 条边使其成为一棵树的方案总数为：

n^{k-2} \prod_{i=1}^{k} s_i

任务： 对于每一个 $v$ ( $1 \le v < n$ )，计算在所有可能的加边成树方案中，满足 $P(T) = v$ 的方案数量。

3. 输出要求

输出 $n-1$ 个整数，第 $i$ 个整数表示满足 $P(T) = i$ 的方案数，结果对 $998244353$ 取模。

样例解释（以样例 1 为例）：

输入 $n=3, m=0$ ，森林由三个孤立点 $\{1, 2, 3\}$ 组成。补全为树的方案共有 $3^{3-2} \cdot (1 \cdot 1 \cdot 1) = 3$ 种：

添加边 (1,2) 和 (1,3)： 叶子节点为 2 和 3。最小叶子 2 被删除，剩余 $\{1, 3\}$ 。故 $P(T)=1$ 。
添加边 (2,1) 和 (2,3)： 叶子节点为 1 和 3。最小叶子 1 被删除，剩余 $\{2, 3\}$ 。故 $P(T)=2$ 。
添加边 (3,1) 和 (3,2)： 叶子节点为 1 和 2。最小叶子 1 被删除，此时 2 变为叶子，删除 2，剩余 $\{3\}$ 与另一节点（在此情况下 Prufer 过程最后剩下的非 $n$ 节点为 2）。

最终输出：1 2（代表 $P(T)=1$ 有 1 种， $P(T)=2$ 有 2 种）。

思路讲解

我们阐述一下题意，叶子在无根树树中应该就是指的是度为 1 的点（虽然给的是森林，不过我们最后都会连成树），样例 1 的答案生成过程如图所示：

我们发现，只要一个点，是只和最大点相连的点（最大点和该点连接且仅和该点连接），那么这个点一定可以被保下来。因为这个点，是最后成为这个叶子节点的。原因：反证法，如果比较早把这个点删除了，那么最大点就变为孤零零一个人了，这显然是不可能的。

那么更进一步的推论就是，答案一定是和最大点直接相连的点。不过，虽然我们知道了答案是和最大点直接相连的点，但是我们不太清楚，到底是哪个点。

我们进行一个猜测，就是以这个点为根的子树，其内部的最大点，是所有的子树中最大的（即其他子树中的最大点，都比这颗子树小）。这样子，在删除这个内部最大点之前，我们会把其他子树全部删除，最后就只剩一颗子树了，结果就确定了。

当然，这个所谓的内部最大点，就是次大值 $n-1$ 啦，以 $n$ 为根， $n-1$ 所在的子树的根就是所能留下来的点。

不过现在的难点就来到了这个统计答案。

从 $n-1$ 的特殊情况看起，我们发现，如果 $n-1$ 已经连接在了 $n$ 的联通块上，且 $n-1$ 与 $n$ 之间未直接相连，此时答案为 0。如果直接相连，那么其实其他连通块要连接到 $n$ 的连通块上，这个要怎么算呢？我们不妨参考一下题目中的这个式子。

给定一个含有 $n$ 个顶点和 $m$ 条边的森林。假设该森林有 $k$ 个连通块，其大小分别为 $s_1, s_2, \dots, s_k$ 。已知将该森林添加 $k-1$ 条边使其成为一棵树的方案总数为：

n^{k-2} \prod_{i=1}^{k} s_i

实际上这个式子是凯莱公式的推论？

我们先来看一下凯莱公式吧，凯莱公式即：

其证明方法有：

呃😅，那我们还是用这个 prufer 序列吧，其实 prufer 序列就是把题目中描述的删点过程：每次我们记录一下这个我们删的点的父节点，得到的就是长度为 $n-2$ 的 prufer 序列。这个序列有 $n^{n-2}$ 种选择，由于每颗生成树对应的 prufer 序列显然是唯一的，prufer 序列也唯一对应一颗生成树，因此生成树的数量就是 $n^{n-2}$ （这个说的比较粗糙，只是引入一下 prufer 序列这个工具，帮助后面我们的这个理解）。

那么这个连通块的式子是怎么来的？

首先从 prufer 序列的角度来看，那么由于其中的每个点，都可以作为长度为 $k-2$ 的 prufer 序列中的点，所以就是 $n^{k-2}$ ，那么由于每个连通块还需选出来一个代表点连接，因此是：

n^{k-2} \prod_{i=1}^{k} s_i

可以想象， $n^{k-2}$ 代表了这个接收端， $\prod_{i=1}^{k} s_i$ 代表了这个发送端。不过还有一个特例，就是没有被 prufer 序列覆盖的根连通块的这个贡献也包含在了这个 $\prod_{i=1}^{k} s_i$ 当中。换句话说，一个长度为 $k-2$ 的 prufer 序列的贡献是 $\prod_{i=1}^{k} s_i$ **，原因在于你要确定所有非根连通块的发送端****（**这个是固定的，只有一个的，否则会成环），还要确定根连通块的接收端（在 prufer 中未体现）（严格来讲是最后一个被删除的块所连接的这个根连通块的接收点）。

哎，我们回来看题目：

我们之前所说的结论：

以 $n$ 为根， $n-1$ 所在的子树的根就是所能留下来的点

说明， $n-1$ 连接在 $i$ 的子树下，是必要条件，是必须满足的。

你就抓住这个，进行分类讨论即可，因为太过细节，这里就不展开了。

然后，你会发现答案不对。

_______________[ Sample Testcase #1 OUTPUT]_______________
1 2
0 0 0 1
10 0 1 5 5

这道题目的难点，特别是计数难点在于，如何去解决一些先 $k$ 连通块连上 $i$ 的子树，然后 $n-1$ 再连上 $k$ 连通块去的这个情况（或者更加复杂情况下的计数）。

具体而言，我们以样例 3 的这个第一个计数为例：

但是这个计数问题我们怎么解决？

我们用算概率的方式，得到这个答案，具体而言：

为什么我们可以使用算概率的方式呢？实际上， $n-1$ 连接到 $1$ 的子树的概率就是 $\frac{1}{2}$ ，无论他是通过 $3$ 连接，还是不通过 $3$ 连接，都是这个概率。这个概率就起到了相当于抽丝剥茧，剥开重重迷雾的作用。

AC代码

https://codeforces.com/contest/2191/submission/360174534

源代码

/**
 * Problem: F. Prufer Vertex
 * Contest: Codeforces Round 1073 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2191/problem/F
 * Created: 2026-01-22 13:22:57
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <string>
#include <cstring>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

#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 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 LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 2e5 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

/**   并查集（DSU）
 *    2023-08-04: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63239142 (base on jiangly)
 *    2025-11-08: https://frp-shy.com:32768/domjudge/team H题 增加dsu on next，标记区间l，r的功能
 *    为了适配这个dsu on next，对merge 函数合并方向进行了修改。
 *    2025-12-05：https://codeforces.com/contest/2171/submission/351963922
 *    增加了 countFa 功能
 *    2025-12-23：移除了宏定义，增加功能说明模块。
 *    功能说明：dsu on next，find(x)，就是在 x 之后第一个没有被标记的数字
 *    该 dsu 传入构造函数的这个大小，需要是 n 就是 n，如果你不希望 countFa 出错的话。
**/
struct DSU {
    vector<int> fa, siz;
    ll n;

    DSU() {
    }

    DSU(ll n): n(n) {
        init(n + 5);
    }

    void init(ll n) {
        fa.resize(n);
        for (int i = 0; i < SZ(fa); ++i) {
            fa[i] = i;
        }
        siz.assign(n, 1);
    }

    ll find(ll x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(ll x, ll y) {
        return find(x) == find(y);
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[y] += siz[x];
        fa[x] = y;
        return true;
    }

    ll size(ll x) {
        return siz[find(x)];
    }

    // dsu on next 技巧，直接标记 [l,r] 这段区间
    // 标记就是指让[l,r]这段区间里的所有数字这个都不指向自己
    // 可以理解为指向 r+1
    void taglr(ll l, ll r) {
        l = max(0ll, l);
        r = min(SZ(fa) - 2, r);
        l = find(l);
        while (l <= r) {
            merge(l, l + 1);
            l += 1;
            l = find(l);
        }
    }

    ll countFa() {
        ll res = 0;
        for (int i = 1; i <= n; ++i) {
            if (fa[i] == i) {
                ++res;
            }
        }
        return res;
    }
};

// 在 k<=0 的时候返回 1
ll binpow(ll a, ll k, const ll &p = mod) {
    ll res = 1;
    a %= p;
    while (k > 0) {
        if ((k & 1) == 1) res = a * res % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<vector<ll> > g(N + 2);
    DSU fa(N);
    DSU without_edge_to_n_fa(N);
    map<ll, map<ll, bool> > u_to_v_mp;
    for (int i = 1; i <= M; ++i) {
        ll u, v;
        cin >> u >> v;
        u_to_v_mp[u][v] = true;
        u_to_v_mp[v][u] = true;
        // g[u].push_back(v);
        // g[v].push_back(u);
        fa.merge(u, v);
        if (u != N && v != N) {
            without_edge_to_n_fa.merge(u, v);
        }
    }
    ll mx_node_connect_to_n = 0;
    for (auto it: u_to_v_mp[N]) {
        mx_node_connect_to_n = max(mx_node_connect_to_n, it.first);
    }
    bool n_to_n_1 = u_to_v_mp[N].contains(N - 1);
    ll s_prod = 1;
    vector<char> vis_connect(N + 2);
    for (int i = 1; i <= N; ++i) {
        ll pa = fa.find(i);
        if (vis_connect[pa]) {
            continue;
        }
        vis_connect[pa] = true;
        s_prod *= fa.size(i);
        s_prod %= mod;
    }
    ll k_cntFa = fa.countFa();
    auto cal_ans = [&](ll k_rem_connect, vector<ll> divide_ls, bool iscal_sum = false)-> ll {
        if (k_rem_connect <= 1) return 1;
        if (iscal_sum) {
            // 计算总单答案，直接使用该式子计算即可
            ll res = s_prod * binpow(N, k_rem_connect - 2);
            res %= mod;
            return res;
        }
        ll multiple = accumulate(all(divide_ls), 0ll);
        ll op_s_prod = s_prod;
        for (auto divide: divide_ls) {
            op_s_prod *= binpow(divide, mod - 2);
            op_s_prod %= mod;
        }
        op_s_prod *= multiple;
        op_s_prod %= mod;
        ll res = binpow(N, k_rem_connect - 2) * op_s_prod % mod;
        if (res < 0) res += mod;
        return res;
    };
    // 我们下面再开一个答案计算函数，有点屎山，但是也没办法
    auto cal_ans2 = [&](ll k_rem_connect, vector<ll> divide_ls,ll sz_i_subtree,
        ll sz_n_component)-> ll {

        if (k_rem_connect <= 1) return 1;
        ll multiple = accumulate(all(divide_ls), 0ll);
        ll op_s_prod = s_prod;
        for (auto divide: divide_ls) {
            op_s_prod *= binpow(divide, mod - 2);
            op_s_prod %= mod;
        }
        op_s_prod *= multiple;
        op_s_prod %= mod;
        ll res = binpow(N, k_rem_connect - 2) * op_s_prod % mod;
        res*=sz_i_subtree;res%=mod;
        res*=binpow(sz_n_component,mod-2);res%=mod;
        if (res < 0) res += mod;
        return res;
    };
    for (int i = 1; i <= N - 1; ++i) {
        if (i == N - 1) {
            if (n_to_n_1) {
                // 总答案这样子计算有问题
                // ll ans=binpow(N,k_cntFa-2)*s_prod;
                ll ans = cal_ans(k_cntFa, {}, true);
                cout << ans << " ";
                continue;
            }
            if (fa.same(N, N - 1)) {
                cout << 0 << " ";
                continue;
            }
            ll ans = cal_ans(k_cntFa - 1, {fa.size(i), fa.size(N)});
            cout << ans << " ";
        } else {
            if (n_to_n_1) {
                cout << 0 << " ";
                continue;
            }
            // 处于同一连通块下
            if (fa.same(N, i)) {
                if (u_to_v_mp[N].contains(i)) {
                    if (fa.same(N - 1, N)) {
                        // N-1 已经在 i 的子树上，已经稳了，剩下的点随便怎么连接
                        if (without_edge_to_n_fa.same(N - 1, i)) {
                            // 就是直接计算总答案
                            ll ans = cal_ans(k_cntFa, {}, true);
                            cout << ans << " ";
                        } else {
                            // N-1 在 N 连通块，但是不在 i 的子树上，直接宣判死刑
                            cout << 0 << " ";
                        }
                    } else {
                        // N 和 i 直接相连
                        // 需要把 N-1 所在联通块连上 i 的子树
                        // 总共答案就是把这个 i 和 N-1连上以后的总答案，乘以 i 的子树大小
                        ll ans = cal_ans2(k_cntFa,{1},without_edge_to_n_fa.size(i),fa.size(N));
                        ans %= mod;
                        cout << ans << " ";
                    }
                } else {
                    // i 和 N 处于同一连通块的时候而且未直接相连，答案为 0。
                    cout << 0 << " ";
                    continue;
                }
            } else {
                if (fa.same(N, N - 1)) {
                    cout << 0 << " ";
                    continue;
                }
                ll ans;
                // 这里这个分类讨论，最开始的程序漏了
                if (fa.same(N-1,i)) {
                    ans=cal_ans(k_cntFa-1,{fa.size(i),fa.size(N)});
                }else {
                    // 我们现在必须要把这个 N-1连接到这个 i 上面（即 i 的子树，连通块上面）
                    ans = cal_ans2(k_cntFa - 1, {fa.size(i),fa.size(N)},
                        fa.size(i),fa.size(i)+fa.size(N));
                }
                cout << ans << " ";
            }
        }
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*
1
3 0

_______________[ Sample Testcase #1 OUTPUT]_______________
1 2
0 0 0 1
10 0 1 5 5

AC
https://codeforces.com/contest/2191/submission/360174534

*/

心路历程（WA，TLE，MLE……）

$n-1$ 的答案是：
- 如果 $n$ 与 $n-1$ 直接相连，答案就是 $n^{k-2} \prod_{i=1}^{k} s_i$ 。如果不直接相连，还处于同一联通块，那么答案是 0。那么最后一种更普遍的情况，就是 $n$ 与 $n-1$ 处于两个连通块，这个时候就将 $n$ 与 $n-1$ 连接在一起，形成的新的森林，用上面那个公式计算即可。
更加普遍的情况下， $i$ 的答案是：
- $i$ 与 $n$ 处于相同连通块：
- $i$ 与 $n$ 处于不同连通块：
  我们之前所说的结论：

以 $n$ 为根， $n-1$ 所在的子树的根就是所能留下来的点
说明， $n-1$ 连接在 $i$ 的子树下，是必要条件，是必须满足的。