[LOJ2145][SHOI2017]分手是祝愿

qwq

题意

n个灯下标从1到n,已知初始状态。

改变一个灯的状态会改变所有它约数的编号的灯的状态。

如果当前可以操作小于等于k次使其全灭,则直接选择次数最小的方案。

否则随机等概率操作开关。

求操作次数期望乘以n阶乘对100003取模后的结果。

思路

设$ f[i] $表示i步到i - 1步的操作次数期望个数。

有$ f[i] = \frac{i}{n} + \frac{n - i}{n}(f[i] + f[i + 1] + 1) $。

即$ f[i] = \frac{(n - 1)f_{i + 1} + n}{i} $ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 100010,MOD = 100003;
int n,k,m,frc,c[N],f[N];
inline int qpow(int a,int b)
{
int r = 1;for(;b;b >>= 1)
{
if(b & 1) r = 1LL * r * a % MOD;
a = 1LL * a * a % MOD;
}
return r;
}
int main()
{
n = getint();k = getint();
frc = 1;
for(int i = 1;i <= n;++i) c[i] = getint(),frc = 1LL * frc * i % MOD;
for(int i = n;i;--i){for(int j = i * 2;j <= n;j += i) c[i] ^= c[j];m += c[i];}
for(int i = n;i > k;--i) f[i] = 1LL * ((n + 1LL * (n - i) * f[i + 1]) % MOD) * qpow(i,MOD - 2) % MOD;
int ans = std::min(m,k);
for(int i = k + 1;i <= m;i++) if((ans += f[i]) >= MOD) ans -= MOD;
ans = 1LL * ans * frc % MOD;
printf("%d\n",(ans + MOD) % MOD);
return 0;
}