这是一道非常有意思的题。
设 \(n\) 为当前队伍数量。
下面对于每个队伍的“数值”不是编号,而是能力。(比如说这时编号为 \(1\) 的队伍能力为 \(n\))。
思路清晰的,我们发现在初始状态下,每两格一组,每组之间是互相独立的。然后我们当前已经确定了一些队伍的位置,只知道这些发现很难去计算答案,因为这一次竞选完的队伍之后还有顺序要求,所以我们得到的性质仍然不够。
经过观察就会发现,每一组只可能有一个能力小于等于 \(\frac{n}{2}\) 和一个能力大于 \(\frac{n}{2}\) 的队伍组成。更重要的是,这一轮小于等于 \(\frac{n}{2}\) 的队伍无论顺序怎么变都不会影响下一轮,并且直接到下一轮剩下的队伍的数量会减少一半!这提醒我们可以用类似于递归的方法解决问题。
我们设一个函数,\(f(a)\) 表示当前编号数组为 \(a\) 的安排位置方案,那么考虑一个转移:
\[f(a)=t\times f(a') \]其中 \(t\) 为转移系数,先想办法求 \(a'\),考虑 \(a'\) 的每一位,如果 \(a_{2i}\) 或者 \(a_{2i+1}\) 大于 \(\frac{n}{2}\),那么显然已经确定,我们给每一个确定的队伍重新分配一个“相对”能力,具体实现可以自己想。反之这一位没有确定,就把 \(-1\) 传下去。 当然了,如果每一组内的队伍能力都小于等于 \(\frac{n}{2}\) 或者都大于 \(\frac{n}{2}\) 显然无解。
接着想办法求转移系数,实际上就是当前这一轮要被淘汰的队伍的位置方案,其实比较好求,设 \(tot\) 表示两个队伍都没有确定能力的组数,\(k\) 表示可以自由分配位置的要被淘汰的队伍数量,那么 \(t=k!\times2^{tot}\)。因为完全没有确定的组相当于有 \(2\) 个位置都可以放。
接下来就是实现问题,运用乘法交换律,发现不需要真的去递归,直接循环就可以了。
代码:
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define rrp(i, l, r) for(int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
using namespace std;
constexpr int N = 6e5 + 5, P = 998244353;
typedef long long ll;
inline int rd ()
{
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int n, m, a[N], b[2][N];
int fac[N], inv[N];
int qpow (int x, int y)
{
int ret = 1;
for (; y; y >>= 1, x = x * x % P)
if (y & 1) ret = ret * x % P;
return ret;
}
void add (int &x, int y) { (x += y) >= P && (x -= P); }
int A (int n, int m) { return fac[n] * inv[n - m] % P; }
auto main () -> signed
{
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
m = rd (); n = 1ll << m; rep (i, 1, n) a[i] = b[0][i] = rd ();
rep (i, 1, n) if (b[0][i] < 0) b[0][i] = 1e9; else b[0][i] = n - b[0][i] + 1;
fac[0] = 1;
rep (i, 1, n) fac[i] = fac[i - 1] * i % P;
inv[n] = qpow (fac[n], P - 2); inv[0] = 1;
rrp (i, 1, n - 1) inv[i] = inv[i + 1] * (i + 1) % P;
int ret = 1, p = 0; while (n > 1)
{
int Mi = n >> 1, tot = 0, sum = Mi;
rep (i, 2, n) if (b[p][i] <= Mi && b[p][i - 1] <= Mi)
return puts ("0"), 0; else ++ i;
rep (i, 2, n)
if (b[p][i] < 1e9 && b[p][i - 1] < 1e9)
if (b[p][i] > Mi && b[p][i - 1] > Mi) return puts ("0"), 0;
else ++ i; else ++ i;
int tmp = 1; rep (i, 1, n) tot += (b[p][i] <= Mi); rep (i, 1, n) {
++ i; if (b[p][i] >= 1e9 && b[p][i - 1] >= 1e9) add (tmp, tmp);
} ret = (ret * tmp % P * fac[Mi - tot] % P);
rep (i, 1, Mi)
{
b[p ^ 1][i] = max (b[p][(i << 1) - 1], b[p][i << 1]);
if (b[p ^ 1][i] >= 1e9)
{
if (b[p][(i << 1) - 1] < 1e9 && b[p][(i << 1) - 1] > Mi)
b[p ^ 1][i] = b[p][(i << 1) - 1];
if (b[p][i << 1] < 1e9 && b[p][i << 1] > Mi)
b[p ^ 1][i] = b[p][i << 1];
} if (b[p ^ 1][i] < 1e9) b[p ^ 1][i] -= Mi;
} p = ! p; n >>= 1;
} printf ("%lld\n", ret);
}
标签:ch,frac,int,Mi,ret,队伍,CF1837E
From: https://www.cnblogs.com/lalaouyehome/p/17806424.html