Cod sursa(job #3267357)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 11 ianuarie 2025 11:06:02
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 5;

int n, a, b, c, v[N], fact[N], inv[N];

int binpow(int baza, int exp) {
    if(!exp)
        return 1;
    int p = binpow(baza, exp/2);
    if(exp & 1)
        return p * p % n * baza % n;
    return p * p % n;
}

struct union_find {
    int dad[N], sz[N], r[N];

    void build() {
        for(int i=1; i<=n; i++)
            dad[i] = i, sz[i] = 1, r[i] = i;
    }
    int get(int x) {
        if(x == dad[x])
            return x;
        return dad[x] = get(dad[x]);
    }
    void join(int x, int y) {
        int dx = get(x), dy = get(y);
        if(dx != dy) {
            if(sz[dx] > sz[dy])
                swap(dx, dy);
            dad[dx] = dy;
            sz[dy] += sz[dx];
            r[dy] = max(r[dy], r[dx]);
        }
    }
} dsu;

int32_t main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> n >> a >> b >> c;
    fact[0] = 1;
    for(int i=1; i<n; i++)
        fact[i] = fact[i-1] * i % n;
    inv[n-1] = binpow(fact[n-1], n-2);
    for(int i=n-2; i>=0; i--)
        inv[i] = inv[i+1] * (i + 1) % n;

    dsu.build();
    a = a * fact[n-1] % n;
    b = b * fact[n-1] % n;
    c = c * fact[n-1] % n;
    for(int i=n-1; i>=1; i--) {
        for(int i=a; i<=b; i++) {
            if(!v[i])
                v[i] = c;
            dsu.join(i, a);
            int lmao = dsu.get(i);
            i = dsu.r[lmao];
        }

        a = a * inv[i] % n * fact[i-1] % n;
        b = b * inv[i] % n * fact[i-1] % n;
        c = c * inv[i] % n * fact[i-1] % n;
    }

    for(int i=1; i<n; i++)
        cout << v[i] << '\n';
    return 0;
}