话说为什么会原地爆炸。。。
因为凌晨 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;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望