T1.supernum

题意:求N!在多少个进制下末尾恰有k个0
思路:将N!分解为素数幂次之积。然后得出有多少B满足$B^k|N!$而$B^k$不整除N!

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define MX 100002
#define MD 1000000009

using namespace std;

typedef long long ll;

ll prm[MX+1],pnum;
char vis[MX+1];

void init()
{
    for(int i=2;i<=MX;)
    {
        prm[++pnum]=i;
        for(int j=1;j*i<=MX;j++)vis[j*i]=1;
        while(vis[i])++i;
    }
}

ll n,k;
ll num[MX+1];
ll num1[MX+1],num2[MX+1];
ll can[MX+1];
ll but[MX+1];

void work()
{
    ll ans1=1,ans2=1;
    cin>>n>>k;
    for(ll i=1;i<=pnum;i++)
        for(ll tmp=prm[i];tmp<=n;tmp*=prm[i])
            num[i]+=n/tmp;
    for(int i=1;i<=pnum;i++)can[i]=num[i]/k;
    for(int i=1;i<=pnum;i++)but[i]=num[i]/(k+1);
    for(int i=1;i<=pnum;i++)ans1=ans1*(can[i]+1)%MD,ans2=ans2*(but[i]+1)%MD;
    cout<<(ans1-ans2+MD)%MD<<endl;
}

int main()
{
    freopen("supernum.in","r",stdin);
    freopen("supernum.out","w",stdout);
    init();
    work();
    return 0;
}



T2.road

题意:在一条数轴上走n步,每次走1个单位,共要向左走x次,求有多少种走法使其永远不出现在正半轴上。
思路:一一对应解题,可知


$$
ans=C_n^{x-1}-C_n^{x+1}
$$


#include <iostream>
#include <cstring>
#include <cstdio>

#define MD 1000000007

using namespace std;

typedef long long ll;

ll frc[1000001];

ll ksm(ll x,ll t)
{
    ll ans=1;
    while(t)
    {
        if(t&1)ans=ans*x%MD;
        x=x*x%MD;
        t>>=1;
    }
    return ans;
}

ll inv(ll x)
{
    return ksm(x,MD-2);
}

void init()
{
    frc[1]=1;
    for(ll i=2;i<=1000000;++i)
        frc[i]=frc[i-1]*i%MD;
}

ll C(ll n,ll m)
{
    if(n==m)return 1;
    else if(m>n)return 0;
    else return frc[n]*inv(frc[m]*frc[n-m]%MD)%MD;
}

void work()
{
    ll n,x;
    while(cin>>n>>x)
    {
        if(x*2<n||x>n)cout<<0<<endl;
        else if(x==n)cout<<1<<endl;
        else if(x==n-1)cout<<x<<endl;
        else cout<<(C(n-1,x-1)+MD-C(n-1,x+1))%MD<<endl;
    }
}

int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    init();
    work();
    return 0;
}

T3.Chess

题意:一个n行n列棋盘上放n个车使其互不攻击的方案数%m(m<=1000000,n<=1e17)
思路:错排的平方,modm是循环的,因此可以很快求解。

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll f[2000004];
ll n,m;

void work()
{
    f[1]=0;
    f[2]=1;
    for(int i=3;i<=m*2;i++)f[i]=(i-1)*(f[i-1]+f[i-2])%m;
    cout<<f[n%m]*f[n%m]%m<<endl;
}

int main()
{
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    cin>>n>>m;
    work();
    return 0;
}

T4.Lights

题意:n盏灯(n<=100)围成一个圈,每个灯可以涂m种颜色,求相邻的灯颜色各不相同的方案数。
思路:容斥(O(n))或DP(O(nnn))还要高精度

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 103

using namespace std;

typedef long long ll;

typedef struct lints
{
    int x[300];
    int len;
}lint;

void out(lint g)
{
    if(g.len==0)cout<<0<<endl;
    else for(int i=g.len;i>=1;i--)cout<<g.x[i];cout<<endl;
}

lint add(lint a,lint b)
{
    int len=max(a.len,b.len),x;
    lint c;
    c.len=len;
    for(int i=1;i<=300;i++)c.x[i]=0;
    for(int i=1;i<=len+1;i++)
    {
        c.x[i]=(a.x[i]+b.x[i]+x)%10;
        //cout<<c.x[i]<<endl;
        if(a.x[i]+b.x[i]+x>=10)x=1;
        else x=0;
    }
    if(c.x[len+1])len++;
    c.len=len;
    return c;
}

lint f[MX][MX],ans;

int main()
{
    freopen("lights.in","r",stdin);
    freopen("lights.out","w",stdout);
    int n,m;
    cin>>n>>m;
    if(n==1){cout<<m<<endl;return 0;}
    f[1][1].len=1;
    f[1][1].x[1]=1;
    for(int i=2;i<=n+1;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=m;k++)
                if(k!=j)
                    f[i][j]=add(f[i][j],f[i-1][k]);//f[i][j]+=f[i-1][k];
    for(int i=1;i<=m;i++)ans=add(ans,f[n+1][1]);
    out(ans);

    return 0;
}
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *