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