BZOJ 3113: Toy

外面有一圈 N 个结点，中心有一个结点与 N 个结点都相连，总共就是 $2\cdot N$ 条边，删除 N 条边，使 N+1 个点连通，旋转相同视为等价，问有多少种情况。

Input

输入 N，M
3<=N<=10^9, 2<=M<=10^9

Output

输出方案数 Mod M 的结果

Sample Input

3 10000
4 10000
4 10

Sample Output

6
13
3

Solution

考虑 burnside 引理，假设分成 $d$ 块，那么每块的方案数是和 bzoj1002 一样的，可以用公式 $f(n+1) = 3f(n) - f(n-1) + 2$ 计算。

所以得到这个公式：$\frac 1 n \sum_{d \mid n} \varphi(\frac n d)\cdot f(d)$。 于是直接 $\sqrt n$ 枚举 d，然后 $\sqrt d$ 求 $\varphi$，矩阵快速幂求 $f$。

Code

#include<bits/stdc++.h>

typedef long long ll;
typedef long double ldb;

ll mod;

inline ll fm(ll x,ll y)
{
    ll tmp=(x*y-(ll)((ldb)x/mod*y+1e-8)*mod);
    return tmp<0?tmp+mod:tmp;
}

inline void mul(ll (&a)[3][3],ll (&b)[3][3],ll (&c)[3][3])
{
    ll t[3][3]={{0,0,0},{0,0,0},{0,0,0}};
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                t[i][k]+=fm(a[i][j],b[j][k]);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            c[i][j]=t[i][j]%mod;
}

inline ll f(int x)
{
    if(x<=1)return x;
    x--;
    ll a[3][3]={{1,0,2},{0,0,mod-1},{0,1,3}},b[3][3]={{1,0,0},{0,1,0},{0,0,1}};
    for(int i=1;i<=x;i<<=1)
    {
        if(i&x)mul(b,a,b);
        mul(a,a,a);
    }
    ll ret=b[0][2]+b[2][2];
    if(ret>=mod)return ret-mod;return ret;
}

inline int phi(int x)
{
    int t=x;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
        {
            t/=i,t*=i-1;
            x/=i;
            while(x%i==0)x/=i;
        }
    if(x>1)t/=x,t*=x-1;
    return t;
}

int main()
{
    int n;
    while(~scanf("%d%lld",&n,&mod))
    {
        mod*=n;
        ll a2=0;
        for(int i=1;i*i<=n;i++)
            if(n%i==0)
            {
                if(i*i==n)
                {
                    a2+=fm(phi(i),f(i));
                }
                else
                {
                    a2+=fm(phi(i),f(n/i))+fm(phi(n/i),f(i));
                }
                a2%=mod;
            }
        printf("%lld\n",a2/n);
    }
}

日期： 2016-11-29

标签： BZOJ 数论 burnside引理

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/87/ 查看。