LGR-060 2019洛谷10月月赛I

LGR-060 2019洛谷10月月赛I

小猪佩奇玩游戏

请先思考后再展开

一个经典的期望模型:给出一个dag,删除一个点就会把所能到达的所有点删除,每次随机选择一个没有被删除的点删除,问期望步数。考虑一个点被选择的概率,等价于对期望的贡献,设有k个点可到达自己,感性理解一下应该和别的点无关,$\frac{1}{k+1}$

考虑如何计算一个点可以被到达多少次,枚举题意中k,$\sum_{k=2} \sum_{i=2}^{log_k n} 更新i^k$,丢hash表里即可,最后hash表大小仅32669,明显能过

1
2
3
4
5
6
7
8
9
10
11
12
13
unordered_map<int,int> cnt;
typedef unordered_map<int,int>::iterator IT;
void main()
{
fo(k,2,30) for(int i=2;pow(i,k)<=1e9;i++) cnt[pow(i,k)]++;
int T=qread();
while(T--)
{
int n=qread(),oth=n;double ans=0;
for(IT a=cnt.begin();a!=cnt.end();a++) if(a->FR<=n) oth--,ans+=1.0/(a->SE+1);
ans+=oth;printf("%lf\n",ans);
}
}

赛车游戏CF241E Flights

请先思考后再展开

首先将1不可达或不可达n的点去掉,剩下的如果有解一定是个dag

$1 \le d_y-d_x \le 9$,直接差分约束,bellman-ford即可

code

小猪佩奇学数学

请先思考后再展开

$$
先考虑k=1,ans=\sum_{i=0}^n C_n^i p^i*i=pn*\sum_{i=0}^{n-1} C_{n-1}^i p^i=pn*(p+1)^{n-1} \\
受此启发,ans=\sum_{i=0}^n C_n^ip^i* \frac{i-i\%k}{k}=\frac{1}{k}*(pn*(1+p)^{n-1}-\sum_{r=0}^{k-1} r*\sum_{i=0}^n [i\%k=r]C_n^ip^i ) \\
单位根反演,a_i=C_n^ip^i,f(x)=\sum_{i=0}^{\infty} a_i x^i=(px+1)^n\\
\sum_{r=0}^{k-1} r*\sum_{i=0}^n [i\%k=r]C_n^ip^i
=\frac{1}{k}\sum_{r=0}^{k-1} r*\sum_{i=0}^n a_i \sum_{t=0}^{k-1} \omega_{k}^{(i-r)t}
=\frac{1}{k}\sum_{r=0}^{k-1} r*\omega_k^{-rt}*\sum_{t=0}^{k-1} \sum_{i=0}^n a_i \omega_{k}^{it} \\
=\frac{1}{k}\sum_{r=0}^{k-1} r*\omega_k^{-rt}*\sum_{t=0}^{k-1} f(\omega_{k}^{t})
=\frac{1}{k}\sum_{t=0}^{k-1} f(\omega_{k}^{t}) (\sum_{r=0}^{k-1} r*\omega_k^{-rt}),后面是个差比数列求和 \\
ans=\frac{1}{k}*(pn*(p+1)^{n-1}- \frac{1}{k}\sum_{t=0}^{k-1} f(\omega_{k}^{t})*getsum(\omega_k^{-t},k) ) \\
getsum(A,n)=\sum_{i=0}^{n-1} iA^i=[A=1]\frac{(n-1)n}{2} +[A \ne 1]\frac{1}{1-A} (\frac{A^n-1}{A-1}-A^n(n-1)-1),O(nlogn)
$$

没有优化常数,跑得很慢;另外直接写个IDFT应该也是可以的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll getsum(int A,int n)
{
if(A==1) return (ll(n-1)*n/2)%MOD;
ll x=(qpower(A,n)-1)*invm(A-1)%MOD;
return (x-qpower(A,n)*(n-1)%MOD-1)%MOD*invm(1-A)%MOD;
}
ll getomega(int n,int k){return qpower(3,(MOD-1)/n*k);}
ll n,p,k;
ll getf(int x){return qpower( (p*x%MOD+1)%MOD,n);}
void main()
{
n=qread(),p=qread(),k=qread();
ll ans=p*n%MOD*qpower( (p+1)%MOD ,n-1)%MOD;
fo(t,0,k-1) {ll w=getomega(k,t);ans-=invm(k)*getf(w)%MOD*getsum(invm(w),k)%MOD,ans%=MOD;}
ans=ans*invm(k)%MOD;write((ans+MOD)%MOD);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4269b7e7.html
转载请注明出处,谢谢!