「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

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}