【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\\1.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)


相关推荐

  • CTF-UPX脱壳加壳讲解;(详细版)

    CTF-UPX脱壳加壳讲解;(详细版)在做CTF-RE题的时候,下载的题目附件会发现缺少函数方法的现象,说明这个文件就被加壳处理了;这个是加壳状态下的;脱壳后~~~~~~~如何发现是加壳的呢?除了开头所描述的方法,还有第二种用ExeinfoPE软件查看附件信息;此时这个软件就提示我们这个附件是UPX加壳处理的;二.脱壳这里我只讲一种方法(因为我只会一种方法-.-)首先下载好打包好的UPX脱壳工具,解压下载好:讲一下用法吧在这个文件夹当中输入cmd进入;输入upx.exe-h有如下反应:

  • 什么是Java多态?如何实现Java多态?[通俗易懂]

    什么是Java多态?如何实现Java多态?[通俗易懂]java多态这个概念在同学们深入学习java的时候就会被提出,很多同学并不知道是什么意思,如何实现。今天小千就来给大家介绍一下什么是java多态和java如何实现多态。什么是多态?指允许不同类的对象对同一消息做出响应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式。(发送消息就是函数调用)实现多态的技术称为:动态绑定(dynamicbinding),是指在执行期间判断所引用对象的实际类型,根据其实际的类型调用其相应的方法。多态的作用:消除类型之间的耦合关系。现实中,关于多态的例子不胜

  • Docker方式安装showdoc

    Docker方式安装showdoc

  • algo_FISTA(fast shrinkage-thresholding algorithm)

    algo_FISTA(fast shrinkage-thresholding algorithm)前言:FISTA(Afastiterativeshrinkage-thresholdingalgorithm)是一种快速的迭代阈值收缩算法(ISTA)。FISTA和ISTA都是基于梯度下降的思想,在迭代过程中进行了更为聪明(smarter)的选择,从而达到更快的迭代速度。理论证明:FISTA和ISTA的迭代收敛速度分别为O(1/k2)和O(1/k)。  本篇博文先从解决优化问题的传统方法

  • 十大经典排序算法-快速排序算法详解

    十大经典排序算法-快速排序算法详解一、什么是快速排序1.概念快速排序(QuickSort)是从冒泡排序算法演变而来的,实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分2.算法原理这是一个无序数列:4、5、8、1、7、2、6、3,我们要将它按从小到大排序。按照快速排序的思想,我们先选择一个基准元素,进行排序我们选取4为我们的基准元素,并设置基准元素的位置为index,设置两个指针left和right,分别指向最左

  • yarn一些最佳配置

    yarn一些最佳配置

    2021年11月27日

发表回复

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

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