【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]

【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]BirthdayToyTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):466    AcceptedSubmission(s):238ProblemDescriptionAekdyCoinloves

大家好,又见面了,我是你们的朋友全栈君。

Birthday Toy

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 466    Accepted Submission(s): 238




Problem Description
AekdyCoin loves toys. It is AekdyCoin’s Birthday today and he gets a special “Toy”.

The “Toy” is in bulk and AekdyCoin has to make one by him. Let’s assume that the “Toy” has N small white beads and one Big bead .If someone want to make a “Toy”, he (or she) must always puts the Big bead in center, and then connect the other N small beads around it by using N sticks with equal length, and then the N small beads must be connected by N sticks with equal length, and it could be seen as a regular polygon. Figure 1 shows a “Toy” with 8 small white beads and one big white bead.



【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]


Now AekdyCoin has C kinds of available color, say blue, green, yellow, pink …etc. He wants to color these beads, but he thinks that must be too boring and stupid. So he colors these beads with one role: any adjacent beads couldn’t have same color. Figure 2 shows a legal situation, and Figure 3 shows an illegal situation.



【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]




【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]


It seems that the “Toy” becomes more interesting for AekdyCoin right now; however, he wants to color the big bead in center. Of course, he should follow the role above.

Now AekdyCoin begins to play with the “Toy”, he always colors the big beads and then the other small beads. He should color under the rule above. After several minutes, AekdyCoin finally makes a perfect “Toy”. Figure 4 shows a situation that is under the color rule.



【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]


AekdyCoin now want to know the different method to color the “Toy” whit at most K color. (“Toy” contains N small beads and one big bead.)

But, no, the problem is not so easy .The repetitions that are produced by rotation around the center of the circular necklace are all neglected. Figure 5 shows 8 “Toy”, they are regard as one method.


【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]


Now AekdyCoin will give you N and K, he wants you to help him calculate the number of different methods, because the number of method is so huge, so AekdyCoin just want you to tell him the remainder when divided by M.

In this problem, M = 1,000,000,007.

 


Input
The input consists of several test cases.(at least 1000)

Every case has only two integers indicating N, K 

(3<=N<=10^9, 4<=K<=10^9)

 


Output
For each case, you should output a single line indicates the remainder of number of different methods after divided by M.
 


Sample Input
  
  
  
3 4 3 5 3 17 162 78923
 


Sample Output
  
  
  
8 40 19040 19469065
 


Source

题意:n个小圆组成的正n边形,中间有一个大圆。有木棍相连的两个圆不能有相同的颜色,旋转后相同视为相同的方案,求着色方案数。

【HDU2865】构造矩阵+Burnside定理+欧拉函数类似poj2888[通俗易懂]

设有n个小圆,k种颜色(3<=N<=10^9, 4<=K<=10^9)。

首先,很容易想到从k种选一种给大圆,然后用k-1种颜色对小圆着色。

若不存在相邻圆颜色不同这个限制,则直接Burnside定理。

若存在限制,但是颜色种数很少,可以构造矩阵然后快速幂,得到一个置换使着色不变的着色方案数。

现在颜色种数很多,但是颜色限制较简单,可以考虑公式之类的。

考虑将n个圆的环,等分成t部分,每部分有m个圆。F表示m个圆满足限制的着色方案数。

若m=1,则F=0

若m=2,则F=k*(k-1)

若m=3,则F=k*(k-1)*(k-2)

若m=4,则F=k*(k-1)*[(k-1)+(k-2)*(k-2)]

……

观察到F[n]=F[n-1]*(k-2)+F[n-2]*(k-1)。

那么就可以对该递推式构造矩阵快速幂得到每种分法的方案数。

剩下的同【POJ】2888 Magic Bracelet

#define DeBUG
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <sstream>
#include <map>
#include <list>
#include <bitset>
using namespace std ;
#define zero {0}
#define INF 0x3f3f3f3f
#define EPS 1e-6
#define TRUE true
#define FALSE false
typedef long long LL;
const double PI = acos(-1.0);
//#pragma comment(linker, "/STACK:102400000,102400000")
inline int sgn(double x)
{
    return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1);
}
#define N 100005
#define mod 1000000007
const int MAXN = 2;
struct Matrix
{
    long long mat[MAXN][MAXN];
    void Zero()
    {
        memset(mat, 0, sizeof(mat));
    }
    void Unit()
    {
        memset(mat, 0, sizeof(mat));
        for (int i = 0; i < MAXN; i++)
            mat[i][i] = 1;
    }
    void Build(long long k)
    {
        Zero();
        mat[0][1] = 1;
        mat[0][0] = k - 2;
        mat[1][0] = k - 1;
    }
    void output()
    {
        for(int i=0;i<MAXN;i++)
        {
            for(int j=0;j<MAXN;j++)
            {
                printf("%d ", mat[i][j]);
            }
            printf("\n");
        }
    }
};

Matrix operator*(Matrix &a, Matrix &b)
{
    Matrix tmp;
    tmp.Zero();
    for (int k = 0; k < MAXN; k++)
    {
        for (int i = 0; i < MAXN; i++)
        {
            if (!a.mat[i][k])
                continue;
            for (int j = 0; j < MAXN; j++)
            {
                tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j]%mod;
                if( tmp.mat[i][j]>=mod)
                    tmp.mat[i][j]-=mod;
            }

        }
    }
    return tmp;
}
Matrix operator ^(Matrix a, int k)
{
    Matrix tmp;
    tmp.Unit();
    for (; k; k >>= 1)
    {
        if (k & 1)
            tmp = tmp * a;
        a = a * a;
    }
    return tmp;
}
std::vector<int> prime;
const int  MAXPR = 320000;
bool vispr[MAXPR];
void Init()
{
    prime.clear();
    memset(vispr, 1, sizeof(vispr));
    int sqrtnum = (int)(sqrt((double)MAXPR) + EPS);
    for (int i = 2; i < sqrtnum; i++)
    {
        if (vispr[i])
            for (int j = i * i; j < MAXN; j += i)
                vispr[j] = false;
    }
    for (int i = 2; i < MAXPR; i++)
    {
        if (vispr[i])
            prime.push_back(i);
    }
}
LL Ext_gcd(LL a, LL b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    LL ret = Ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
LL Inv(LL a, LL m)   ///求逆元a相对于m
{
    LL d, x, y, t = m;
    d = Ext_gcd(a, t, x, y);
    if (d == 1) return (x % t + t) % t;
    return -1;
}
//复杂度根号x
std::vector<int> factor;
void Factor(int n)
{
    factor.clear();
    int i;
    for (i = 1; i * i < n; i++)
    {
        if (n % i == 0)
        {
            factor.push_back(i);
            factor.push_back(n / i);
        }
    }
    if (i * i == n)
        factor.push_back(i);
}
long long F(int n, int k)
{
    long long res;
    if (n == 1)
        res = 0;
    else if (n == 2)
        res = (long long)k * (k - 1);
    else if (n == 3)
        res = (long long)k * (k - 1) % mod * (k - 2);
    else
    {
        Matrix g;
        g.Build(k);
        g = g ^ (n - 3);
        // g.output();
        res = g.mat[0][0] * k % mod * (k - 1) % mod * (k - 2);
        res += g.mat[1][0] * k % mod * (k - 1);
    }
    return (res) % mod;
}
int eular(int n)
{
    int i, res = 1;
    for (i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            n /= i; res *= i - 1;
            while (n % i == 0)
            {
                n /= i; res *= i;
            }
        }
    }
    if (n > 1)   res *= n - 1;
    return res;
}
int eularbyPR(int x)
{
    int res, i;
    res = x;
    for (i = 0; prime[i] * prime[i] <= x; i++)
    {
        if (x % prime[i] == 0)
        {
            res -= res / prime[i];
            while (x % prime[i] == 0)
                x /= prime[i];
        }
    }
    if (x > 1)
        res -= res / x;
    return res;
}
long long Burnside(int n, int k)
{
    long long ans=0;
    int i;
    Factor(n);
    for (i = 0; i < factor.size(); i++)
    {
        ans += F(factor[i], k) * eular(n / factor[i]) % mod;
         if (ans >= mod)
            ans -= mod;
    }
    return (ans * Inv(n, mod) + mod) % mod;
}
int main()
{
#ifdef DeBUGs
    freopen("C:\\Users\\Sky\\Desktop\.in", "r", stdin);
#endif
    int n, k;
    Init();
    while (scanf("%d%d", &n, &k) + 1)
    {
        printf("%I64d\n", (Burnside(n, k - 1)*k + mod) % mod);
    }

    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/163385.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • oracle 内置函数

    oracle 内置函数

  • mysql 删除一条数据sql语句_sql删除语句[通俗易懂]

    mysql 删除一条数据sql语句_sql删除语句[通俗易懂]sql删除语句一般简单的删除数据记录用delete就行了,但是如何要删除复杂的外键就不是一条delete删除来实例的,我们本文章先讲一下delete删除,然后再告诉你利用触发器删除多条记录多个表。删除数据库中的数据sql删除语句一般简单的删除数据记录用delete就行了,但是如何要删除复杂的外键就不是一条delete删除来实例的,我们本文章先讲一下delete删除,然后再告诉你利用触发器删除多…

  • 2018最新APP Android UI设计规范「建议收藏」

    2018最新APP Android UI设计规范「建议收藏」设计稿尺寸:从目前市场主流设备尺寸来看,我们要用1080x1920PX来做安卓设计稿尺寸。以1080x1920px作为设计稿标准尺寸的原由:从中间尺寸向上和向下适配的时候界面调整的幅度最小,最方便适配。大屏幕时代依然以小尺寸作为设计尺寸,会限制设计师的设计视角。用主流尺寸来做设计稿尺寸,极大的提高了视觉还原和其他机型适配。所以做安卓设计稿时请以1…

  • 设计模式之抽象工厂模式代码示例

    设计模式之抽象工厂模式代码示例

  • rtmp协议详解_rtmp服务器

    rtmp协议详解_rtmp服务器前言最近在学习rtmp协议,在看官方文档的时候总是懵懵懂懂,硬生生看了两天,现在基本上了解rtmp协议了,想用自己觉得比较清晰的方式来讲解rtmp协议,希望能够对向我一样的初学者有所帮助。本文将通过以下四部分讲解rtmp协议。1、消息2、块3、rtmp的消息类型4、实例分析rtmp传输过程一、消息消息是rtmp的基本数据单元,服务端和客户端通过在网络上发送RTMP消息进行通讯。…

    2022年10月22日
  • freemarker 教程_freemarker自定义标签

    freemarker 教程_freemarker自定义标签FreeMarker是一个用Java语言编写的模板引擎,它基于模板来生成文本输出。FreeMarker与Web容器无关,即在Web运行时,它并不知道Servlet或HTTP。它不仅可以用作表现层的实现技术,而且还可以用于生成XML,JSP或Java等。页面的静态化有的较多中的注释都是以#号表示的第一个项目结构代码的实现[java…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号