Submission #2693993

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll M = 1e9 + 7;
const int N = 100100;

ll binpow(ll a, ll p) {
    ll s = 1;
    while (p) {
        if (p & 1) {
            s = s * a % M;
        }
        a = a * a % M;
        p >>= 1;
    }
    return s;
}

ll f[N], finv[N];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
    }
    f[0] = finv[0] = 1;
    for (int i = 1; i <= n + 1; ++i) {
        f[i] = f[i - 1] * i % M;
        finv[i] = binpow(f[i], M - 2);
    }
    vector<ll> ans(n + 1);
    for (int i = 0; i <= n; ++i) {
        ans[i] = f[n + 1] * finv[i + 1] % M * finv[n - i] % M;
    }
    vector<int> pos[N];
    for (int i = 0; i <= n; ++i) {
        pos[a[i]].push_back(i);
    }
    int l, r;
    for (int i = 1; i <= n; ++i) {
        if (pos[i].size() == 2) {
            l = min(pos[i][0], pos[i][1]);
            r = max(pos[i][0], pos[i][1]);
        }
    }
    int x = l + n - r;
    for (int i = 0; i <= n; ++i) {
        if (x >= i) {
            ans[i] -= f[x] * finv[i] % M * finv[x - i] % M;
        }
        ans[i] = (ans[i] + M) % M;
    }
    for (int i = 0; i <= n; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Submission Info

Judge Result