鹏鹏的旧OI博客

高二及以前的哦,只剩文字了,图片、附件等都没了



Let it Bead 和 Invoker

题目描述

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As you can deduce from the company name, their business is beads. Their PR department found out that customers are interested in buying colored bracelets. However, over 90 percent of the target audience insists that the bracelets be unique. (Just imagine what happened if two women showed up at the same party wearing identical bracelets!) It's a good thing that bracelets can have different lengths and need not be made of beads of one color. Help the boss estimating maximum profit by calculating how many different bracelets can be produced.
A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.

输入

Every line of the input file defines a test case and contains two integers: the number of available colors c followed by the length of the bracelets s. Input is terminated by c=s=0. Otherwise, both are positive, and, due to technical difficulties in the bracelet-fabrication-machine, cs<=32, i.e. their product does not exceed 32.

输出

For each test case output on a single line the number of unique bracelets. The figure below shows the 8 different bracelets that can be made with 2 colors and 5 beads.

样例输入

1 1
2 1
2 2
5 1
2 5
2 6
6 2
0 0

样例输出

1
2
3
5
8
13
21

来源

POJ2409


大概意思就是用c种颜色染s个点构成的环,旋转或翻转后重合的方案被认为是相同的,问不同的方案数。
可以直接套用Pólya定理。
先考虑旋转。用gcd求就可以了,最基本的。
翻转的话,要分奇偶讨论。
当珠子个数为奇数时,以n=5为例,
过一点珠子和对边的中点,一共是5{n}条对称轴,此时的置换群的循环节是(1)(25)(34){(1)(2 n-1)(3 n-2)...},所以这种情况对答案的贡献是5×c^3{n×c^((n+1)/2)}。
当珠子个数为偶数时,又要分情况讨论,以n=6为例,
1° 此时以相邻两个珠子之间的点连线作为对称轴
这样的话一共有n/2条对称轴,置换群的循环节为(16)(25)(34),共n/2个循环节,所以这种情况对答案的贡献是n/2×c^(n/2)。
2° 此时以相对的两个珠子连线作为对称轴
这样的话一共有n/2条对称轴,置换群的循环节为(1)(26)(35)(4),共n/2+1个循环节,所以这种情况对答案的贡献是n/2×c^(n/2+1)。
最后,把得到的结果除上循环节数2n就是答案了。

#include<cstdio>
#include<cmath>
using namespace std;
int m,n;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
    while(~scanf("%d%d",&m,&n)&&m&&n){
        int ans=0;
        for(int i=1;i<=n;++i)ans+=pow(m,gcd(n,i));
        if(n&1)ans+=n*pow(m,(n+1)/2);
        else ans+=n/2*(pow(m,n/2+1)+pow(m,n/2));
        printf("%d\n",ans/2/n);
    }
    return 0;
}

题目描述

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.

输入

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 )

输出

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.

样例输入

2
3 4
1 2

样例输出

Case #1: 21
Case #2: 1

来源

HDU3923


这题和POJ那题一个意思,就是数据范围大一点,要对答案取模。由于取模没有除法,所以就要多用一个逆元。本质是一样一样的。

#include<cstdio>
using namespace std;
const long long MOD=1000000007ll;
int n,m;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long pow(int a,int b){
    long long r=1ll,base=(long long)a;
    while(b){
        if(b&1)(r*=base)%=MOD;
        (base*=base)%=MOD;b>>=1;
    }
    return r;
}
int ex_gcd(int a,int b,int &x,int &y){
    if(!b){x=1;y=0;return a;}
    ex_gcd(b,a%b,y,x);
    y-=a/b*x;
}
int main(){
    int t;scanf("%d",&t);
    for(int i=1;i<=t;++i){
        scanf("%d%d",&n,&m);
        printf("Case #%d: ",i);
        long long ans=0;
        for(int i=1;i<=m;++i)(ans+=pow(n,gcd(m,i)))%=MOD;
        if(m&1)(ans+=m*pow(n,(m+1)/2))%=MOD;
        else (ans+=m/2*(pow(n,m/2+1)+pow(n,m/2)))%=MOD;
        int x,y;ex_gcd(2*m,MOD,x,y);
        while(x<0)x+=MOD;
        printf("%I64d\n",(ans*(long long)x)%MOD);
    }
    return 0;
}