「LOJ 2145」「SHOI2017」分手是祝愿

LOJ #2145

Zeit und Raum trennen dich und mich.

时空将你我分开。

题意

你有一排$n$个灯泡，有初始状态$0/1$，从$1$开始编号

一次操作可以选定一个整数$x\in[1,n]$，把$x$的所有约数号（含$1$和$x$）灯泡状态取反。

你要把所有灯泡变成$0$，给出$0\le k\le n$

1. 若剩余最小操作次数$\le k$，你会直接按照最小操作次数操作，并结束

2. 否则每次你会在$[1,n]$中等概率地选择一个整数进行操作，直到满足1的条件

求期望操作次数乘$n!$对$100003$取模的结果

$1\le n\le 10^5$

---

分析

先考虑求出最小操作次数。

容易发现，如果相同操作最多执行1次，那么操作的集合是唯一的

我们可以在$\mathcal O(n\ ln\ n)$的复杂度内处理出每个数的约数，从大到小枚举位置，若该位置需要复原，那么执行操作。

从这里也可以发现$2^n$个状态到$2^n$个操作集合是个双射

设求出的剩余操作次数为$x$，若$x\le k$，输出$x*n!$。

事实上直接这么做可以获得$80$分的好成绩

---

考虑$x>k$的情况

做法1

令$f_i$表示剩余需要$i$次操作时，期望操作次数

可以发现

$$f_k=k\tag{1}$$

$$f_n=f_{n-1}+1\tag{2}$$

$\forall k\le i<n,f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1\tag{3}$

(3)只要考虑有$\frac{i}{n}$的概率随机到需要被执行的操作上，$\frac{n-i}{n}$的概率随机到不需要的操作上，并且消耗一步

$f_x*n!$就是答案

事实上可以解出来，保留变量$f_n$，由(3)得

$$f_i=\frac{nf_{i+1}-(n-i-1)f_{i+2}-n}{i+1}\tag{4}$$

倒着可以推出$f_k$关于$f_n$的一次式，用(1)解出$f_n$，代入$f_x$即可

做法2

对$f_i$差分，令$g_i=f_i-f_{i-1}$，表示从剩余$i$步到剩余$i-1$步期望的操作次数

由(3)

$$
\begin{align}
\frac{i}{n}(f_i-f_{i-1})&=\frac{n-i}{n}(f_{i+1}-f_i)+1\
\therefore\frac{i}{n}g_i&=\frac{n-i}{n}g_{i+1}+1\
\therefore g_i&=\frac{(n-i)g_{i+1}+n}{i}\tag{5}
\end{align}
$$

且$g_n=1\tag{6}$

这样可以倒着推出$g_i$，最后$$ans=n!* \sum_{i=k+1}^xg_i$$

总复杂度都是$\mathcal O(n\ ln\ n)$

---

代码

1

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
	if (iosig) x = -x;
}

const int N = 100005, P = 100003;
int n, k, x, inv[N];
bool a[N];
vector<int> s[N];
struct num{
	int x, y;
	inline num(){}
	inline num(int a, int b){ x=a, y=b;}
	inline num operator +(const num &rhs)const{ return num((x+rhs.x)%P, (y+rhs.y)%P);}
	inline num operator -(const num &rhs)const{ return num((x-rhs.x)%P, (y-rhs.y)%P);}
	// inline num operator +(int rhs)const{ return num(x, (y+rhs)%P);}
	inline num operator -(int rhs)const{ return num(x, (y-rhs)%P);}
	inline num operator *(int rhs)const{ return num((ll)x*rhs%P, (ll)y*rhs%P);}
}f[N];
inline int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
int main() {
	int nfac=1;
	read(n), read(k);
	for(int i=1; i<=n; ++i) read(a[i]), nfac=(ll)nfac*i%P;
	for(int i=1; i<=n; ++i) for(int j=i; j<=n; j+=i) s[j].push_back(i);
	for(int i=n; i; --i) if(a[i]){
		++x;
		for(int j:s[i]) a[j]^=1;
	}
	if(x<=k) return printf("%lld", (ll)x*nfac%P), 0;
	inv[1]=1;
	for(int i=2; i<=n; ++i) inv[i]=(ll)(P-P/i)*inv[P%i]%P;
	f[n]=num(1, 0);
	f[n-1]=f[n]-1;
	for(int i=n-2; i>=k; --i) f[i]=(f[i+1]*n-f[i+2]*(n-i-1)-n)*inv[i+1];
	int x0=(ll)(k-f[k].y)*Pow(f[k].x)%P;
	return printf("%lld", (((ll)f[x].x*x0+f[x].y)%P+P)%P*nfac%P), 0;
}

2

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
	if (iosig) x = -x;
}

const int N = 100005, P = 100003;
int n, k, x, ans, inv[N], f[N];
bool a[N];
vector<int> s[N];
int main() {
	int nfac=1;
	read(n), read(k);
	for(int i=1; i<=n; ++i) read(a[i]), nfac=(ll)nfac*i%P;
	for(int i=1; i<=n; ++i) for(int j=i; j<=n; j+=i) s[j].push_back(i);
	for(int i=n; i; --i) if(a[i]){
		++x;
		for(int j:s[i]) a[j]^=1;
	}
	if(x<=k) return printf("%lld", (ll)x*nfac%P), 0;
	inv[1]=1;
	for(int i=2; i<=n; ++i) inv[i]=(ll)(P-P/i)*inv[P%i]%P;
	f[n]=1;
	for(int i=n-1; i>k; --i) f[i]=((ll)f[i+1]*(n-i)+n)%P*inv[i]%P;
	for(int i=x; i>k; --i) (ans+=f[i])%=P;
	return printf("%lld", (ll)nfac*(ans+P+k)%P), 0;
}