首页 > poj2154-color-polyan次二面体+欧拉函数优化

poj2154-color-polyan次二面体+欧拉函数优化

N<=1e9,O(nlogn)的做法会超时。从枚举置换转变为枚举轮换长度，然后可以利用欧拉函数，把复杂度变为O(√n * logn)

 1 /*--------------------------------------------------------------------------------------*/
 2 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include <string>
11 #include 
12 #include 
13 #include 
14 #include <set>
15 #include 
16 
17 //debug function for a N*M array
18 #define debug_map(N,M,G) printf("
");for(int i=0;i<(N);i++)
19 { for(int j=0;j<(M);j++){
20 printf("%d",G[i][j]);}printf("
");}
21 //debug function for int,float,double,etc.
22 #define debug_var(X) cout<<#X"="<23 #define LL long long
24 const int INF = 0x3f3f3f3f;
25 const LL LLINF = 0x3f3f3f3f3f3f3f3f;
26 /*--------------------------------------------------------------------------------------*/
27 using namespace std;
28 
29 int N,M,T;
30 int MOD = 1e9+7;
31 
32 int Eular(int n)
33 {
34     int ans = n;
35     for(int i=2;i*i<=n;i++)
36     {
37         if(n%i == 0)
38         {
39             ans -= ans/i;
40             while(n%i == 0) n/= i;
41         }
42     }
43     if(n>1) ans -= ans/n;
44     return ans;
45 }
46 int pow_mod(int x,int cnt)
47 {
48     int base = x%MOD,res = 1;
49     while(cnt)
50     {
51         if(cnt&1) {res *= base;res %= MOD;}
52         base *= base;base %= MOD;
53         cnt >>= 1;
54     }
55     return res;
56 }
57 
58 int polya(int n,int m)
59 {
60     int res = 0;
61     int i;
62     for(i=1;i*i)
63     {
64         if(n%i == 0)
65         {
66             res += Eular(i)%MOD * pow_mod(m,n/i-1)%MOD;res %= MOD;
67             res += Eular(n/i)%MOD * pow_mod(m,i-1)%MOD;res %= MOD;
68         }
69     }
70     if(i*i == n) res += Eular(i)%MOD*pow_mod(m,i-1)%MOD;
71     return res%MOD;
72 }
73 
74 int main()
75 {
76     scanf("%d",&T);
77     while(T--)
78     {
79         scanf("%d%d",&N,&MOD);
80         printf("%d
",polya(N,N));
81     }
82 }

 

转载于:https://www.cnblogs.com/helica/p/5823656.html

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

  • LeetCode 7. Reverse Integer

    问题链接 LeetCode 7 题目解析 给定一个32位有符号整数，求其反转数字。 解题思路 如果是简单反转的话，那这道题就太简单了。题目要求判断溢出问题，32位int类型的范围是-2147483648～2147483647。数字反转过后是有可能超出范围的，此时应该返回0。 最简单的想法是，反转结果用long long表示，其范围远超...

  • 小程序地图的使用笔记

    这两天在看小程序的地图，写写笔记记录一下 小程序官方文档提供的方法 https://mp.weixin.qq.com/debug/wxadoc/dev/api/location.html 腾讯地图提供的jssdk http://lbs.qq.com/qqmap_wx_jssdk/qqmapwx.html 根据提示使用腾讯地图jssdk...

  • OpenJudge 2739 计算对数

    1.链接地址： http://bailian.openjudge.cn/practice/2739/ 2.题目： 总时间限制:1000ms内存限制:65536kB描述给定两个正整数a和b。可以知道一定存在整数x，使得x <= logab < x + 1输出x输入第1行是测试数据的组数n，每组测试数据占2行，分别是a和b。每组测试数据之...

©2024 11GX.COM