P3750 [六省联考 2017] 分手是祝愿题解
Link
思路
比较神经。
首先题目中每个操作都不可以被替代，也就是说，不在原来的最优解中的操作做了一次，就要再做一次才可以。
发现这个东西的期望和步数有关系，考虑将步数定义在状态中。
设 \(f_i\) 表示目前有最优解有 \(i\) 步，要从第 \(i\) 步进行到 \(i-1\) 步的期望为 \(f_i\)。
那么转移为：
\[f_i = \frac{i}{n}+\frac{n-i}{n}(f_{i+1}+f_i+1)
\]
即：
\[f_i=\frac{n+(n-i)f_{i+1}}{i}
\]
然后就可以转移了。
最后的答案处理也很简单，做一个前缀和即可。
代码：
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5;
const int Md = 100003;
int n, k, a[N], cnt;
ll f[N];
ll qpow(ll a, ll b) {ll ret = 1;while (b) {if (b & 1) ret = (ret * a) % Md;a = (a * a) % Md;b >>= 1;}return ret;
}
int main() {FASTIO;cin >> n >> k;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = n; i >= 1; --i) {if (a[i]) {++cnt;for (int j = 1; j * j <= i; ++j) {if (i % j == 0) {a[j] ^= 1;if (i / j != j) a[i / j] ^= 1;}}}}f[n + 1] = 0;for (int i = n; i >= 1; --i) f[i] = (f[i + 1] * (n - i) % Md + n) % Md * qpow(i, Md - 2) % Md; ll sum = 0;if (cnt <= k) sum = cnt;else {for (int i = cnt; i > k; --i)sum = (sum + f[i]) % Md;sum = (sum + k) % Md;}for (int i = 1; i <= n; ++i)sum = (sum * i) % Md;cout << sum << '\n';return 0;
}
总结
这题的思路挺神经的，说实话没有见过将这种最优步数转为期望步数，然后放在状态中的做法，感觉很妙。