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;
}