题目描述
B 君在玩一个游戏，这个游戏由 n 个灯和 n 个开关组成，给定这 n 个灯的初始状态，下标为从 1 到 n 的正整数。
每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。
但是当操作第 i 个开关时，所有编号为 i 的约数（包括 1 和 i）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。
B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。
这个策略需要的操作次数很多，B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 k 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 k 步）操作这些开关。
B 君想知道按照这个策略（也就是先随机操作，最后小于等于 k 步，使用操作次数最小的操作方法）的操作次数的期望。
这个期望可能很大，但是 B 君发现这个期望乘以 n 的阶乘一定是整数，所以他只需要知道这个整数对 100003 取模之后的结果。
题解
如果这道题要求我们求出最少需要按多少步的话，我们可以直接从高到低依次贪心的判断每一个位置按或者不按。
可以发现，这个答案是不超过n的。
所以我们可以对所有状态按照需要的最小步数分为n类，而且对于任意一个状态i，可以证明，我们按到它应该按到的位置会将它引入i-1中，按到其他位置会将它引入i+1中。
这个可能是这道题最不容易攻破的地方，不过仔细想一想也是可以理解的。
对于随机的部分，我们可以设计一个状态dp[i]表示从i状态转移到i-1状态期望需要的步数。
dp[i]=i/n*1+(n-i)/n*(dp[i]+dp[i+1]+1)
如果我按对了，只会有1的贡献，如果按错了，会有1的贡献并跳到i+1去，有要花dp[i]+dp[i+1]的代价转移到i-1去。
可以轻松解出上面式子的转移式(注意一定要从n开始往前推)。
最后求个∑就好了。
代码
#include<iostream> #include<cstdio> #include<vector> #define N 100009 using namespace std; typedef long long ll; const ll mod=100003; vector<int>vec[N]; bool a[N]; ll dp[N],ans,n; int k,now; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } inline ll power(ll x,ll y){ ll ans=1; while(y){ if(y&1)ans=ans*x%mod; x=x*x%mod;y>>=1; } return ans; } int main(){ n=rd();k=rd(); for(int i=1;i<=n;++i)a[i]=rd(); for(int i=1;i<=n;++i)for(int j=i;j<=n;j+=i)vec[j].push_back(i); for(int i=n;i>=1;--i)if(a[i]){ now++; for(int j=0;j<vec[i].size();++j)a[vec[i][j]]^=1; } if(now<=k)ans=now; else{ for(int i=n;i>k;--i){ ll x=power(i,mod-2); dp[i]=(n%mod+1ll*(n-i)%mod*dp[i+1]%mod)%mod;dp[i]=dp[i]*x%mod; } ans=k; for(int i=k+1;i<=now;++i)ans=(ans+dp[i])%mod; } for(int i=1;i<=n;++i)ans=ans*i%mod; cout<<ans; return 0;