4872: [Shoi2017]分手是祝愿
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 458 Solved: 299
[Submit][Status][Discuss]
Description
Zeit und Raum trennen dich und mich.
时空将你我分开。B 君在玩一个游戏，这个游戏由 n 个灯和 n 个开关组成，给定这 n 个灯的初始状态，下标为
从 1 到 n 的正整数。每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏
的目标是使所有灯都灭掉。但是当操作第 i 个开关时，所有编号为 i 的约数（包括 1 和 i）的灯的状态都会被
改变，即从亮变成灭，或者是从灭变成亮。B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机
操作一个开关，直到所有灯都灭掉。这个策略需要的操作次数很多， B 君想到这样的一个优化。如果当前局面，
可以通过操作小于等于 k 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个
策略显然小于等于 k 步）操作这些开关。B 君想知道按照这个策略（也就是先随机操作，最后小于等于 k 步，使
用操作次数最小的操作方法）的操作次数的期望。这个期望可能很大，但是 B 君发现这个期望乘以 n 的阶乘一定
是整数，所以他只需要知道这个整数对 100003 取模之后的结果。
Input
第一行两个整数 n, k。
接下来一行 n 个整数，每个整数是 0 或者 1，其中第 i 个整数表示第 i 个灯的初始情况。
1 ≤ n ≤ 100000, 0 ≤ k ≤ n；
Output
输出一行，为操作次数的期望乘以 n 的阶乘对 100003 取模之后的结果。
Sample Input
4 0
0 0 1 1
0 0 1 1
Sample Output
512
HINT
Source
首先一个状态最少需要多少步是可以 O(N log N)算出来的，调和级数一下就好了。
而且我们可以发现，对于每一个状态，用最小步数关掉所有灯的方案是唯一的，考虑从后向前扫描，是1就动否则不动，总是最优的。
然后我们就设 f[i] 为关掉所有灯的最小步数为i的期望答案。
显然 当i<=k的时候，f[i]=i；其他情况，f[i] = (i/n) * f[i-1] + ((n-i)/n) * f[i+1] 。
为什么随机的式子是长那个样子的呢？
前面已经证明了对于每一个状态，最小步数关掉所有灯的方案是唯一的。
而又因为按灯的顺序不影响答案，所以有(i/n)的几率最短步数减少；
但如果没有按最短路上的灯，首先最短步数不会减少，因为最短路唯一；
而且也不会不变，因为如果还按原来的套路按灯的话最后不会都灭；
那么按了不是最短方案的灯，会让最短步数增加多少呢？
只能是1，因为可以再按一步回去。
我们可以发现的是，f[n] = f[n-1] + 1。
通过这个向前推，可以推出形如f[i] = f[i-1] + h[i]的式子，并且h[i] = (n / i) (1 + h[i+1] * (n-i) / n) 。
然后就可以直接从前往后递推了，对于i<=k,f[i] = i；否则, f[i] = f[i-1] + h[i] 。
然后就可以A了2333
#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
#define ha 100003
using namespace std;
int n,k,T,a[maxn],opt[maxn];
int f[maxn],jc=1,inv[maxn],h[maxn]; inline int add(int x,int y){
x+=y;
return x>=ha?x-ha:x;
} inline void init(){
inv[1]=1;
for(int i=2;i<ha;i++) inv[i]=-inv[ha%i]*(ll)(ha/i)%ha+ha;
} int main(){
init(); scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",a+i),jc=jc*(ll)i%ha;
for(int i=n;i;i--){
for(int j=i<<1;j<=n;j+=i) a[i]^=opt[j];
if(a[i]) opt[i]=1,T++;
} f[0]=0;
for(int i=1;i<=k;i++) f[i]=i;
h[n]=1;
for(int i=n-1;i;i--) h[i]=add(n*(ll)inv[i]%ha,h[i+1]*(ll)(n-i)%ha*(ll)inv[i]%ha);
for(int i=k+1;i<=T;i++) f[i]=add(f[i-1],h[i]); printf("%d\n",f[T]*(ll)jc%ha);
return 0;
}