2011-0047

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：
{{{
下围棋，第一颗黑棋只能放在k1×k1的范围内，第二颗白棋只能放在k2×k2的范围内，第三颗黑棋只能放在k3×k3的范围内，这里ki×ki均拥有相同的中心。
问在这样的规则下，前三手后会出现多少种本质不同的局面。所谓本质不同即通过旋转或对称不与原图重合
}}}

解法：
{{{
用[http://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside定理]解决。
cnt = sigma(c(Gi)) (c(Gi)为在置换Gi下1阶循环的个数，即保持元素不变的个数)

这道题目中的置换有8种：

* 旋转0度  : 这里共有k1*k1*(k2*k2-1)*(k3*k3-2)-(k1*k1*(k1*k1-1)*(k2*k2-2)/2种情况，之所以后面要减掉一部分是因为黑棋在题目里不加以区分所以当都放在k1×k1中时会有重复

* 旋转90度 : 不存在这种局面，个数为0

* 旋转180度: 白棋只能放在中心，又由于黑棋没有区分，所以共有(k1*k1-1)/2种情况

* 沿轴对称 : 分别可以关于x=0，y=0，x+y=0和x-y=0对称，四种情况都是一样的，每一种有k1*(k2-1)*(k3-2)-k1*(k1-1)*(k2-2)/2+k2*k1*(k1-1)/2种情况，第一项是放在对称轴上的
  情况，第二项是去掉第一种情况黑棋重复的部分，第三项是白棋在对称轴上，黑棋在两边的情况
}}}

代码:
{{{
#include <cstdio>
using namespace std;

int main() {
    long long k1, k2, k3, L;

    while (4 == scanf("%lld %lld %lld %lld", &L, &k1, &k2, &k3)) {
        printf("%lld\n", (k1*k1*(k2*k2-1)*(k3*k3-2)-(k1*k1*(k1*k1-1)*(k2*k2-2)>>1)+((k1*k1-1)>>1)+((k1*(k2-1)*(k3-2)-(k1*(k1-1)*(k2-2)>>1)+k2*k1*(k1>>1))<<2))>>3);
    }
    return 0;
}
}}}
[by delta_4d]

题目大意：

下围棋，第一颗黑棋只能放在k1×k1的范围内，第二颗白棋只能放在k2×k2的范围内，第三颗黑棋只能放在k3×k3的范围内，这里ki×ki均拥有相同的中心。
问在这样的规则下，前三手后会出现多少种本质不同的局面。所谓本质不同即通过旋转或对称不与原图重合

解法：

用[http://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside定理]解决。
cnt = sigma(c(Gi)) (c(Gi)为在置换Gi下1阶循环的个数，即保持元素不变的个数)
这道题目中的置换有8种：
* 旋转0度  : 这里共有k1*k1*(k2*k2-1)*(k3*k3-2)-(k1*k1*(k1*k1-1)*(k2*k2-2)/2种情况，之所以后面要减掉一部分是因为黑棋在题目里不加以区分所以当都放在k1×k1中时会有重复
* 旋转90度 : 不存在这种局面，个数为0
* 旋转180度: 白棋只能放在中心，又由于黑棋没有区分，所以共有(k1*k1-1)/2种情况
* 沿轴对称 : 分别可以关于x=0，y=0，x+y=0和x-y=0对称，四种情况都是一样的，每一种有k1*(k2-1)*(k3-2)-k1*(k1-1)*(k2-2)/2+k2*k1*(k1-1)/2种情况，第一项是放在对称轴上的
  情况，第二项是去掉第一种情况黑棋重复的部分，第三项是白棋在对称轴上，黑棋在两边的情况

代码:

#include <cstdio>
using namespace std;
int main() {
    long long k1, k2, k3, L;
    while (4 == scanf("%lld %lld %lld %lld", &L, &k1, &k2, &k3)) {
        printf("%lld\n", (k1*k1*(k2*k2-1)*(k3*k3-2)-(k1*k1*(k1*k1-1)*(k2*k2-2)>>1)+((k1*k1-1)>>1)+((k1*(k2-1)*(k3-2)-(k1*(k1-1)*(k2-2)>>1)+k2*k1*(k1>>1))<<2))>>3);
    }
    return 0;
}

[by delta_4d]