台湾菜

继续置换群

twcai • acm/icpc

奉Teddy大牛暨队长之命,我这个离散白痴重新开始置换群专题。

先链接一下以前的关于这个专题的日志:置换群及Pólya定理

pku1721 CARDS : 这道题我用模拟置换群的平方运算,找出循环次数n,再顺推 n - s(mod n) 次这样的笨办法过的。最好的方法是用置换群的分数幂运算(这个还在学习中,看得相当头大),在效率上会有很大的差别,不过POJ数据偏弱了。
贴下代码:
#include
using namespace std;

int dor[1010];
int d[2][1010];

int main()
{
int n, s, i, j;
int f, nf, np, count;

while(scanf("%d %d", &n, &s) != EOF)
{
for(i = 1; i <= n; i++)
{
scanf("%d", &dor[i]);
d[0][i] = dor[i];
}
f = 0;
np = 0;
count = 0;
while(1)
{
nf = 1 - f;
np = 1;
for(i = 1; i <= n; i++)
if(d[f][i] != dor[i])
{
np = 0;
break;
}
if(np == 1 && count) break;
for(i = 1; i <= n; i++)
d[nf][i] = d[f][d[f][i]];
f = nf;
count++;
}

s = count - s % count;
f = 0;
for(i = 1; i <= n; i++)
d[0][i] = dor[i];

for(i = 0 ; i < s; i++)
{
nf = 1 - f;
for(j = 1; j <= n; j++)
d[nf][j] = d[f][d[f][j]];
f = nf;
}

for(i = 1; i <= n; i++)
printf("%dn", d[nf][i]);
}
return 0;
}

comments powered by Disqus