菜单

ACM暑期培训-HDU-3923

八月 1, 2018 - 算法
ACM暑期培训-HDU-3923

前言

模板型的题目,需要记录下来。

题目描述

Invoker

On of Vance’s favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.
In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

Input
The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )
Output
For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.
Sample Input
2
3 4
1 2
Sample Output
Case #1: 21
Case #2: 1

题目大意

我BB酱作为一名资深DOTA玩家,Kale这个英雄对我来说一直都是在黑名单榜首,复杂的技能操作令我头秃(就好像acm一样),这个题的背景就是建立在卡尔搓技能的基础上的,不过呢加入了一个特点——组合没有头尾,也就是说aaab和baaa和abaa和aaba都是一样的,在网上很多教程我觉得写得不错,有一种说法是把它看成一个项链,于是题目变成了这样:

有条n长度的项链,m种不同的颜色,问可以组成多少种不同的项链(翻转与旋转后相同的都算是同一条项链)

解题思路

这道题用到了Polya原理和费马小定理,还有快速幂的知识,对我来说还有些复杂,但是这里还是要把这个题记录一下,因为之前见到过很多这样的题,这次也算是整合一个模板吧。

解题代码

总结

还有很多东西需要学,polya原理需要好好看看,希望能有时间吧。

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注