原题链接 写到一半发现写不下去了。。。 所以orz xyz32768,您去看这篇题解吧,思路很清晰,我之前写的胡言乱语与之差距不啻天渊
#include #include #include #include #include #include #include #include #include #include #include #include #include #define IINF 0x3f3f3f3f3f3f3f3fLL #define u64 unsigned long long #define pii pair #define mii map #define u32 unsigned int #define lbd lower_bound #define ubd upper_bound #define INF 0x3f3f3f3f #define vi vector #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; }