@hdu - 6427@ Problem B. Beads

@description@
@solution@
@accepted code@
@details@

@description@

有 m 种不同颜色的珠子，颜色分别为 1~m，每一种颜色的珠子有任意多个。你需要从中选出 n 个珠子构成一个项链。

如果经过任意次以下的操作后项链 A 变为了 B，我们就认为 A 与 B 等价。

（1）将项链旋转。

（2）将项链翻转。

（3）同时将项链上的每一颗珠子替换成它的下一种颜色，颜色 i 将被替换为 i mod m + 1。

求最后不同的项链的个数。

Input

第一行一个整数 T 表示数据组数。

对于每组数据包含两个整数 n, m，描述了项链长度以及颜色个数。

1 ≤ T ≤ 20, 3 ≤ n ≤ 10^18, 2 ≤ m ≤ 10^18, 998244353 不整除 n, m

Output

对于每组数据，输出答案模 998244353.

Sample Input

5

3 2

4 2

8 5

9 5

2333 333

Sample Output

2

4

5079

22017

544780894

Hint

对于 n = 3, m = 2:

[1, 1, 1], [2, 2, 2] 等价
[1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2] 等价

@solution@

较为典型的 burnside 引理计数问题。

首先我们将颜色全部减一，变为 0~m-1 之间的颜色。这样就可以直接取模。

题目中的操作可以分为两类：位移操作和颜色操作。

其中位移操作就是经典的旋转 + 翻转问题，构成置换群 G1，G1 包含 2*n 个置换。

而颜色操作构成的群 G2 中共含有 m 个置换，对应的操作分别为将颜色 i 变为 i, (i+1) mod m, (i+2) mod m, ...。

对于一个项链的置换可以由一个位移置换套上一个颜色置换组成，令这个置换群为 G3，则有 |G3| = |G1|*|G2| = 2*n*m。

考虑在一个位移置换与一个颜色置换嵌套的情况下不动点的个数。

类比 polya 定理，我们考虑位移置换形成的循环中染色的方案数，再将所有循环的方案数相乘。

假设一个循环为 (a1, a2, a3, ... ak)，如果要在颜色变化量为 d 的情况下相同，则要满足 a1 + d = a2, a2 + d = a3, ..., ak + d = a1（这里的“加法”被重新定义模意义下的加法）。

所以有 k*d = 0 mod m。因为 d 是一个 0~m-1 之间的数，所以 d 的取值共有 gcd(m, k) 种。

注意 d 的取值要对每个循环都要满足，对于旋转每个循环大小一样所以不重要，但是翻转可能同时存在大小为 1 和 2 的循环。

如果位移是翻转，可以直接分类讨论出来。

如果位移是旋转，需要枚举 n 的因子作为循环的大小，算出对应的欧拉函数计算贡献。

然后因为 n 很大，所以需要 pollard-rho 加速分解因数的过程。

@accepted code@

#include<map>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iostream>

using namespace std;

typedef long long ll;

const int MOD = 998244353;

const int PRM[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

map<ll, int>mp;

int pow_mod(int b, int p) {

	int ret = 1;

	while( p ) {

		if( p & 1 ) ret = 1LL*ret*b%MOD;

		b = 1LL*b*b%MOD;

		p >>= 1;

	}

	return ret;

}

ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a%b);}

ll mul_mod(ll a, ll b, ll mod) {

	a %= mod, b %= mod;

	ll ret = 0;

	while( b ) {

		if( b & 1 ) ret = (ret + a) % mod;

		a = (a + a) % mod;

		b >>= 1;

	}

	return ret;

}

ll pow_mod(ll b, ll p, ll mod) {

	ll ret = 1;

	while( p ) {

		if( p & 1 ) ret = mul_mod(ret, b, mod);

		b = mul_mod(b, b, mod);

		p >>= 1;

	}

	return ret;

}

bool Miller_Rabin(ll n, ll m, int a) {

	if( n == a ) return true;

	else if( n % a == 0 ) return false;

	ll x = pow_mod(a, m, n);

	if( x == 1 || x == n-1 )

		return true;

	while( m != n-1 ) {

		x = mul_mod(x, x, n), m *= 2;

		if( x == 1 ) return false;

		else if( x == n-1 ) return true;

	}

	return false;

}

bool IsPrime(ll n) {

	ll m = n-1;

	while( m % 2 == 0 ) m /= 2;

	for(int i=0;i<10;i++)

		if( !Miller_Rabin(n, m, PRM[i]) )

			return false;

	return true;

}

ll PollardRho(ll n) {

	if( n == 1 ) return n;

	if( n % 2 == 0 ) return 2;

	ll x = rand() % (n-2) + 2, y = x;

	ll c = rand() % (n-1) + 1, d = 1;

	while( d == 1 ) {

		x = (mul_mod(x, x, n) + c) % n;

		y = (mul_mod(y, y, n) + c) % n;

		y = (mul_mod(y, y, n) + c) % n;

		d = gcd(n, x > y ? x-y : y-x);

	}

	return d;

}

void GetDiv(ll x) {

	if( x == 1 ) return ;

	if( IsPrime(x) )

		mp[x]++;

	else {

		ll k = PollardRho(x);

		GetDiv(k), GetDiv(x/k);

	}

}

int ans; ll n, m;

vector<pair<ll, int> >d;

void dfs(int x, ll nw, ll phi) {

	if( x == d.size() ) {

		ans = (ans + 1LL*(gcd(m, nw)%MOD)*pow_mod((m%MOD), (n/nw)%(MOD-1))%MOD*(phi%MOD)%MOD)%MOD;

		return ;

	}

	dfs(x + 1, nw, phi);

	nw *= d[x].first, phi *= d[x].first - 1;

	dfs(x + 1, nw, phi);

	for(int i=2;i<=d[x].second;i++) {

		nw *= d[x].first, phi *= d[x].first;

		dfs(x + 1, nw, phi);

	}

}

void solve() {

	scanf("%lld%lld", &n, &m);

	mp.clear(), d.clear(), GetDiv(n);

	for(map<ll, int>::iterator it=mp.begin();it!=mp.end();it++)

		d.push_back(*it);

	ans = 0; dfs(0, 1, 1);

	if( n & 1 )

		ans = (ans + (n%MOD)*pow_mod((m%MOD), ((n+1)/2)%(MOD-1))%MOD)%MOD;

	else {

		ans = (ans + ((n/2)%MOD)*pow_mod((m%MOD), (n/2)%(MOD-1))%MOD*gcd(2, m)%MOD)%MOD;

		ans = (ans + ((n/2)%MOD)*pow_mod((m%MOD), (n/2+1)%(MOD-1))%MOD)%MOD;

	}

	printf("%lld\n", 1LL*ans*pow_mod((2*n%MOD)*(m%MOD)%MOD, MOD-2)%MOD);

}

int main() {

	srand(20041112);

	int T; scanf("%d", &T);

	for(int i=1;i<=T;i++) solve();

}

@details@

算是中档难度的经典题吧。写起来也没有什么特别需要注意的细节。

巴特西

@hdu - 6427@ Problem B. Beads

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章