夜夜十三岁啦
作为女孩子，夜夜憧憬着自己的未来
如果NOIP能满分就好了！如果能有男朋友就好了！如果有人能送我花裙子就好了！
一场NOIP提高组难度的模拟赛，如果你们都能来参加就好了！

开始时间 2015-10-03 18:30:00
结束时间 2015-10-03 21:30:00

NOIP模拟赛
题目难度: NOIP提高组
赛制 OI
题量 4题

主办 少女夜夜
负责 twd2

<<<实时更新>>>
+--------------------------------------------------------------------------------------+
* 比赛所有题目的内存限制都是512MB，时间限制请参见每一题。
* 所有题目均以最后一次提交为准，请避免编译错误。
* 详细帮助请参阅https://vijos.org/wiki/help#contest
* 比赛结束前均可在比赛页面右边点击参加比赛来参与比赛。
* C++选手请慎用cin cout, 比赛的评测机为Windows Server 2008 R2 对于64位整数, 可以采用 %I64d 。
* 18:32 比赛已经开始了，祝各位好运
* 19:03 比赛已经开始30mins了，后台工作人员twd2决定亲自上场参加比赛
* 19:50 请注意，第二题中，0<=X,A,B<C且X,A,B都是整数
* 20:25 请注意，第三题第二个样例的输出有误，应该是16.0。
* 20:28 此外，请注意，c/c++选手对于double的输出，请采用%f而不要用%lf
* 21:30 比赛结束啦，夜夜在此一鞠躬

+--------------------------------------------------------------------------------------+

解题报告

Problem A：

因为(1! + 2! + .. +n!) %m = 1!%m + 2!%m + ... +n!%m，显然如果n>=m则n!%m=0。
因为有一个点的n在10^8以内,所以有些人60分
有些人没数清楚几个0?用int读入的应该是90分,挂在第六个点,自然溢出后n是负的

Problem B:

对于15%的数据：直接输出无解。通过:6,7,8三个点。

对于20%的数据：直接把0 0 0...c-1 c-1 c-1输出，通过:1,2,3,4四个点。
上面两个可以结合，35分。

对于45%的数据：直接暴力X,A,B,O(N)暴力判定，通过:1,2,3,4,6,7,8,9,10九个点。
如果加一个break，可以额外通过11,12,13,14,15五个点，即70分。

对于70%的数据：前45%同上。
考虑c>n-10，那么我们可以发现X(c+i)=(X(c+i-1)*A+B)%c%(c+i)，那么外层就没有意义了，所以X(c+i)=(X(c+i-1)*A+B)%c。
枚举X,A可以求B。通过：11，12，13，14，15五个点，25分。
加上上面算法，70分。

对于95%的数据：前45%同上。
在上面算法的基础上，我们发现，X(c+i)的后继应该是固定的，如果有不同,直接输出Unsuccess。
那么这样判定变成了O(c)的，即判定每个后继是否对应。可以通过:11,12,13,14,15,16,17,18,19,20五个点。

对于100%的数据：余下的部分一定是N=O(c)的，考虑用O(c^2N)的算法即可。

Problem C:

令X[i]为从i出发，首次抵达N的期望用时。那么X[N]=0。
对于i<N，X[i]可以由其余的X得到。比如说，在样例2中X[2]=(1/2)*(X[1]+1+X[2]+1)。
这样我们可以得到一个N元方程组，其中X[N]=0固定。解方程后的解X[1]就是问题的答案。

Problem D:

对于20%的数据：答案不会很大，可以直接枚举B和C。

对于80%的数据：动态规划。
考虑F[i][j][0/1][0/1][0/1]表示用了i根火柴棒，考虑了A,B和C的最低i位。
其中A,B是否已经结束（即是否不会有更高位），以及是否需要进位分别用2*2*2的状态表示。
转移的时候枚举最高位的情况，时间复杂度O(n^2)。

对于100%的数据，考虑上述中j所在这一维不要，时间复杂度O(n)。
.
.
+--------------------------------------------------------------------------------------+
.
.
.
【投票环节－今天的比赛你最喜欢哪一题，哪一题出得最良心？】
A. 第一题
B. 第二题
C. 第三题
D. 第四题
.
参与回答的同学将有机会获得精美礼品哦 ^_^