手链强化[FJWC2020Day2]

发表于 分类于 ，

题意

给定一个长度为 $n$ 的手链，对于每一个珠子，可以不染色，也可
以染 $k$ 种颜色中的一种。不能有相邻的两个珠子同时被染色。问
不同的染色手链种类数。旋转相同视作一种。对 $10^9+7$ 取模。

$n,k\leq 10^9$

题解

首先由 Burnside引理，得到答案为 $\frac{1}{n}\sum_{i=1}^n=f(\gcd(i,n))$，其中 $f(i)$ 表示长度为 $i$ 的环，不考虑旋转时的答案。

显然答案也等于 $\frac{1}{n}\sum_{d|n}\varphi(\frac{n}{d})f(d)$。

那么现在只需要考虑如何求 $f(i)$ 就好了。

设 $g_{i,0/1}$ 表示依次考虑环上每一个点，考虑到环上第 $i$ 个，该点染不染色的方案数。

显然有：$g_{i,0}=g_{i-1,0}+g_{i-1,1},g_{i,1}=kg_{i-1,0}$。

然后分两种情况讨论：

1，第一个点不染色，那么有 $g_{1,0}=1,g_{1,1}=0$，此时对答案贡献为 $g_{n,0}+g_{n,1}$。

2，第一个点染色，那么有 $g_{1,0}=0,g_{1,1}=k$，此时对答案贡献为 $g_{n,0}$。

那么就可以用矩阵快速幂求出这个 $f(i)$ 了。

求一个 $\varphi(i)$ 的复杂度可以通过预处理根号内的质数做到 $\frac{\sqrt i}{\log i}$。

那么时间复杂度为：

$$O(\sum_{d|n}\frac{\sqrt{d}}{\log d})\le O(\sum_{d|n}\frac{\sqrt{n}}{\log n})\le O(n^{\frac{1}{3}}\frac{\sqrt n}{\log n})=O(\frac{n^{\frac{5}{6}}}{\log n})$$

实际上跑得极快。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
struct mat{
	ll a[2][2];
	mat() {memset(a,0,sizeof(a));}
	inline ll* operator [] (const int &x)
	{
		return a[x];
	}
	friend inline mat operator * (mat A,mat B)
	{
		mat C;
		fo(i,0,1) fo(j,0,1) fo(k,0,1)
			C[i][j]=Add(C[i][j],A[i][k]*B[k][j]%mod);
		return C;
	}
};
inline mat Pow(mat A,int n)
{
	mat B; B[0][0]=B[1][1]=1;
	for(;n;n>>=1,A=A*A) if(n&1) B=B*A;
	return B;
}
mat F,G,H,A;
int n,k;
inline ll f(int n)
{
	ll sum=0;
	H[0][0]=1; H[0][1]=0;
	A=Pow(F,n-1);
	G=H*A;
	sum=Add(sum,Add(G[0][0],G[0][1]));
	H[0][0]=0; H[0][1]=k;
	G=H*A;
	sum=Add(sum,G[0][0]);
	return sum;
}
const int M=1e5+5;
int vis[M],pri[M],cnt;
inline void init(int n)
{
	fo(i,2,n)
	{
		if(!vis[i]) {pri[++cnt]=i;}
		for(int j=1;j<=cnt&&pri[j]*i<=n;j++)
		{
			vis[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}
inline int phi(int n)
{
	ll s=n;
	for(int i=1;i<=cnt&&pri[i]*pri[i]<=n;i++)
		if(n%pri[i]==0)
		{
			s=s*(pri[i]-1)/pri[i];
			for(;n%pri[i]==0;n/=pri[i]);
		}
	if(n!=1) s=s*(n-1)/n;
	return s;
}
ll calc(int n)
{
	ll ans=0;
	fo(i,1,sqrt(n))
		if(n%i==0)
		{
			ans=Add(ans,Mul(phi(n/i),f(i)));
			if(i*i!=n) ans=Add(ans,Mul(phi(i),f(n/i)));
		}
	return ans;
}

int main()
{
	FO(bracelet);
	cin>>n>>k;
	init(sqrt(n));
	F[0][0]=1; F[0][1]=k;
	F[1][0]=1; F[1][1]=0;
	printf("%lld",Mul(calc(n),Pow(n,mod-2)));
	return 0;
}