Chlience

【题解】SPOJ TRANSP - Transposing is Fun & TRANSP2 - Transposing is Even More Fun
Problem给定一个 $2^a​$ 行 $2^b​$ 列的矩阵,从上到下,从左到右用依次按照 $1...2^{a...
扫描右侧二维码阅读全文
14
2019/01

【题解】SPOJ TRANSP - Transposing is Fun & TRANSP2 - Transposing is Even More Fun

Problem

给定一个 $2^a​$ 行 $2^b​$ 列的矩阵,从上到下,从左到右用依次按照 $1...2^{a+b}​$ 标号
每次交换一对点,最少需要多少次才能将其变为原矩阵的转置矩阵

Thought

看到了一些瞎几把写的题解,然后...
其实我也是瞎几把写的

题目中要用 $[1,2^{a+b}]$ 编号,我非要用 $[0,2^{a+b}-1]$编号
求转置矩阵相当于将原矩阵按照 $i=j$ 这条线翻转

$$ \begin{bmatrix} 0&1\\ 2&3\\ 4&5\\ 6&7 \end{bmatrix} \Rightarrow \begin{bmatrix} 0&2&4&6\\ 1&3&5&7 \end{bmatrix} $$

这是一个经典的 $2^2*2^1$ 矩阵转置过程

考虑每个编号的位置转换关系:

$$ 0(000)\to0(000)\\ 1(001)\to4(100)\\ 2(010)\to1(001)\\ 3(011)\to5(101)\\ 4(100)\to2(010)\\ 5(101)\to6(110)\\ 6(110)\to3(011)\\ 7(111)\to7(111) $$

这不恰好相当于一个置换么?

$$ \begin{pmatrix} 0&1&2&3&4&5&6&7\\ 0&4&1&5&2&6&3&7 \end{pmatrix} = (0)(124)(356)(7) $$

对于置换中的某个长度为 $x$ 的循环,至少需要 $x-1$ 个两两交换才能完成,也就是说,每多一个循环节,总次数 $-1$

假设有 $k​$ 个循环节,那么所需要的最少次数为 $2^{a+b}-k​$

那么如何计算循环节个数呢?首先得看看置换的规则

每个节点转职后的新编号相当于原编号向左移动了 $2​$ 位,或者说向右移动了 $1​$ 位,为什么呢?

考虑一下行列的变化,每个节点的初始位置为 $(i,j)​$,编号为 $i*2^b+j​$
经过转置后,$(i,j)​$ 互换,位置为 $(j,i)​$,编号为 $j*2^a+i​$

两者转化关系为

$$ ((i*2^b+j)*(2^a))\%2^{a+b}+((i*2^b+j)*(2^a))/2^{a+b}\\ \Downarrow\\ j*2^a+i $$

相当于将编号向左移动了 $a$ 位,或者说向右移动了 $b$ 位,与前面得到的一致

也就是说需要计算 $2^{a+b}$ 个元素在向右移动 $b​$ 位的情况下循环节个数
直接去算个数肯定会炸

容易发现每个循环节内部是向右移动 $kb$ 位同构的,也就是说可以计算在置换群 $G=\{\text{移动b位,移动2b位,...}\}$ 情况下本质不同的元素个数

那么如果将其看做一个长度为 $a+b$ 的环,白色为 $0$,黑色为 $1$,确定一个锚点,顺时针将 $01$ 串写出来,就能表示出 $[0,2^{a+b}-1]$ 中的每个数字
其中在置换群 $G=\{\text{旋转b位,旋转2b位,...}\}$ 下本质不同的元素个数即为上文所求

既然每次旋转的是 $b​$ 位的倍数,那么每个循环节最大为 $\frac{a+b}{gcd(b,a+b)}​$,当且仅当旋转 $b​$ 位
显然可以看出,对于任意一个旋转 $kb​$ 位的循环节,循环节内部的元素必然是旋转 $b​$ 位时循环节内部元素的子集,必然不会出现原来不属于同一个循环节的元素变得属于同一个循环节的情况

同时,连续的 $gcd(b,a+b)​$ 个元素必然不属于同一个循环节,所以直接将其缩成一个点,有 $2^{gcd(b,a+b)}​$ 种不同颜色,求这 $\frac{a+b}{gcd(b,a+b)}​$ 个点的本质不同的元素个数,置换群 $G=\{\text{旋转1位,旋转2位,...}\}​$

那么就可以套路求解啦!

$$ L=\frac{1}{|G|}\sum_{i=1}^{s}m^{c(g_i)} $$

其中有:$|G|=s=\frac{a+b}{gcd(b,a+b)}=\frac{a+b}{gcd(a,b)}$,$m=2^{gcd(b,a+b)}$,$c(g_i)=gcd(i,\frac{a+b}{gcd(b,a+b)})=gcd(i,\frac{a+b}{gcd(a,b)})​$

令 $n=\frac{a+b}{gcd(a,b)}$,​$m=2^{gcd(a,b)}$

那么答案为:

$$ L=\frac{1}{n}\sum_{i=1}^{n}m^{gcd(i,n)}\\ L=\frac{1}{n}\sum_{d|n}\sum_{i=1}^{n}m^d[gcd(i,n)=n]\\ L=\frac{1}{n}\sum_{d|n}m^d\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]\\ L=\frac{1}{n}\sum_{d|n}m^d*\phi(\frac{n}{d}) $$

时间复杂度 $O(\sqrt{a+b}*\log (a+b))$

记得这只是算的可以减少的交换次数啊!
要用 $2^{a+b}$ 减去它才是最终答案
还有 $a=0,b=0​$ 要记得特判

Code

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000003;
int pri[mod] , pri_num , phi[mod];
bool np[mod];
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void getPri() {
    phi[1] = 1;
    for(int i = 2 ; i < mod ; ++ i) {
        if(!np[i]) {
            pri[++ pri_num] = i;
            phi[i] = i - 1;
        }
        for(int j = 1 ; j <= pri_num && i * pri[j] < mod ; ++ j) {
            np[i * pri[j]] = 1;
            if(i % pri[j])
                phi[i * pri[j]] = phi[i] * phi[pri[j]];
            else {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
        }
    }
}
int gcd(int a , int b) {
    if(a < b) swap(a , b);
    return b ? gcd(b , a % b) : a;
}
int qpow(int a , int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    getPri();
    int t = read();
    while(t --) {
        int a = read() , b = read();
        if(a == 0 && b == 0) {
            puts("0");
            continue;
        }
        int n = (a + b) / gcd(a , b);
        int inv_n = qpow(n , mod - 2);
        int m = qpow(2 , gcd(a , b));
        int ans = 0;
        for(int i = 1 ; i * i <= n ; ++ i)
            if(n % i == 0) {
                ans += 1ll * qpow(m , i) * phi[n / i] % mod;
                if(ans >= mod) ans -= mod;
                if(i * i != n) {
                    ans += 1ll * qpow(m , n / i) * phi[i] % mod;
                    if(ans >= mod) ans -= mod;
                }
            }
        ans = 1ll * ans * inv_n % mod;
        ans = (qpow(2 , a + b) - ans + mod) % mod;
        printf("%d\n" , ans);
    }
    return 0;
}
Last modification:January 14th, 2019 at 11:55 am

Leave a Comment