话说为什么会原地爆炸。。。
因为凌晨 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}$整除。
代码：
#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
int pri[505],is[505];
LL n,m,mod=1000000009;int tot;
void init(){
for(int i=2;i<=500;i++){
if(!is[i])pri[++tot]=i;
for(int j=1;j<=tot&&pri[j]*i<=500;j++){
is[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
}
LL work(LL x,LL y){
LL re=1;
for(LL i=1;pri[i]<=x;i++){
LL kl=x,js=0;
while(kl){kl/=pri[i],js+=kl;}//求质因子个数
if(!(js/y))break;
re=(re*(js/y+1))%mod;
}
return re;
}
int main()
{
freopen("supernum.in","r",stdin);
freopen("supernum.out","w",stdout);
init();scanf("%lld%lld",&n,&m);
printf("%lld\n",(work(n,m)-work(n,m+1)+mod)%mod);
return 0;
}
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）求解。
代码：
#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define N 1000000
LL mod=1000000007;
LL jie[N+5],ni[N+5],n,m,ans;
LL ksm(LL x,LL y){
LL re=1;
while(y){
if(y&1)re=(re*x)%mod;
x=(x*x)%mod,y>>=1;
}
return re;
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
jie[0]=ni[0]=1;
for(LL i=1;i<=N;i++)jie[i]=(jie[i-1]*i)%mod;
ni[N]=ksm(jie[N],mod-2);
for(LL i=N-1;i>=1;i--)ni[i]=(ni[i+1]*(i+1))%mod;
while(scanf("%lld%lld",&n,&m)==2){
n=n-m;if(m<n){printf("0\n");continue;}
ans=jie[n+m]*ni[n]%mod*ni[m]%mod;
ans=(ans+mod-jie[n+m]*ni[m+1]%mod*ni[n-1]%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
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 循环。
代码：
#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL n,m;
LL f[1000005];
int main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
scanf("%lld%lld",&n,&m);
n=(n-1)%m+1;
f[1]=0,f[2]=1;
for(LL i=3;i<=n;i++)f[i]=((i-1)%m)*((f[i-1]+f[i-2])%m)%m;
printf("%lld",(f[n]*f[n])%m);
return 0;
}
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。
代码：
#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define MOD 10000
struct bign{
int len,s[100];
bign(){memset(s,0,sizeof(s)),len=1;}
bign operator * (int a){
bign c;c.len=len+1;
for(int i=1;i<=len;i++){
c.s[i+1]=(c.s[i]+s[i]*a)/MOD;
c.s[i]=(c.s[i]+s[i]*a)%MOD;
}
while(!c.s[c.len]&&c.len>1)--c.len;//注意不要把 c. 什么什么写漏了！
return c;
}
bign operator + (bign a){
bign c;c.len=max(len,a.len);
for(int i=1;i<=len;i++){
c.s[i+1]=(c.s[i]+a.s[i]+s[i])/MOD;
c.s[i]=(c.s[i]+a.s[i]+s[i])%MOD;
}
while(c.s[c.len+1])++c.len,c.s[c.len+1]=c.s[c.len]/MOD,c.s[c.len]%=MOD;
return c;
}
void print(){
for(int i=len;i>=1;i--){
if(i!=len)printf("%04d",s[i]);
else printf("%d",s[i]);
}
}
}f[105][2];
int n,m;
int main()
{
freopen("lights.in","r",stdin);
freopen("lights.out","w",stdout);
scanf("%d%d",&n,&m);
if(n==1){printf("%d",m);return 0;}
f[1][1].s[1]=m;
for(int i=2;i<=n;i++){
f[i][1]=f[i-1][0];
f[i][0]=f[i-1][0]*(m-2)+f[i-1][1]*(m-1);
}
f[n][0].print();
return 0;
}
