挑了几道可做的做了，难度大概升序排序
F New Year and Arbitrary Arrangement
New Year and Arbitrary Arrangement
期望dp，考虑逆推。
考虑设\(f_{i,j}\)为有\(i\)个\(a\)，当前序列有\(j\)个\(ab\)的期望长度。
有\(f_{i,j}=f_{i+1,j}\times p_a+f_{i,j+i}\times p_b\)
目标要设为为\(f_{1,0}\)，因为\(f_{0,0}\)会从自身转移，因为如果前面没有\(a\)的话会无限加\(b\)，目标状态设为\(f_{1,0}\)可以避免这个问题。
考虑边界，容易发现当\(i+j\ge k\)时就是边界，因为再加入一个\(b\)就停止了。
考虑如何求\(f_{i,j}(i+j\ge k)\)。
记\(A=\frac{p_a}{p_a+p_b},B=\frac{p_b}{p_a+p_b}\)
\[\begin{aligned} f_{i,j}&=B\times \sum_{a=0}^{\infty}(i+j+a)A^a\quad(\text{a是枚举又加入的$a$的个数})\\ &=B\times \sum_{i=0}^{\infty}(c+i)A^i\quad(\text{为方便，记c=i+j,将a替换为i})\\ &=(1-A)\times\sum_{i=0}^{\infty}(c+i)A^i\quad(\text{发现B=1-A，替换})\\ &=(1-A)\times\sum_{i=0}^{n}(c+i)A^i\quad(\text{写$\infty $不直观，将其替换为n，方便下面变形})\\ &=\sum_{i=0}^n(c+i)A^i-\sum_{i=0}^n(c+i)A^{i+1}\quad(\text{拆开})\\ &=c+\sum_{i=1}^n(c+i)A^i-\sum_{i=1}^{n}(c+i-1)A^i+(c+n)\times A^{n+1}\\ &=c+\sum_{i=1}^nA^i+(c+n)\times A^{n+1}\\ &=i+j+\frac{p_a}{p_b}\quad (\text{当$\lim\limits_{n\to\infty},0<A<1$时，$(c+n)\times A^{n+1}=0$，$\sum\limits_{i=1}^nA^i=\frac{A}{1-A}=\frac{p_a}{p_b}$}) \end{aligned}\]然后这道题用记搜就做完了。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define InF(x) freopen(x".in","r",stdin)
#define OutF(x) freopen(x".out","w",stdout)
#define ErrF(x) freopen(x".err","w",stderr)
#define AnsF(x) freopen(x".ans","w",stdout)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = InF("in"),*OutFile = OutF("out");
// FILE *ErrFile = ErrF("err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e3 + 10,mod = 1e9 + 7;
inline int power(int a,int b,int mod){
int res = 1;
for(;b;b >>= 1,a = 1ll*a*a%mod) if(b&1) res = 1ll*res*a%mod;
return res;
}
int k,pa,pb,inv,inv1,inv2,inv3,f[N][N];
bool vis[N][N];
int dp(int x,int y){
if(x + y >= k) return (x+y+inv3)%mod;
if(vis[x][y]) return f[x][y];
vis[x][y] = true;
int res = 0;
res = (res + 1ll*dp(x+1,y)*inv1%mod)%mod;
res = (res + 1ll*dp(x,x+y)*inv2%mod)%mod;
return f[x][y] = res;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>k>>pa>>pb;
inv = power(pa+pb,mod-2,mod);
inv1 = 1ll*pa*inv%mod,inv2 = 1ll*pb*inv%mod,inv3 = 1ll*pa*power(pb,mod-2,mod)%mod;
cout<<dp(1,0);
}
E - Steps to One
由于个人习惯，以下的\(n\)表示题目中的\(m\)
设\(f_{i}\)为当前数列的\(gcd\)为\(i\)，且\(gcd\)变为1还需要的期望步数。
显然有\(ans=1+\frac{\sum\limits_{i=1}^nf_i}{n}\)
转移方程为\(f_k=1+\frac{\sum\limits_{i=1}^nf_{\gcd(i,k)}}{n}\)
考虑优化\(\sum\limits_{i=1}^nf_{\gcd(i,k)}\)，推柿子。
看到了\(\gcd\)。考虑莫反。
\[\begin{aligned} \sum_{i=1}^nf_{\gcd(i,k)}&=\sum_{d|k}f_d\sum_{i=1}^n[gcd(i,k)=d]\\ &=\sum_{d|k}f_d\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{k}{d})=1]\\ &=\sum_{d|k}f_d\sum_{i=1}^{\frac{n}{d}}\sum_{t|gcd(i,\frac{k}{d})}\mu(t)\\ &=\sum_{d|k}f_d\sum_{t|\frac{k}{d}}\mu(t)\left\lfloor\frac{n}{dt}\right\rfloor\\ &=\sum_{T|k}\left\lfloor\frac{n}{T}\right\rfloor\sum_{d|T}f_d\mu(\left\lfloor\frac{T}{d}\right\rfloor) \end{aligned}\]所以就有了\(f_i=\frac{\sum\limits_{T|k}\left\lfloor\frac{n}{T}\right\rfloor\sum\limits_{d|T}f_d\mu(\left\lfloor\frac{T}{d}\right\rfloor)}{n}+1\)
再考虑把整个柿子当成一个以\(f_i\)为未知量的方程解。
\[\begin{aligned} f_i&=\frac{\sum\limits_{T|k}\left\lfloor\frac{n}{T}\right\rfloor\sum\limits_{d|T}f_d\mu(\left\lfloor\frac{T}{d}\right\rfloor)}{n}+1\\ f_i&=\frac{\sum\limits_{T|k}\left\lfloor\frac{n}{T}\right\rfloor\sum\limits_{d|T,d<i}f_d\mu(\left\lfloor\frac{T}{d}\right\rfloor)}{n}+1+\frac{\left\lfloor\frac{n}{i}\right\rfloor\times f_i}{n}\\ f_i&=\frac{\sum\limits_{T|k}\left\lfloor\frac{n}{T}\right\rfloor\sum\limits_{d|T,d<i}f_d\mu(\left\lfloor\frac{T}{d}\right\rfloor)+n}{n-\left\lfloor\frac{n}{i}\right\rfloor} \end{aligned}\]然后设\(dp_i=\sum\limits_{d|T,d<i}f_d\mu(\left\lfloor\frac{T}{d}\right\rfloor)\)。
更新\(dp\)的话暴力跑就行，复杂度\(O(n\log n)\)。
至于\(d<i\)的条件，先更新\(f\)再更新\(dp\)就可以了。
复杂度\(O(n\log n)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define InF(x) freopen(x".in","r",stdin)
#define OutF(x) freopen(x".out","w",stdout)
#define ErrF(x) freopen(x".err","w",stderr)
#define AnsF(x) freopen(x".ans","w",stdout)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = InF("in"),*OutFile = OutF("out");
// FILE *ErrFile = ErrF("err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10,mod = 1e9 + 7;
#define eb emplace_back
inline int power(int a,int b,int mod){
int res = 1;
for(;b;b >>= 1,a = 1ll*a*a%mod) if(b&1) res = 1ll*res*a%mod;
return res;
}
int n,f[N],dp[N],mu[N],inv[N];
bitset<N> pd;
vector<int> prime,fac[N];
inline void get_mu(int n){
mu[1] = 1;
for(int i = 2;i <= n; ++i){
if(!pd[i]) prime.eb(i),mu[i] = -1;
for(int j:prime){
if(i * j > n) break;
pd[i*j] = true;
if(i%j == 0) break;
mu[i*j] = -mu[i];
}
}
}
inline void solve(){
cin>>n;get_mu(n);
rep(i,1,n,1) rep(j,i,n,i) fac[j].eb(i);
rep(i,1,n,1) inv[i] = power(i,mod-2,mod);
rep(i,1,n,1){
f[i] = n;
for(int T:fac[i]) f[i] = (f[i] + 1ll*(n/T)%mod*dp[T]%mod + mod)%mod;
f[i] = 1ll*f[i]*power(n-n/i,mod-2,mod)%mod;
for(int j = i;j <= n;j += i)
dp[j] = (dp[j] + 1ll*f[i]*mu[j/i]%mod + mod)%mod;
}
int ans = 0;
rep(i,1,n,1) ans = (ans + f[i])%mod;
ans = 1ll * ans * inv[n]%mod;
cout<<(ans+1)%mod;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
持续更新中……
标签：专题,frac,int,vjudge,sum,数学,res,using,mod From： https://www.cnblogs.com/hzoi-Cu/p/18468493