题解 P4607 【[SDOI2018]反回文串】

Soulist · 2020-04-29 22:06:23 · 题解

这道题很有意思，需要你进行大量的手玩来推结论

结论1：一个字符串 A 的不同的轮换的数量为 |\sigma(A)|，其中 \sigma(S) 表示 S 的最小循环节。

这个结论比较基础/fad

结论2：一个回文串的最小循环节 \sigma(S) 必然也是一个回文串。

证明的话可以手玩。

结论3：一个长度为 n 的字符串可以被一个最小循环节唯一表示，同时这个循环节也会唯一表示一个长度为 n 的字符串。

这个结论也非常显然。

不过我们可以开始转变思路了，我们尝试对 \sigma 进行计数，根据结论 1 一个 \sigma 可以衍生出来的本质不同的字符串的数量为 |\sigma|

所以我们猜想答案是：\sum |\sigma|

很快你就会意识到不对，我们发现比如字符串 abbaabba 他在一定的循环之后会变成 baabbaab 我们统计 \sigma 的时候会将 abba 与 baab 都一起算一遍。

我们接着又可以发现这几个结论：

结论4：如果一个合法的循环节 \sigma 的长度为偶数，那么至少存在另一个 \sigma 与之对应。

~~证明的话手玩~~，大概就是把 \sigma 分解为 s1+s2，那么 s1\ne s2,s1=rev(s2)，那么一定存在另一个循环节为 s2+s1 可以通过轮换得到一样的结果。

结论5：在结论 4 的基础上，每个长度为偶数的合法最小循环节 \sigma 都有且仅有一个 \zeta 与之对应，即 4 的证明下面补充的例子。

这个结论就需要手玩了，画一个图，然后假设一个位移 k 使得其回文，最后会推导出来 \sigma 是存在循环节的之类的，比较感性...不过直觉上这个结论挺对的。

结论6：类比结论 5，如果一个回文最小循环节 \sigma 为奇数，那么其不存在任意一个与之对应 \zeta 使之回文。

这个结论的手玩方式和 5 类似。

结论 7：约数个数函数的增长十分缓慢，对于 n\le 10^{18}，有 \max\{d(n)\}=103680

我们发现结论 6 十分的优美，他意味着如果一个回文循环节的长度为奇数，那么其对于答案的贡献就是 |\sigma|

而结论 5 则让我们意识到对于长度为偶数的回文循环节，其总是两两配对的，所以单独一者的贡献可以直接视为 \frac{|\sigma|}{2}

结论 7 则告诉我们，复杂度为 O(d(n))（d(x) 表示 x 的约数个数）的算法是可以通过这道题的。

现在我们可以开始计数了，令 f(d) 表示最小循环节长度为 d 的循环节数量，那么我们知道答案就是：

\sum_{d|n}f(d)\times \frac{d}{1+r(d)}

其中 r(d) 表示 "[d 为偶数]"，我们发现 f(d) 不好求，但是我们不妨设 F(x) 为长度为 x 的回文串的数量，那么有：

\sum_{d|x}f(d)=F(x)

~~可以直接当作用了一次结论2，虽然也比较显然~~

我们知道 F(x)=m^{\lceil\frac{x}{2}\rceil}，于是我们可以通过莫比乌斯反演得到 f

于是有：

f(d)=\sum_{x|d}F(x)\times \mu(\frac{d}{x})

于是我们知道：

Ans=\sum_{d|n} \dfrac{d}{1+r(d)}\sum_{x|d}\mu(\frac{d}{x})F(x)

令 g(d)=\frac{d}{1+r(d)}，则有：

Ans=\sum_{d|n}\sum_{x|d}\mu(\frac{d}{x})F(x)g(d)

Ans=\sum_{x|n}F(x)\sum_{k|\frac{n}{x}}\mu(k)g(kx)

到目前为止，如果我们能够做到 O(d(n)) 的枚举约数那么本题已经可以得到部分分了。

我们肯定希望有一种玄幻的操作可以将 g(kx) 分解出来，让后面变成之和 \frac{n}{x} 有关的一个函数。

假设将 k 从 g(kx) 中提取出来变成 kg(x)，那么此时 kg(x)\ne g(kx) 当且仅当 x 为奇数，k 为偶数。

由于 k|\frac{n}{x}，于是 \frac{n}{x} 为偶数，我们现在来考虑这个式子的取值：

\sum_{k|\frac{n}{x}}\mu(k)g(kx)

~~通过打表可以发现这个式子的值恒定为 0~~

我们理性分析一下，这个式子的前提为 \frac{n}{x} 为偶数，x 为奇数，所以对于答案有贡献的 \mu(k) 都满足 \mu(k)\ne 0，我们对于 \frac{n}{x} 进行质因数分解，现在只关注 \mu(k)\ne 0 的 k，我们发现每一个不含 2 作为因数的 k 都存在一个 \mu(2k) 与之对应，且其值恰好相反，而且 g(kx),g(2kx) 是相同的，所以这两个值会在一起抵消，所以这一部分对于答案的贡献为 0。

由于我们不关注 0 的取值，我们可以忽略这一类，对于剩下的情况，有答案为：

\sum_{x|n}F(x)g(x)\sum_{k|\frac{n}{x}}\mu(k)k

如果能够 O(1) 的求出后面的式子的值，那么我们就可以得到一个 O(d(n)) 的解法了，现在考虑：

\sum_{k|n}\mu(k)k

的取值，我们仍然只考虑 \mu(k)\ne 0 的数，那么此时我们可以将一个 k 视为 p_1p_2...p_m

考虑一个 dp 的思想来统计答案，每次新增一个质因数 p' 进入集合的时候，显然答案有两类，一类是不选入 p' 一类是选入 p'，选入 p ' 的同时会使得所有贡献都乘以 (-1)，令 f_i 表示之前的答案，则有 f_i'=(f_i-p'f_i)，我们把每一项的贡献单独提取出来，则可以得到上式为：

\sum_{k|n}\mu(k)k=\prod(1-p_i)

我们先通过 Pollard−Rho 将 n 进行质因数分解，然后通过质因数来进行搜索，做到 O(d(n)) 枚举所有约数，对于 x 为奇数而 \frac{n}{x} 为偶数的情况忽略，然后沿途统计一下 \prod(1-p_i) 即可。

值得注意的是被统计的 \prod (1-p_i) 是补集的。

复杂度 O(T\times (d(n)\log n+n^{1/4}\log n))

Code:

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int __int128
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 10000 + 5 ; 
int T, n, m, P, st[N], top, w[N], num, c[N] ; 
int mul( int a, int b, int p ) {
    return ( a % p ) * ( b % p ) % p ;  
}
int fpow( int x, int k, int p ) {
    int ans = 1, base = x % p ; 
    while( k ) {
        if( k & 1 ) ans = mul( ans, base, p ) ;
        base = mul( base, base, p ), k >>= 1 ; 
    } return ans % p ; 
}
bool M_R( int p ) {
    if( p == 2 || p == 3 ) return 1 ; 
    if( p == 1 || ( p % 2 == 0 ) ) return 0 ; 
    re int d = p - 1, s = 0 ; while( !( d & 1 ) ) ++ s, d >>= 1 ; 
    rep( i, 0, 5 ) {
        re int a = rand() % ( p - 3 ) + 2 ; 
        re int x = fpow( a, d, p ), y = 0 ;
        for( register int j = 0; j < s; ++ j ) {
            y = mul( x, x, p ) ; if( y == 1 && ( x != 1 ) && x != ( p - 1 ) ) return 0 ;
            x = y ;
        } if( y != 1 ) return 0 ;
    } return 1 ; 
}
int gcd( int x, int y ) {
    return ( x == 0 ) ? y : gcd( y % x, x ) ;
}
int Rand( int x ) {
    return 1ll * ((rand() << 15 ^ rand()) << 30 ^ (rand() << 15 ^ rand())) % x ; //2
}
int work( int p ) {
    re int k = 2, x = Rand(p - 1) + 1, y = x, d = 1, c = Rand(p) % 999997 ;
    for( re int i = 1; d == 1; ++ i ) {
        x = ( mul( x, x, p ) + c ) % p ;
        d = gcd( (x > y) ? x - y : y - x, p ) ;
        if( i == k ) y = x, k <<= 1 ; 
    } return d ; 
}
void Pollard_Rho(int p) {
    if( p == 1 ) return ; 
    if( M_R(p) ) { st[++ top] = p; return ; }
    int x = p ; while( x == p ) x = work(x) ;
    Pollard_Rho(x), Pollard_Rho(p / x) ;
}
int Ans = 0 ;
void dfs( int x, int f, int d, int p ) {
    if( x == num + 1 ) {
        if( ( (d & 1) ) && ( !( (n / d) & 1 ) ) ) return ;
        int g = ( d & 1 ) ? d : d / 2 ;
        Ans = ( Ans + mul( mul( fpow( m, ( d + 1 ) / 2, p ), g, p ), (f + p) % p, p ) + p ) % p ;
        return ; 
    }
    int fd = 1 ; 
    rep( i, 0, c[x] ) {
        if( i == c[x] ) dfs( x + 1, f, d * fd, p ) ;
        else dfs( x + 1, f * ( 1 - w[x] ), d * fd, p ) ;
        fd = fd * w[x] ; 
    }
}
signed main()
{
    srand(time(NULL)) ; 
    T = gi() ; 
    while( T-- ) {
        n = gi(), m = gi(), P = gi(), top = 0, num = 0, Ans = 0 ;
        memset( c, 0, sizeof(c) ), memset( w, 0, sizeof(w) ), memset( st, 0, sizeof(st) ) ;
        Pollard_Rho(n) ; 
        sort( st + 1, st + top + 1 ) ;
        rep( i, 1, top ) {
            if( st[i] == st[i - 1] ) ++ c[num] ; 
            else w[++ num] = st[i], c[num] = 1 ; 
        }
        dfs( 1, 1, 1, P ) ;
        printf("%lld\n", (long long)((Ans) % P) ) ;
    }
    return 0 ;
}