[Algo Beat Contest 001 C] Creating a Queue 官方题解

· · 题解

这题放在 C 确实有点难了。

我们发现这个对序列的要求比较复杂，可以考虑如何转化成简单的形式。

用我们惊人的观察力，可以发现一个特别重要的性质：一个序列满足条件，当且仅当序列中没有重复的数。

证明：反证法，假设存在重复的数，设相隔最近的两个相同的数的下标分别为 i 和 j，其中 i<j。那么，子数组 A_{i},A_{i+1},\dots,A_{j} 中 A_i 和 A_j 显然是唯一众数。

那么，这道题就很简单了。设已经有 a 个数被用过了，还有 b 个位置没有用过，那么答案即为 \prod\limits_{i=a}^{a+b-1}(M-i) \bmod 1145141923，即每次乘上还没有用过的数的数量。

需要特判 N>M 和序列中本身就有重复的数的情况。

时间复杂度：O(N)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6, MOD = 1145141923;
int N, M;
bool A[MAXN + 5];
unordered_map<int, bool> mp;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    if (M < N) {
        cout << "0\n";
        return 0;
    }
    int cnt = 0;
    for (int i = 1, u; i <= N; i++) {
        cin >> u;
        A[i] = (u >= 1);
        if (A[i]) {
            if (mp[u]) {
                cout << "0\n";
                return 0;
            }
            mp[u] = 1;
            cnt++;
        }
    }
    ll ans = 1;
    for (int i = 1; i <= N; i++) {
        if (!A[i]) {
            (ans *= M - cnt) %= MOD;
            cnt++;
        }
    }
    cout << ans << '\n';
    return 0;
}