话说为什么会原地爆炸。。。
因为凌晨3:00蜜汁醒来了然后睡不着了。。。整个人都是晕的。。。
然后T1想到了一半的解法,就打了打,后来发现剩下一半是错的,又想了想,可是死活想不出,所以浪费了1.5h,因为整个人都很方。。。然后后面的题目几乎没有怎么想着那
还有最主要的原因是我太辣鸡了QAQ。。。特别是数学这一块。。。
所以本蒟蒻在此立下flag:以后每天都要做一道数学题。

T1

题目描述
大胖研究出了一种数字,名字叫做超级数。
这种数字有一个非常奇葩的属性,就跟大胖样的。
对于每一个超级数,其实都是对于给定的一个正整数 N 的阶乘的一种 B 进制表达,而且末尾恰好为 K 个 0。
现在大胖想知道,对应于某一个正整数 N,到底有多少个超级数?
答案对 1000000009 取模。
数据范围
对于 20%的数据,保证有 $n≤5$ 。
对于 50% 的数据,保证有 $n≤1000000$。
对于 100% 的数据,保证有 $n≤10^{15}$,K大于N/500。
题目分析
如果B进制下x恰好有K个0在末尾,则x能被$B^k$整除且不能被$B^{k+1}$整除
我们假设:
$x=\sum p_i^{a_i}$($p_i$为质数)
$B=\sum p_i^{b_i}$
则如果要保证$x$能被$B^k$整除,$0\leq b_i\leq \lfloor a_i/k \rfloor$
因为这样的话就有$a_i≤b_i * k$啦。
那么$b_i$的值就有$\lfloor a_i/k \rfloor +1$种选择,根据乘法原理乘起来即可,这就是求x能被$B^k$整除的$B$的个数的方法。
用类似的方法求出$B^{K+1}$能整除x的B的个数后相减即可。
至于怎么求$n!$的每一个质因子的个数。。。看代码吧。。。很容易的。。。
由于k非常大,所以质数只要筛500以内的即可。
错误分析
一开始想到要筛素数,素数范围较小之类的,但是陷入了x恰好被$B^k$整除的死胡同,没有想到可以通过减法解决这个问题。
其实只要想到所谓恰好被$B^k$整除就是不能被$B^{k+1}$整除。
代码

T2

题目描述
大胖最近在锻炼身体。(格式,格式,真的只是格式)
他家有一个无比巨大无比巨大的南北向跑道。
我们可以把这条跑道视作一个数轴,大胖家的位置在原点。
这天,大胖收到了大胖父母的指令,要求大胖今天要跑 N 次,每次 1Km,为了体现公平公正的原则,大胖有选择向南跑或者向北跑的权利,而且我们将这 N 次决策视作一个方案,对于任意两个方案如果有一次决策不同那么就视作两个不同的方案(规定对应每一次决策,往南跑为 1,往北跑为 0,则这 N 次决策顺次构成一个 01 序列,若两个 01 序列每一位对应相同,即视作相同方案)。
大胖最近虐现哥出的题目虐到无聊了,于是他决定,他要向南跑 X 次,而且每次大胖都希望自己不出现在自己家的北方。
他想知道,有多少种不同的方案满足自己的要求?答案对 1000000007 取模。
数据范围
对于 20% 的数据,保证有 n≤10。
对于 50% 的数据,保证有 $n≤10^3$。
对于 70% 的数据,保证有 $n≤10^6$,而且数据只有一组。
对于 100% 的数据,保证有 $n≤10^6$,0≤X≤N,数据组数不超过 1000。
错误分析
一看题目:哎呀!这不就是codevs3240吗?设f(i,j)表示向南走i步向北走j步(j≤i),那么$f(i,j)=f(i-1,j)+f(i,j-1)$,好水。
再一看数据范围:。。。当我没说。。。
于是只拿了50分。
题目分析
首先我们可以知道世界上有一道题叫做bzoj3907
这道题目也是一个卡特兰数推广的题目,大概就是如图,你只能走红线以下区域(即对于每一状态,已经走的向右的步数要大于等于向左的步数),每次可以往右或者往上走一格,走到右上角(m,n),m小于等于n,的方案数。

那么我们很容易知道,从左下角走到右上角的总方案数是$C_{n+m}^n$对吧。
由于穿过红线的方案有点难考虑,我们先考虑“碰到红线”就是不可以的。
假如我们第一步向上走,则会产生$C_{n+m-1}^{m-1}$种不可行的方案。
假如我们第一步向左走,如图所示,它如果碰到了红线,关于红线对称一下

那么就有关于第一步向上走的一一对应的方案了。
但是我们现在的问题是不能穿过红线。
于是我们把红线往上移动1个单位,使得n变为n+1。得到:
$ans=C_{n+m+1}^{m}-2*C_{n+m}^{m-1}$
根据通项公式变形:$ans=C_{n+m}^m-C_{n+m}^{m+1}=C_{n+m}^n-C_{n+m}^{n-1}$
因为这题有多组数据,我们可以打表出每一个$i!$的值和逆元,即可O(1)求解。
代码

T3

题目描述
大胖最近在玩中国象棋。
他非常喜欢“車”这个棋子,因为读音和猪肉很像。
而且車能上能下,能左能右,是外出旅行,杀人放火之必需必备必不可少之良器。
现在有一个 N×N 的棋盘,大胖有 N 个車,这些車从 1 到 N 编号,其中第 i 个車不能放在第 i 行也不能放在第 i 列,请问有多少种摆放方法使得这些車互不冲突(意思就是这些車不在同一行且不在同一列)。
请输出方案数对一个数 M 的模值。
数据范围
对于 50% 的数据,保证有 n≤$10^6$。
对于 100% 的数据,保证有 $n≤10^{17}$,$m≤10^6$ 。
错误分析
因为当时有点思维惯性了。。。觉得如果没有错排的限制条件并且不编号就是n!嘛,只编号就是$n! * n!$,所以就认为是错排再乘以n!然后用容斥搞,觉得太难了放弃了。。。
题目分析
假设每个车的位置为(x,y),那么x是一个错排,y是一个错排。设f(i)表示i错排的种类数,则$f(i)=(i-1) * (f(i-1)+f(i-2))$,答案是$f(n) * f(n)$
打表可知答案关于m循环。
代码

T4

题目描述
征夷王将越南(南夷) 攻下来之后, 决定用 N 个火炬摆成一个圆圈, 围住越南的都城,以举火燎天宣告自 己的胜利。
这 N 个火炬的位置已经固定了, 但是, 每个火炬的颜色都没定, 总共有 M 种颜色的火炬。 为了显示我们中华文化的博大精深, 征夷王决定, 相邻的火炬的颜色不能相同。 现在征夷王想知道, 满足他要求的方案有多少个。 由于火炬的位置已经固定, 所以即便旋转翻转之后两种方案相同也视作不同方案。
数据范围
对于 100% 的数据,1≤N,M≤100
错误分析
惯性思维,因为想到了越狱那题,所以以为是组合数学。。。最后打了一个搜索优化,试了试需要高精的数据就肯定过不了,所以开个unsigned然后就这样了。
题目分析
f(i,1)表示点i把火,与第一把火颜色相同的方案数。f(i,0)则是不同的方案数。那么非常容易得到转移方程:$f(i,1)=f(i-1,0)$.$f(i,0)=f(i-1,1) * (m-2)+f(i-1,0) * (m-1)$
但是这个数据范围。。。肯定要写高精。。。在欢声笑语中打出GG。
代码