#PQJ389x3267. QOJ 389_3267
QOJ 389_3267
2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试分手是祝愿(trennen) 分手是祝愿(trennen) 【问题描述】 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 取模之后的结果。 【输入格式】 从文件trennen.in 中读入数据。 第一行两个整数n, k。 接下来一行n 个整数,每个整数是0 或者1,其中第i 个整数表示第i 个灯的初始 情况。 【输出格式】 输出到文件trennen.out 中。 输出一行,为操作次数的期望乘以n 的阶乘对100003 取模之后的结果。 【样例1 输入】 4 0 0 0 1 1 第8 页 共14 页
2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试分手是祝愿(trennen) 【样例1 输出】 512 【样例2 输入】 5 0 1 0 1 1 1 【样例2 输出】 5120 【样例3~8】 见选手目录下的trennen/trennen3~8.in 与trennen/trennen3~8.ans。 【子任务】 • 对于0% 的测试点,和样例一模一样; • 对于另外30% 的测试点,n ≤10; • 对于另外20% 的测试点,n ≤100; • 对于另外30% 的测试点,n ≤1000; • 对于100% 的测试点,1 ≤n ≤100000, 0 ≤k ≤n; • 对于以上每部分测试点,均有一半的数据满足k = n。 第9 页 共14 页