分手是祝愿:dp
Description
Zeit und Raum trennen dich und mich.
时空将你我分开。
B 君在玩一个游戏,这个游戏n个灯和n个开关组成,给定这n个灯的初始状态,下标为从1到n的正整数。
每个灯有两个状态亮和灭,我们用1来表示这个灯是亮的,用0表示这个灯是灭的,游戏的目标是使所有灯都灭掉。
但是当操作i个开关时,所有编号为i的约数(包括1和i)的灯的状态都会被改变,即从亮变成灭,或者是从灭变成亮。
B 君发现这个游戏很难,于是想到了这样的一个策略,每次等概率随机操作一个开关,直到所有灯都灭掉。
这个策略需要的操作次数很多,B 君想到这样的一个优化。如果当前局面,可以通过操作小于等于k个开关使所有灯都灭掉
那么他将不再随机,直接选择操作次数最小的操作方法(这个策略显然小于等于k步)操作这些开关。
B 君想知道按照这个策略(也就是先随机操作,最后小于等于k步,使用操作次数最小的操作方法)的操作次数的期望。
这个期望可能很大,但是 B 君发现这个期望乘n的阶乘一定是整数,所以他只需要知道这个整数对100003取模之后的结果。
1<=n<=100000,0<=k<=n。对于50%的数据,k=n。
这题也是咕了好久啊,今天难得改题快,回来把它干了。
然而我颓题解了,想了几次了也没有想出来,呃。。。颓题解再怎么样也比干脆不做好一些
这题的主要难点在于如何确定状态定义,其它的其实还好。
看那个50%的部分分(数据水了,能拿80。。。)
也就是我们先考虑最优决策是什么。
首先,你操作编号小的开关,编号大的那个灯泡不会有反应。
所以对于编号最大的亮的那个灯,你想让它灭掉,只有两个方法。
一个是按掉它的开关,另一个是按掉比它更大的开关。
但是因为这已经是亮的里编号最大的了,那么如果你按一个编号更大的开关,那么亮的灯泡里编号上界就更大了。
这样的话迟早会涨到n左右,然后这时候我们只能关闭它自己。。。然后直到恢复初始状态。
所以你当然会直接按掉它自己。
这之后编号最大的亮灯编号变小了,继续同理解决问题即可。
这样我们就拿到了这个部分分。
但是直到这里,和我们的dp还是没有什么关系。
但是我们可以发现一些性质:
任意一个开关,都不能被其它的开关集合等价代替。
这样的话,给定我们一个初始状态,我们能像那个部分分一样求出它需要的开关集合。
这样的话,我们就可以断言,那些开关需要你动,那些开关你不能动。
而它是随机操作的,那么如果动了那些你不能动的开关。。。那么你还得再动一次让它回复原状
这就是异或操作,具有“操作偶数次等于没操作”和“交换操作顺序结果不变”的性质。
到了这里,我们开始构造dp数组的含义。
我们发现,现在开关到底是什么已经不重要了,开关只有两种:你需要动的,你不能动的
那么其实你只需要知道你还需要动几个开关就可以了
设$dp[i]$表示还有i个开关需要操作,想按对一个开关期望需要多少次操作。考虑转移:
你有$\frac{i}{n}$的概率按对,那么就是$\frac{i}{n}$
你有$\frac{n-i}{n}$的概率按错,这时候需要按的变成了$i+1$个,
于是先按$1$下到$i+1$步,再回来是$dp[i+1]$,而且你还要再按掉一个,是$dp[i]$。
于是$dp[i]=\frac{i}{n} + \frac{n-i}{n} \times (dp[i+1]+dp[i]+1)$
把$dp[i]$合并同类项,再化一下系数,得到$dp[i]=1+\frac{n-i}{i}\times (dp[i+1]+1)$
那么答案就是先把原有的cnt个按成k个,再把k个用最优决策判掉。
$ans=k+\sum\limits_{i=k+1}^{cnt} dp[i]$
当然如果cnt<=k的话答案就是cnt啊。
最后按照题意乘上$n!$即可。
#include<cstdio>
#define mod 100003
#define int long long
int dp[mod],st[mod],cnt,n,k,ans;
int qp(int b,int t,int a=){for(;t;t>>=,b=b*b%mod)if(t&)a=a*b%mod;return a;}
main(){
scanf("%lld%lld",&n,&k);
for(int i=;i<=n;++i)scanf("%lld",&st[i]);
for(int i=n;i;--i)if(st[i]){
cnt++;
for(int j=;j*j<=i;++j)if(i%j==){
st[j]^=;if(j*j!=i)st[i/j]^=;
}
}
if(cnt<=k){
for(int i=n;i;--i)cnt=cnt*i%mod;
printf("%lld\n",cnt);
return ;
}
dp[n]=;
for(int i=n-;i;--i)dp[i]=((n-i)*qp(i,mod-)%mod*(dp[i+]+)+)%mod;
for(int i=k+;i<=cnt;++i)ans=(ans+dp[i])%mod;ans+=k;
for(int i=n;i;--i)ans=ans*i%mod;
printf("%lld\n",ans);
}
好题,思路很不错。
其实这么顺下来貌似不是很难,但是为什么想不出来呢?
我和正解思路之间的距离。。。
还需要多练啊。
最新文章
- SQL Server被锁的表以及解锁
- (转载)如何借助KeePassX在Linux上管理多个密码
- 2016年12月17日 星期六 --出埃及记 Exodus 21:12
- ORA-12547:TNS:lost contact 问题分析思路
- web前端开发分享-css,js进阶篇
- 段错误bug的调试
- 深入研究-webkit-overflow-scrolling:touch及ios滚动
- phpstorm 代码注释后,撤销某段代码的注释的,快捷键是什么?
- vue-element 动态单选多选全选
- net core体系-web应用程序-4asp.net core2.0 项目实战(1)-3项目架构说明
- [转]Go语言中的make和new
- 腾讯云主机及CentOS7.2简单上手体验
- hdu3255扫描线:带权面积交转体积交
- Java知多少(102)多媒体基础
- CString成员函数详解[转]
- MyCat - 背景篇(1)
- querySelectorAll 方法和 getElementsBy 系列方法的区别
- SQL竖列变横列
- vue 子父组件之间的通信,及在调用组件的地方
- leetcode--笔记8 Fizz Buzz