挺有意思的计数。
计数感觉很难做,不妨转成期望,期望又可以转成概率之和。
考虑枚举 \(w \in [0,m-1]\),把 \(> w\) 的数设为 \(1\),\(\le w\) 的数设为 \(0\)。那么期望就是所有 \(w\),\(a_i\) 为 \(1\) 的概率之和。对于一个 \(i\),只有以下的操作能改变 \(a_i\),称以下操作为 \(i\) 的关键操作:
- 满足 \(i \in [l,r], v < w\) 的操作 \(1\);
- 满足 \(i \in [l,r], v \ge w\) 的操作 \(2\)。
设 \(p_i\) 为一个操作能为 \(i\) 的关键操作的概率,分别考虑它是否包含 \(i\),\(v\) 是否 \(< w\),是否为操作 \(1/2\),那么:
\[p_i = \dfrac{i(n-i+1)}{\dfrac{n(n+1)}{2}} \times (\dfrac{1}{2} \times \dfrac{m}{2m+1} \times \dfrac{w}{m} + \dfrac{1}{2} \times \dfrac{m}{2m+1} \times \dfrac{m-w}{m}) = \dfrac{2mi(n-i+1)}{n(n+1)(2m+1)}
\]
设 \(f_{w,t,i}\) 为 \(t\) 时刻 \(a_i\) 为 \(1\) 的概率,则:
\[f_{w,t,i} = [1 - (1-p_i)^t] \times \dfrac{m-w-1}{m}
\]
设 \(g_{t,i}\) 为 \(t\) 时刻 \(a_i\) 的和,枚举 \(w\) 求和,即:
\[g_{t,i} = \sum\limits_{w=0}^{m-1} f_{w,t,i} = \sum\limits_{w=0}^{m-1} [1 - (1-p_i)^t] \times \dfrac{m-w-1}{m} = \dfrac{m-1}{2} \times [1 - (1-p_i)^t]
\]
枚举第 \(t+1\) 个操作为 \(3\) 操作,每个位置拆贡献,答案即:
\[ans = \sum\limits_{t=0}^{q-1} \sum\limits_{i=1}^n \dfrac{i(n-i+1)}{\dfrac{n(n+1)}{2}} \times \dfrac{1}{2m+1} \times \dfrac{m-1}{2} \times [1 - (1-p_i)^t]
\]
\[= \sum\limits_{i=1}^n \dfrac{i(n-i+1)}{n(n+1)} \times \dfrac{m-1}{2m+1} \times \sum\limits_{t=0}^{q-1} [1 - (1-p_i)^t]
\]
\[= \sum\limits_{i=1}^n \dfrac{i(n-i+1)}{n(n+1)} \times \dfrac{m-1}{2m+1} \times (q - \dfrac{1-(1-p_i)^q}{p_i})
\]
至此可以 \(O(n \log P)\) 计算,\(P\) 为模数。
code
// Problem: F - Do you like query problems?
// Contest: AtCoder - AtCoder Regular Contest 111
// URL: https://atcoder.jp/contests/arc111/tasks/arc111_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
ll n, m, q, p[maxn];
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &q);
for (int i = 1; i <= n; ++i) {
p[i] = 1LL * i * (n - i + 1) % mod * m % mod * 2 % mod * qpow(n * (n + 1) % mod * (m * 2 + 1) % mod, mod - 2) % mod;
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ll t = (mod + 1 - qpow((mod + 1 - p[i]) % mod, q)) % mod * qpow(p[i], mod - 2) % mod;
ans = (ans + 1LL * i * (n - i + 1) % mod * (m - 1) % mod * qpow(n * (n + 1) % mod * (m * 2 + 1) % mod, mod - 2) % mod * (q - t + mod) % mod) % mod;
}
ans = ans % mod * qpow(((n * (n + 1) / 2) % mod) * (m * 2 + 1) % mod, q) % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- problems AtCoder Regular Contest queryatcoder regular contest queries problems atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder