简要题意
Zeit und Raum trennen dich und mich. 时空将你我分开。
有一个长度为 \(n\) 的 \(01\) 序列。ZYB 君在 ZBZ 爷爷的指引下，重复进行以下操作，直到原序列变成全 \(0\) 序列：
- ZBZ 爷爷用他智慧的双眼看看这个序列需要 ZYB 君最多进行几次操作，如果只要进行最多 \(k\) 次，就直接用用最好的方法进行这些操作。
- ZYB 君进行一次操作，操作方法为等概率选择一个数 \(p\)，将 \(p\) 的全部因子对应的序列上的值取反。
问期望操作次数。答案乘上 \(n!\) 然后对 \(100003\) 取模。
\(0 \leq k \leq n \leq 10^5\)，对于 \(50\%\) 的数据，有 \(k=n\)。
思路
50pts
50pts，实际上是 80pts。
其实就是 ZBZ 的智慧双眼生效了。我们只需要讨论最优方案。
引理：\(\forall x,\not\exists y<x\)，使得可以操作 \(y\) 来改变 \(x\)。
Proof: 显然有 \(\forall i|x,i\leq x\)。证毕。
所以我们可以从大到小，只要是 \(1\) 就操作。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005,mod = 100003;
int n,k,a[N];
vector<int> factor[N];
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;i*j<=n;j++) factor[i*j].push_back(i);
}
int ans=0;
for(int i=n;i;i--){
if(!a[i]) continue;
ans++;
for(int j : factor[i]) a[j]^=1;
}
for(int i=1;i<=n;i++) ans=ans*i%mod;
cout<<ans;
return 0;
}
100pts
我们考虑一般情况，令 \(f(i)\) 为将操作数为 \(i\) 的变成操作数为 \(i-1\) 的的期望次数。则：
\[f(i)=\frac{i}{n}+\frac{n-i}{n}(f(i+1)+f(i)+1) \]稍微解释一下，第一种情况是 \(\frac{i}{n}\) 选择了正确的地方。第二种情况是 \(\frac{n-i}{n}\) 的概率就是用 \(1\) 次变成期望 \(i+1\) 次，我们还需要一次 \(f(i+1)\) 和一次 \(f(i)\)。
然后如果 50pts 暴力搞就搞，否则你就按照期望公式，\(k+1\leftarrow\text{暴力次数}\) 都可能是一种情况，求出它们的和加上 \(k\) 即可。
这就是期望的答案。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005,mod = 100003;
int n,k,a[N],f[N],inv[N]={1,1};
vector<int> factor[N];
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;i*j<=n;j++) factor[i*j].push_back(i);
}
for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
// for(int i=2;i<=n;i++) cout<<inv[i]<<' ';cout<<'\n';
int ans=0;
for(int i=n;i;i--){
if(!a[i]) continue;
ans++;
for(int j : factor[i]) a[j]^=1;
}
for(int i=n;i;i--){
f[i]=(n+(n-i)*f[i+1])%mod;
f[i]*=inv[i];
f[i]%=mod;
// cout<<f[i]<<' ';
}
if(ans>k){
int ret=0;
for(int i=ans;i>k;i--) ret+=f[i];
ans=(ret%mod+k)%mod;
}
for(int i=1;i<=n;i++) ans=ans*i%mod;
cout<<ans;
return 0;
}