UVA10294项链和手镯(等价类计数问题)
等价 项链
2023-09-11 14:14:00 时间
题意:
给你一串珠子(连接成了一个环),共有n个珠子组成,你有t种颜色,现在你来给这个珠子染色,问染成项链有多少种方法?染成手镯有多少种方法?在项链里,经过顺时针旋转后相同的算一个,在手镯里,经过顺时针旋转或者沿着对称轴兑换后一样的算一个。
思路:
比较典型的等价类计数问题,我们定义两个变量,a是旋转的总个数,b是翻转的总个数,那么根据Burnside和Polya定理,a = C[0] + C[1] + C[2] +..+C[n-1];
C[i]表示的是顺时针移动i个后的种类数,C[i] = t^w,t是颜色种类,w是循环节个数,在这个题目里,旋转是的循环节个数为gcd(i ,n);至于为什么可以自己想,想不通的话可以想想杭电上那个切蛋糕的题目,那么C[i] = t^gcd(i ,n)这样就能求出各个C[i]然后求出a,此时的相连的答案已经出来了,就是a/n,那么b呢?b可以分情况讨论,如果n是奇数那么对角线一共有n条,每次可以分出来(n+1)个循环节,那么b = n * t ^ ((n + 1)/2)如果n是偶数的话有两种情况,不穿过任何点的为 n/2*t(n/2) 穿过两个点的对角线为n/2*(n/2+1)那么此时的b=n/2*(t^(n/2) + t^(n/2+1)),那么手镯的种类为(a+b)/(n*2).
这里在解释下上面的那两个定理,那两个定理是求等价类计数问题的常用定理,大体意思就是说种类数等于所有可能置换方法的方法数的平均数,而每一个置换方法的个数等于颜色个数的循环节次幂,循环节就是置换里面的那个循环节。
#include<stdio.h>
long long gcd(long long a ,long long b)
{
return a % b == 0 ? b : gcd(b ,a % b);
}
int main ()
{
long long pow[60];
long long n ,t ,i;
long long a ,b;
while(~scanf("%lld %lld" ,&n ,&t))
{
pow[0] = 1;
for(i = 1 ;i <= n ;i ++)
pow[i] = pow[i-1] * t;
a = 0;
for(i = 0 ;i < n ;i ++)
a += pow[gcd(i ,n)];
if(n & 1) b = n * pow[(n+1)/2];
else b = n / 2 * pow[n/2] + n / 2 * pow[n/2 + 1];
printf("%lld %lld\n" ,a / n ,(a + b) / n / 2);
}
return 0;
}
给你一串珠子(连接成了一个环),共有n个珠子组成,你有t种颜色,现在你来给这个珠子染色,问染成项链有多少种方法?染成手镯有多少种方法?在项链里,经过顺时针旋转后相同的算一个,在手镯里,经过顺时针旋转或者沿着对称轴兑换后一样的算一个。
思路:
比较典型的等价类计数问题,我们定义两个变量,a是旋转的总个数,b是翻转的总个数,那么根据Burnside和Polya定理,a = C[0] + C[1] + C[2] +..+C[n-1];
C[i]表示的是顺时针移动i个后的种类数,C[i] = t^w,t是颜色种类,w是循环节个数,在这个题目里,旋转是的循环节个数为gcd(i ,n);至于为什么可以自己想,想不通的话可以想想杭电上那个切蛋糕的题目,那么C[i] = t^gcd(i ,n)这样就能求出各个C[i]然后求出a,此时的相连的答案已经出来了,就是a/n,那么b呢?b可以分情况讨论,如果n是奇数那么对角线一共有n条,每次可以分出来(n+1)个循环节,那么b = n * t ^ ((n + 1)/2)如果n是偶数的话有两种情况,不穿过任何点的为 n/2*t(n/2) 穿过两个点的对角线为n/2*(n/2+1)那么此时的b=n/2*(t^(n/2) + t^(n/2+1)),那么手镯的种类为(a+b)/(n*2).
这里在解释下上面的那两个定理,那两个定理是求等价类计数问题的常用定理,大体意思就是说种类数等于所有可能置换方法的方法数的平均数,而每一个置换方法的个数等于颜色个数的循环节次幂,循环节就是置换里面的那个循环节。
#include<stdio.h>
long long gcd(long long a ,long long b)
{
return a % b == 0 ? b : gcd(b ,a % b);
}
int main ()
{
long long pow[60];
long long n ,t ,i;
long long a ,b;
while(~scanf("%lld %lld" ,&n ,&t))
{
pow[0] = 1;
for(i = 1 ;i <= n ;i ++)
pow[i] = pow[i-1] * t;
a = 0;
for(i = 0 ;i < n ;i ++)
a += pow[gcd(i ,n)];
if(n & 1) b = n * pow[(n+1)/2];
else b = n / 2 * pow[n/2] + n / 2 * pow[n/2 + 1];
printf("%lld %lld\n" ,a / n ,(a + b) / n / 2);
}
return 0;
}
相关文章
- 关于ECMP 等价路由
- 教程-Tbutton(sender) 与 (sender as Tbutton) 等价吗?
- 【shell 】 test, /usr/bin/test, [ ], 和/usr/bin/[都是等价命令
- 第三条、多用字面量语法,少用与之等价的方法
- Lintcode---等价二叉树
- golang reflect.DeepEqual深等价比较引用数据类型是否相等
- golang reflect.DeepEqual深等价比较引用数据类型是否相等
- 【b504】等价表达式(NOIP2005第4题)
- 等价多米诺骨牌对的数量-c语言实现
- 练习 3-3 编写函数expand(s1, s2),将字符串s1中类似于a-z一类的速记符号在字符串s2中扩展为等价的完整列表abc···xyz。
- 练习 2-2 在不使用运算符&&或||的条件下编写一个与上面的for 循环语句等价的循环语句。
- 练习2-3 编写函数 htoi(s),把由十六进制数字组成的字符串(包含可选的前缀0x 或0X)转换为与之等价的整型值。字符串中允许包含的数字包括:0~9、a~f以及A~F。
- Leetcode 1128. 等价多米诺骨牌对的数量(终于解决)
- Leetcode 1128. 等价多米诺骨牌对的数量(终于解决)
- Leetcode 1128. 等价多米诺骨牌对的数量(终于解决)
- 【Groovy】集合遍历 ( 调用集合的 every 方法判定集合中的所有元素是否符合闭包规则 | =~ 运算符等价于 contains 函数 | 代码示例 )
- TPT 18功能扩展与更新:IBM ALM,等价类,ADAS测试,代码调试
- 【软件测试基础 】等价类分析法
- 等价与类似关系
- 软件测试用例设计 (一)等价类划分法
- 【快乐离散数学】命题逻辑 | 复合命题 | 等价命题 | Propositional Logic | Propositional Equivalences