昨晚 CF D
2026-07-27 09:41:14
发布于：广东
39阅读
0回复
0点赞
什么叫我过了 ABD？什么叫 C 过题人数是 D 5 倍？
由于是排列，所以有一个很好的性质： 会出现恰好一次。
所以对于每一个位置，它左边和右边恰好有一个最大值是 ， 就是另一边的最大值。显然 在 左侧时 单调不减，在右侧时 单调不增；。
假设 的位置已经确定，我们统计答案。
假设 ，。
显然， 更新一定是因为 的前缀 / 后缀最大值变大了，而这种情况只有 。所以所有 相同的块最左边 / 右边的答案就确定了。那么目前已知的 为 。
块内其它答案呢？显然可以随便填，只要小于 即可。所以所有可能的 有 。
这是个简单数数问题，用求排列数即可。注意，如果 两端有 相同的块，那么就会出现两个 相同，不合法。
现在我们确定 的位置。
观察样例，可以看出所有情况的 似乎都在 块两侧。
证明：
- 当 不在 的块中时，显然不符合“ 在 左侧时 单调不减，在右侧时 单调不增”的性质。
- 当 在 的块中但不是两端时，注意到 左右两端都有一个 ，不符合刚刚的讨论。
而且这两种情况的确定的其它数的位置一定相同，所以答案直接 即可。
namespace cjdst{
const ll N = 1000000, mod = 998244353;
ll frac[N + 5], invfrac[N + 5];
ll ksm(ll x, ll y){
ll ans = 1;
while(y){
if(y & 1) ans = x * ans % mod;
x = x * x % mod, y >>= 1;
}
return ans;
}
void init(){
frac[0] = 1;
for(int i = 1; i <= N; i++){
frac[i] = frac[i - 1] * i % mod;
}
invfrac[N] = ksm(frac[N], mod - 2);
for(int i = N - 1; i >= 0; i--){
invfrac[i] = invfrac[i + 1] * (i + 1) % mod;
}
}
ll A(ll n, ll m){
if(n < m) return 0;
if(m < 0) return 1;
return (frac[n] * invfrac[n - m] % mod);
}
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i < n; i++){
std::cin >> a[i];
}
ll cur = std::max_element(a.begin() + 1, a.begin() + n + 1) - a.begin();
if(a[cur] != n - 1){
std::cout << "0\n";
return;
}
std::vector <int> bucket(n + 5), bucket2(n + 5);
for(int i = 1; i < cur; i++){
if(a[i] < a[i - 1]){
std::cout << "0\n";
return;
}
bucket2[a[i]] = 1;
bucket[a[i]]++;
}
for(int i = cur + 1; i < n; i++){
if(a[i] < a[i + 1] || (a[i] != n - 1 && bucket2[a[i]])){
std::cout << "0\n";
return;
}
bucket[a[i]]++;
}
ll ans = 2, cnt = 0;
for(int i = 1; i < n; i++){
cnt++;
ans = ans * A(cnt - 1, bucket[i] - 1) % mod;
cnt -= bucket[i];
}
std::cout << ans << '\n';
}
}
时间复杂度：。
有帮助，赞一个