P3745 [六省聯考 2017] 期末試験

m 種の試験があり、各試験 i は第 b_i 日に成績が発表される予定である。n 人の学生が成績を待っている。学生 i は第 t_i 日までにすべての成績を知りたいと思っている。最終的に最も遅く成績が出る試験の日を T とする。以下の3種類の不快度が生じる。

• 各学生は C × max(T - t_i, 0) の不快度を負担する。
• 試験 x を1日遅らせて試験 y を1日前倒しにする操作には不快度 A がかかる。
• 試験 x を1日前倒しにする操作には不快度 B がかかる。

最小の不快度を求めよ（1 ≤ n, m, t_i, b_i ≤ 10⁵, 0 ≤ A, B, C ≤ 10⁵）。

調整後の T は元の T 以下であり、T ≤ 10⁵ であることから、可能なすべての T についてコストを計算し、最小値を求める戦略が有効である。特定の T へ調整する際には、「前倒し」が必要な科目と「遅延可能」な科目がある。このとき、貪欲法で最適な操作を決定できる。

もし B < A なら、前倒し操作のみを用いればよい。必要前倒し日数が x ならば、コストは Bx となる。一方、A < B ならば、遅延可能な科目を最大限活用すべきである。前倒しが必要日数が x、遅延可能日数が y ならば、コストは A × min(x, y) + B × max(0, x - y) となる。

これらの値を効率的に更新するために、b_i と t_i をソートし、指標を用いて範囲内の科目数を管理する。各 T に対して、前倒し・遅延可能な科目数を均摊 O(1) で更新できる。

また、学生による不快度も同様に動的更新可能。学生の t_i が昇順に並んでおり、そのうち成績待ちが終了する人数を指標で管理することで、不快度の変化量を即時計算できる。

全体の時間計算量は O(n + m + max(t_i)) となり、実装も簡潔にできる。

#include <cstdio>
#include <algorithm>
const int N = 1e5 + 10;
typedef long long ll;

int a[N], b[N], A, B, C, n, m;
int main() {
    scanf("%d%d%d%d%d", &A, &B, &C, &n, &m);
    ll ans = 1e18;

    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= m; ++i) scanf("%d", b + i);

    std::sort(a + 1, a + n + 1);
    std::sort(b + 1, b + m + 1);

    ll res = 0, need = 0, now = 0, add;
    int pos_a = n, pos_b = m;

    while (pos_b >= 1 && b[pos_b] == b[m]) --pos_b;
    for (int i = 1; i < m; ++i) res += (b[m] - b[i]);
    for (int i = 1; i <= n; ++i) {
        if (a[i] >= b[m]) { pos_a = i - 1; break; }
        now += (ll)C * (b[m] - a[i]);
    }

    ans = std::min(ans, now);

    for (int i = b[m] - 1, cnt; i >= 1; --i) {
        cnt = 0;
        while (pos_b >= 1 && b[pos_b] == i) --pos_b, ++cnt;
        res -= pos_b + cnt;
        need += m - pos_b - cnt;

        if (A < B && res > 0)
            add = std::min(res, need) * A + std::max(0LL, need - res) * B;
        else
            add = need * B;

        while (pos_a >= 1 && a[pos_a] == i) now -= C, --pos_a;
        now -= (ll)pos_a * C;

        ans = std::min(ans, now + add);
    }

    printf("%lld\n", ans);
    return 0;
}

P3747 [六省聯考 2017] 相逢是問候

長さ n の配列を扱い、定数 c, p が与えられる。次の2種類の操作を行う：

• 区間 [l, r] 内の各要素 a_i に置き換える：a_i ← c^a_i
• 区間 [l, r] の和を mod p で出力

(1 ≤ n, m ≤ 5×10⁴, 1 ≤ c, a_i < p ≤ 10⁸)

指数の冪乗はオイラー関数 φ によって再帰的に簡約できる。特に、φ(φ(…φ(p))) は急速に 1 に収束するため、深さは O(log p) に抑えられる。これにより、操作回数が非常に少ないことがわかる。

線分木を用い、各節点に「最大の操作深さ」（minx）と「区間和」（sum）を保持する。深さが既に上限に達していれば更新しない。そうでなければ、葉まで再帰的に処理する。

各要素の更新は、事前に φ 序列を計算し、光速累乗（Exponential Preprocessing）を用いて O(1) で行う。各層でのべき乗は O(log p) だが、全体で O(m log²p) 以内に抑えられる。

事前計算として φ 関数の値を O(√p log p) で算出し、累乗テーブルを構築。これにより、全体の時間計算量は O((√p + √m) log p + m log²p + n log n) となり、制限内に収まる。

#include <cstdio>
#include <algorithm>
const int N = 5e4 + 10, D = 100, B = 1e4;
typedef long long ll;

int pw[2][D][B + 10], ov[2][D][B + 10], phi[D], dep, n, m, p, c, over, a[N];

inline int Phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) res = res / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

inline void pre() {
    phi[0] = p;
    while (phi[dep] > 1) ++dep, phi[dep] = Phi(phi[dep - 1]);
    phi[++dep] = 1;

    for (int i = 0; i <= dep; ++i) {
        pw[0][i][0] = 1;
        for (int j = 1; j <= B; ++j) {
            ll t = (ll)pw[0][i][j - 1] * c;
            if (t >= phi[i]) ov[0][i][j] = 1;
            pw[0][i][j] = t % phi[i];
            ov[0][i][j] |= ov[0][i][j - 1];
        }

        pw[1][i][0] = 1;
        for (int j = 1; j <= B; ++j) {
            ll t = (ll)pw[1][i][j - 1] * pw[0][i][B];
            if (t >= phi[i]) ov[1][i][j] = 1;
            pw[1][i][j] = t % phi[i];
            ov[1][i][j] |= ov[1][i][j - 1];
        }
    }
}

inline int gsm(int d, int b) {
    int v1 = b / B, v2 = b % B;
    over |= ov[0][d][v2] | ov[1][d][v1];
    ll t = (ll)pw[0][d][v2] * pw[1][d][v1];
    if (t >= phi[d]) over = 1;
    return t % phi[d];
}

int calc(int p, int cnt, int d) {
    over = 0;
    if (d == cnt) {
        if (a[p] >= phi[d]) over = 1;
        return a[p] % phi[d];
    }
    int x = calc(p, cnt, d + 1);
    if (over) x += phi[d + 1], over = 0;
    return gsm(d, x);
}

struct SegTree {
    #define ls(k) (k << 1)
    #define rs(k) (k << 1 | 1)
    struct node { int l, r, cnt, sum; } h[N << 2];

    void pushup(int k) {
        h[k].cnt = std::min(h[ls(k)].cnt, h[rs(k)].cnt);
        h[k].sum = (h[ls(k)].sum + h[rs(k)].sum) % p;
    }

    void build(int k, int l, int r) {
        h[k].l = l; h[k].r = r;
        if (l == r) return h[k].sum = a[l], void();
        int mid = (l + r) >> 1;
        build(ls(k), l, mid); build(rs(k), mid + 1, r);
        pushup(k);
    }

    void change(int k, int x, int y) {
        if (h[k].cnt >= dep) return;
        if (h[k].l == h[k].r) {
            ++h[k].cnt;
            h[k].sum = calc(h[k].l, h[k].cnt, 0);
            return;
        }
        int mid = (h[k].l + h[k].r) >> 1;
        if (x <= mid) change(ls(k), x, y);
        if (mid < y) change(rs(k), x, y);
        pushup(k);
    }

    int query(int k, int x, int y) {
        if (x <= h[k].l && h[k].r <= y) return h[k].sum;
        int mid = (h[k].l + h[k].r) >> 1, ret = 0;
        if (x <= mid) (ret += query(ls(k), x, y)) %= p;
        if (mid < y) (ret += query(rs(k), x, y)) %= p;
        return ret;
    }
} sgt;

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &c);
    pre();
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sgt.build(1, 1, n);

    for (int i = 1, op, l, r; i <= m; ++i) {
        scanf("%d%d%d", &op, &l, &r);
        if (op) printf("%d\n", sgt.query(1, l, r));
        else sgt.change(1, l, r);
    }
    return 0;
}

P3746 [六省聯考 2017] 組合數問題

整数 n, p, k, r が与えられ、次の値を求める：

∑_{i≥0} C(nk, ik + r) mod p

(1 ≤ n ≤ 10⁹, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2³⁰ - 1)

k が小さいため、剰余クラス k に注目する。状態を f[i][j]：i 個のアイテムから選んだ個数が ≡ j (mod k) となる組み合わせ数とする。初期状態は f[0][0] = 1。

遷移式は：

f[i][j] = f[i-1][j] + f[i-1][(j-1) mod k]

これは定係数線形漸化式であり、行列累乗で高速化可能。転置行列を用いた畳み込み形式で、次のような行列を構築：

M[i][j] = 1 if j == i or j == (i-1)%k else 0

この行列を (nk) 乗して、初期ベクトルとの積を取ることで答えを得る。時間計算量は O(k³ log(nk))。

#include <cstdio>
const int N = 60;
typedef long long ll;

int n, p, k, r;
struct Matrix {
    int a[N][N], n, m;
    int* operator[](int n) { return a[n]; }
    void init(int N, int M, int on = 0) {
        n = N; m = M;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                a[i][j] = on ? (i == j) : 0;
    }
    Matrix operator*(Matrix A) {
        Matrix ret; ret.init(n, A.m);
        for (int i = 1; i <= ret.n; ++i)
            for (int j = 1; j <= ret.m; ++j)
                for (int k = 1; k <= m; ++k)
                    (ret[i][j] += (ll)a[i][k] * A[k][j] % p) %= p;
        return ret;
    }
} A, B, I;

Matrix ksm(Matrix A, ll b) {
    Matrix ret = I;
    while (b) {
        if (b & 1) ret = ret * A;
        A = A * A; b >>= 1;
    }
    return ret;
}

int main() {
    scanf("%d%d%d%d", &n, &p, &k, &r);
    A.init(1, k); B.init(k, k, 1); I.init(k, k, 1);
    A[1][1] = 1;
    for (int i = 2; i <= k; ++i) ++B[i][i - 1];
    ++B[1][k];
    B = ksm(B, (ll)n * k);
    A = A * B;
    printf("%d\n", A[1][r + 1]);
    return 0;
}

P3750 [六省聯考 2017] 分手は願い

n 個のランプがあり、初期状態は明暗混合。スイッチ i は、d|i となるすべての位置を反転させる。ある人がランダムにスイッチを押すが、最適操作が ≤ k 手で終了できる場合、最適手順を採用する。期待操作回数 × n! を 10⁵+3 で出力せよ。

最適手順は、番号が大きい順に、明になっているランプがあればスイッチを押す。これにより最小手数 m が得られる。この手数は O(n√n) で計算可能。

期待値を求めるため、f[i]：最適手順が i 手必要な状態の期待操作回数とする。再帰的に：

f_i = (i/n) f_{i-1} + ((n-i)/n) f_{i+1} + 1

差分 d_i = f_i - f_{i-1} を導入すると、

d_i = ((n-i)/i) d_{i+1} + (n/i)

この式は逆順に計算可能。f_k = k とし、d_n = 1 から逆算すれば、f_m が得られる。特例として、k ≥ m の場合は直接出力。

#include <cstdio>
const int N = 1e6 + 10, mod = 100003;

int a[N], f[N], d[N];

inline int ksm(int a, int b) {
    int ret = 1;
    while (b) {
        if (b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod; b >>= 1;
    }
    return ret;
}

int main() {
    int n, m = 0, k, fac = 1;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        fac = 1ll * fac * i % mod;
    }

    for (int i = n; i >= 1; --i) {
        if (!a[i]) continue;
        for (int j = 1; j * j <= i; ++j) {
            if (i % j) continue;
            a[j] ^= 1;
            if (j * j != i) a[i / j] ^= 1;
        }
        ++m;
    }

    if (m <= k) {
        printf("%lld\n", 1ll * m * fac % mod);
        return 0;
    }

    d[n] = 1;
    for (int i = n - 1; i >= k; --i) {
        int inv = ksm(i, mod - 2);
        d[i] = (1ll * inv * (n - i) % mod * d[i + 1] % mod + 1ll * inv * n % mod) % mod;
    }

    f[k] = k;
    for (int i = k + 1; i <= m; ++i)
        f[i] = (f[i - 1] + d[i]) % mod;

    f[m] = 1ll * f[m] * fac % mod;
    printf("%d\n", f[m]);
    return 0;
}

P3749 [六省聯考 2017] 寿司レストラン

寿司 n 種類、代号 a_i。購入は連続区間。区間 [l, r] の美味度は d_{l,r} で、同じ代号の寿司は1度だけ課金される。課金額は m×x² + c×x。最大の利益（美味度 - 費用）を求める。

制約 n ≤ 100 なので、最大權閉路問題としてネットワークフローで解ける。構成方法：

• 区間 [l, r] のノード → 美味度 = d_{l,r}
• 代号ごとに虚ノード → 次のノードに接続、価値 = -m×x²
• 各寿司 i → 代号ノードに接続、価値 = -a_i
• 区間 [l, r] → [l, r-1] と [l+1, r] に接続（境界は自己参照）

最大權閉路は、源点から正の重みノードへ、負の重みノードからターゲットへ、容量無限の辺を張り、最大流を引くことで得られる。実装では代号を座標圧縮。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 5e6 + 10, M = 110, inf = 2e9;

int a[M], b[M], rev[M], tmp[M], id[M][M], ID[M], len;
struct edge { int v, c, next; } E[N << 1];
int cur[N], p[N], cnt, S, T = N - 1, tn, d[N];

inline void init() {
    memset(p, -1, sizeof(p));
    memset(cur, -1, sizeof(cur));
    cnt = 0;
}

inline void insert(int u, int v, int c) {
    E[cnt].v = v; E[cnt].c = c; E[cnt].next = p[u]; p[u] = cnt++;
}

inline void addedge(int u, int v, int c) {
    insert(u, v, c); insert(v, u, 0);
}

inline bool bfs() {
    memset(d, -1, sizeof(int) * (tn + 10));
    d[T] = -1;
    std::queue<int> q; q.push(S); d[S] = 0; cur[S] = p[S];
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = p[u], v; i + 1; i = E[i].next) {
            v = E[i].v; cur[v] = p[v];
            if (d[v] == -1 && E[i].c) d[v] = d[u] + 1, q.push(v);
        }
    }
    return d[T] != -1;
}

int dfs(int u, int flow) {
    if (u == T) return flow;
    int ans = 0, ret;
    for (int i = cur[u], v; i + 1; i = E[i].next) {
        v = E[i].v; cur[u] = i;
        if (d[v] == d[u] + 1 && E[i].c) {
            ret = dfs(v, std::min(E[i].c, flow));
            E[i].c -= ret; E[i ^ 1].c += ret;
            flow -= ret; ans += ret; if (!flow) break;
        }
    }
    if (!ans) d[u] = -1;
    return ans;
}

int dinic() { int ans = 0; while (bfs()) ans += dfs(S, inf); return ans; }

int main() {
    init();
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), tmp[i] = a[i];
    std::sort(tmp + 1, tmp + 1 + n);
    len = std::unique(tmp + 1, tmp + 1 + n) - tmp - 1;

    for (int i = 1; i <= n; ++i) {
        b[i] = std::lower_bound(tmp + 1, tmp + 1 + len, a[i]) - tmp;
        rev[b[i]] = a[i];
    }

    for (int i = 1; i <= len; ++i)
        addedge(++tn, T, m * rev[i] * rev[i]);

    for (int i = 1; i <= n; ++i) {
        addedge(ID[i] = ++tn, T, a[i]);
        addedge(ID[i], b[i], inf);
    }

    for (int i = 1, d; i <= n; ++i)
        for (int j = 1; j <= n - i + 1; ++j) {
            scanf("%d", &d);
            if (d < 0) addedge(!id[i][j] ? id[i][j] = ++tn : id[i][j], T, -d);
            else addedge(S, !id[i][j] ? id[i][j] = ++tn : id[i][j], d), ans += d;

            if (j == 1) addedge(id[i][j], ID[i], inf);
            else {
                addedge(id[i][j], id[i][j - 1], inf);
                addedge(id[i][j], (!id[i + 1][j - 1] ? (id[i + 1][j - 1] = ++tn) : id[i + 1][j - 1]), inf);
            }
        }

    printf("%d\n", ans - dinic());
    return 0;
}