0%

「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;
}