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\)
若剩余最小操作次数\(\le
k\)，你会直接按照最小操作次数操作，并结束
否则每次你会在\([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((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;
}
|