洛谷P3600随机数生成器——期望+DP

洛谷P3600随机数生成器——期望+DP

原题链接

写到一半发现写不下去了。

。

。

所以orz xyz32768，您去看这篇题解吧，思路很清晰，我之前写的胡言乱语与之差距不啻天渊

#include <algorithm>

#include  <iostream>

#include   <cstdlib>

#include   <cstring>

#include    <cstdio>

#include    <random>

#include    <string>

#include    <vector>

#include     <cmath>

#include     <ctime>

#include     <queue>

#include       <map>

#include       <set>

#define IINF 0x3f3f3f3f3f3f3f3fLL

#define u64 unsigned long long

#define pii pair<int, int>

#define mii map<int, int>

#define u32 unsigned int

#define lbd lower_bound

#define ubd upper_bound

#define INF 0x3f3f3f3f

#define vi vector<int>

#define ll long long

#define mp make_pair

#define pb push_back

#define is insert

#define se second

#define fi first

#define ps push

using namespace std;

#define MOD 666623333

void add(int &x, int y) {

    x = (x + y) % MOD;

    if (x < 0) x += MOD;

}

int Add(int x, int y) {

    return (x + y + MOD) % MOD;

}

void mul(int &x, int y) {

    x = 1LL * x * y % MOD;

    if (x < 0) x += MOD;

}

int Mul(int x, int y) {

    return (1LL * x * y % MOD + MOD) % MOD;

}

int fpow(int x, int p) {

    int ret = 1;

    while(p) {

        if (p & 1) mul(ret, x);

        mul(x, x);

        p >>= 1;

    }

    return ret;

}

const int MAXN = 2000;

int n, x, q, h[MAXN + 5], g[MAXN + 5], f[MAXN + 5][MAXN + 5], sum[MAXN + 5][MAXN + 5], l[MAXN + 5], r[MAXN + 5], tmp[MAXN + 5], ans;

pii qrs0[MAXN + 5], qrs[MAXN + 5];

void init() {

    cin >> n >> x >> q;

    for (int i = 1; i <= q; ++i)

        cin >> qrs0[i].fi >> qrs0[i].se;

    int tot = 0;

    sort(qrs0 + 1, qrs0 + q + 1);

    for (int i = 1; i <= q; ++i) {

        if (i > 1 && qrs0[i].fi == qrs0[i - 1].fi) continue;

        while (tot && qrs[tot].se >= qrs0[i].se) tot--;

        qrs[++tot] = qrs0[i];

    }

    q = tot;

    for (int i = 1; i <= q; ++i) tmp[qrs[i].se + 1]--, tmp[qrs[i].fi]++;

    for (int i = 2; i <= n; ++i) tmp[i] += tmp[i - 1];

    for (int i = 1; i <= n; ++i) {

        if (!tmp[i]) {

            int j = 0;

            while (j + 1 <= q && qrs[j + 1].se < i) j++;

            r[i] = j, l[i] = j + 1;

        }

        else {

            int j = 0;

            while (j + 1 <= q && qrs[j + 1].se < i) j++;

            l[i] = ++j;

            while (j + 1 <= q && qrs[j + 1].fi <= i) j++;

            r[i] = j;

        }

    }

}

void solve() {

    f[0][0] = sum[0][0] = 1;

    int p = -1;

    for (int i = 1; i <= n; ++i) {

        while (p < i && r[p + 1] + 1 < l[i]) p++;

        sum[0][i] = 1;

        for (int j = 1; j <= n; ++j) {

            f[i][j] = Add(sum[j - 1][i - 1], (~p ? -sum[j - 1][p] : 0));

            sum[j][i] = Add(sum[j][i - 1], f[i][j]);

        }

        if (r[i] == q)

            for (int j = 1; j <= n; ++j)

                add(g[j], f[i][j]);

    }

    for (int i = 1; i <= x; ++i)

        for (int j = 1; j <= n; ++j)

            add (h[i], Mul(g[j], Mul(fpow(i, j), fpow(x - i, n - j))));

    for (int i = 1; i <= x; ++i)

        add (ans, Mul(i, Add(h[i], -h[i - 1])));

    mul(ans, fpow(fpow(x, n), MOD - 2));

}

int main() {

    init();

    solve();

    cout << ans << endl;

    return 0;

}