luogu P3750 [六省联考 2017]分手是祝愿

https://www.luogu.com.cn/problem/P3750

$k=n$给了$80$分可还行
首先考虑$k=n$,不难想到一个贪心，从大到小枚举每个开关，如果为$1$就把按，这样一定是最优的，就做完了

考虑$k<n$,先跑一边上面的得到$gs$

把期望的式子写出来$E(i)=\frac{i}{n}E(i?1)+\frac{n?i}{n}E(i+1)+1$
最少还要$i$步的时候，期望几步能搞完，显然$E(k)=k$
这显然是个带状矩阵，可以直接上带状矩阵高斯消元，不过我写的是手动消元
答案就是$E(gs)$

code:

#include<bits/stdc++.h>
#define ll long long
#define mod 100003
#define N 200050
using namespace std;
ll qpow(ll x, ll y) {
    ll ret = 1;for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;return ret;
}
struct A {
    ll a, b, c, d;
} v[N];
int n, k, a[N];
ll E[N];
vector<int> d[N];
int main() {
    scanf("%d%d", &n, &k);for(int i = 1; i <= n; i ++)for(int j = i; j <= n; j += i) d[j].push_back(i);for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);int gs = 0;for(int i = n; i >= 1; i --) if(a[i]) {
    for(int x : d[i]) a[x] ^= 1;gs ++;}ll ans = 0;if(gs <= k) ans = gs;else {
    //wdnmd 不会啊// E[k] = k;// for(int i = k; i <= gs; i ++) E[i + 1] = (E[i] - i * qpow(n, mod - 2) % mod * E[i - 1] % mod - 1 + mod) % mod * n % mod * qpow(n - i, mod - 2) % mod;// for(int i = k; i <= gs; i ++) printf("%lld ", E[i]); printf("\n");E[k] = k;for(int i = k + 1; i <= n; i ++) {
    v[i].a = i * qpow(n, mod - 2) % mod;v[i].b = mod - 1;v[i].c = (n - i) * qpow(n, mod - 2) % mod;v[i].d = mod - 1;}for(int i = n - 1; i >= k; i --) {
    ll bs = v[i].c * qpow(v[i + 1].b, mod - 2) % mod;v[i].b = (v[i].b - bs * v[i + 1].a % mod + mod) % mod;v[i].c = (v[i].c - bs * v[i + 1].b % mod + mod) % mod;v[i].d = (v[i].d - bs * v[i + 1].d % mod + mod) % mod;}   for(int i = k + 1; i <= n; i ++) {
    ll bs = qpow(v[i].b, mod - 2) % mod;E[i] = (v[i].d - v[i].a * E[i - 1] % mod + mod) % mod * bs % mod;}// for(int i = k; i <= n; i ++) printf("%lld ", E[i]); printf("\n");ans = E[gs];    }for(int i = 1; i <= n; i ++) ans = ans * i % mod;printf("%lld", ans);return 0;
}

看了眼题解，发现了一个nb的东西
可以考虑把期望的定义差分,$E(i)$表示从$i$变成$i?1$期望要几步

显然$E(i)=\frac{n?i}{n}(E(i+1)+E(i))+1$
就是说可能变多了一步，然后又变回去，
移一下项变成$E(i)=\frac{(n?i)E(i+1)}{i}+\frac{n}{i}$
然后直接倒过来递推即可

然后在把$E(k)$到$E(gs)$加起来即可

code:

懒得写