未分类

AHOI 2002 黑白瓷砖

题目

小可可在课余的时候受美术老师的委派从事一项漆绘瓷砖的任务。首先把 $frac {n×(n+1)}{2}$ 块正六边形瓷砖拼成三角形的形状。然后把每一块瓷砖漆成纯白色或者纯黑色,而且每块瓷砖的正、反两面都必须漆成同样的颜色。
有一天小可可突发奇想,觉得有必要试试看这些瓷砖究竟能够漆成多少种本质不同的图案。所谓两种图案本质不同就是其中的一种图案无论如何旋转、或者翻转、或者同时旋转和翻转都不能得到另外一种图案。

  • 旋转是将瓷砖三角形整体顺时针旋转 120 度或 240 度

  • 翻转是将瓷砖三角形整体左右翻动 180 度

一开始,小可可觉得这项实验很有意思,他知道 n=1 时有两个本质不同的漆绘方案,n=2 时也只有四个本质不同的漆绘方案。小可可还把这些漆绘方案画了出来。
但是后来小可可发现在 n 变大的过程中,漆绘方案的数目增长很快,在 n=14 的时候,居然有 6760803201217259503457555972096 种不同的漆绘方案。这果然是一项非常艰巨的实验。因此他决定请你编写程序帮他求解本质不同的漆绘方案数。

输入格式
输入一个正整数 $n(n≤20)$。

输出格式
输出一个整数,即问题的解(解的位数不超过 200 位)。

         一道Polya定理的裸题。
         首先题目中虽然只给了三种方式进行置换,但因为这三个置换并不能形成一个置换群(不满足封闭性、没有不动元素),所以需要将斜向上翻转、斜向下翻转、不置换。都添加进置换群中。(它们都可以由题目中所给的置换方式得来)
         然后就十分的愉悦了。由Polya定理可得: $ans=frac{sum^n_{i=1}(2^{c(a_i)}}{n}$。$a_i$ 代表每一个置换,$c(a_i)$ 代表在每一个$a_i$ 下所存在环的个数(下图中$c(a_i)$ 的个数为 4 {(1),(2,3),(4,6),(5)}。

         对应三种翻转的 $c(a_i)$ 为 $frac{frac{n×(n+1)}{2}+frac{n+1}{2}}{2}$
         对应两种旋转的 $c(a_i)$ 为 $2^{(frac{n×(n+1)}{2}+2)/3+1}$
         对应不动的 $c(a_i)$ 肯定为 $2^{frac{n×(n+1)}{2}}$
         将其相加再除以6即为答案。
         这道题答案很大,要使用高精。因为很懒,所以没有去写高精。用python打了打表就A掉了。好像网上的OJ上也没有这道题(我们学校的OJ上倒是有,但没有对外开放)。

         代码(没有高精)

#include<bits/stdc++.h>
#include<bits/stdc++.h>
int main() {
    int n;
    scanf("%d",&n);
    int s = n * (n + 1) / 2;
    int m = (s + (n + 1) / 2) / 2;
    printf("%dn", (2<em>(1<<((s+2)/3)) + 3</em>(1<<m) + (1<<s)) / 6);
}

Python

n=input();
s=(n<em>(n+1))/2;
m = (s + (n + 1) / 2) / 2;
ans=0;
ans=ans+2</em>((1<<(s+2)/3));
ans=ans + 3*(1<<m) + (1<<s);
ans=ans/6;
print ans;

        给一张表吧
$$
begin{array}{c|lcr}
n & text{Ans}
hline
1 & 2
2 & 4
3 & 20
4 & 208
5 & 5728
6 & 351616
7 & 44772352
8 & 11453771776
9 & 5864078802944
10 & 6004800040206336
11 & 12297829416834170880
12 & 50371909152808594571264
13 & 412646679762074900658913280
14 & 6760803201217259503457555972096
15 & 221537999297485988040673580072042496
16 & 14518714321960041110131833181979847688192
17 & 1902996923607946508078923551753025410956263424
18 & 498859225542281529413525041870510961437758449516544
19 & 261545905641111698493157893267478067457861758958922891264
20 & 274250759553534340359161530426874121271106557923036528403021824
end{array}
$$
        AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n<8) {
        int s = n * (n + 1) / 2;
        int m = (s + (n + 1) / 2) / 2;
        printf("%dn", (2(1<<((s+2)/3)) + 3(1<<m) + (1<<s)) / 6);
    }
    if(n==8) cout<<"11453771776";
    if(n==9) cout<<"5864078802944";
    if(n==10) cout<<"6004800040206336";
    if(n==11) cout<<"12297829416834170880";
    if(n==12) cout<<"50371909152808594571264";
    if(n==13) cout<<"412646679762074900658913280";
    if(n==14) cout<<"6760803201217259503457555972096";
    if(n==15) cout<<"221537999297485988040673580072042496";
    if(n==16) cout<<"14518714321960041110131833181979847688192";
    if(n==17) cout<<"1902996923607946508078923551753025410956263424";
    if(n==18) cout<<"498859225542281529413525041870510961437758449516544";
    if(n==19) cout<<"261545905641111698493157893267478067457861758958922891264";
    if(n==20) cout<<"274250759553534340359161530426874121271106557923036528403021824";
}

Be the First to comment.

Leave a Comment

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