网站开发要学的代码,蓬莱做网站哪家好,wordpress大小,信宜网站开发公司正题
题目链接:https://www.luogu.com.cn/problem/P4980 题目大意 nnn个物品图上mmm种颜色#xff0c;求在可以旋转的情况下本质不同的涂色方案。 解题思路
既然是群论基本题就顺便写一下刚刚了解到的相关知识把#xff08;顺便消磨一下时间
一个群(G,)(G,\times )(G,)定义…正题
题目链接:https://www.luogu.com.cn/problem/P4980 题目大意
nnn个物品图上mmm种颜色求在可以旋转的情况下本质不同的涂色方案。 解题思路
既然是群论基本题就顺便写一下刚刚了解到的相关知识把顺便消磨一下时间
一个群(G,×)(G,\times )(G,×)定义为一个在运算×\times×下满足以下条件的集合
封闭性若存在a,b∈Ga,b\in Ga,b∈G那么有a×b∈Ga\times b\in Ga×b∈G交换律若有a,b,c∈Ga,b,c\in Ga,b,c∈G那么有(a×b)×ca×(b×c)(a\times b)\times ca\times (b\times c)(a×b)×ca×(b×c)单位元群中∃e∈G\exist e\in G∃e∈G满足∀x∈G\forall x\in G∀x∈G都有x×exx\times exx×ex逆元对于∀x∈G\forall x\in G∀x∈G都有一个唯一元素y∈Gy\in Gy∈G且x×yex\times yex×ye
然后中间一些东西很多很杂这里不多说了直接到置换部分。
一般来说规定置换第一行为(1,2,3...)(1,2,3...)(1,2,3...)那么定义一个置换σ(g1,g2,g3,...)\sigma(g_1,g_2,g_3,...)σ(g1,g2,g3,...)。如果一个置换作用与一个排列aaa一般写为σ(a)b\sigma(a)bσ(a)b的话就有biagib_ia_{g_i}biagi。需要注意的是对于一个置换两次后相当与使用了另一个置换。也就是置换只能生效一次
然后就是Burnside\text{Burnside}Burnside引理了对于一个置换群GGG若GGG作用与一个集合XXX时集合XXX中本质不同的元素个数为 1∣G∣∑f∈GC(f)\frac{1}{|G|}\sum_{f\in G}C(f)∣G∣1f∈G∑C(f) 其中C(f)C(f)C(f)表示XXX的所有元素中对于置换fff的不动点数量。
而Polya\text{Polya}Polya定理就是建立在Burnside\text{Burnside}Burnside引理上的对于一个置换fff定义它的循环节数量为T(f)T(f)T(f)用mmm种颜色染色时方本质不同的染色方案数就是 1∣G∣∑f∈GmT(f)\frac{1}{|G|}\sum_{f\in G}m^{T(f)}∣G∣1f∈G∑mT(f) 也就是mT(f)C(f)m^{T(f)}C(f)mT(f)C(f)这个很显然因为每个循环节涂成一种颜色就是一个不动点。
回到这题的旋转来我们可以将其视为nnn个不同的置换构成的一个置换群。对于旋转iii步它的循环节数量就是gcd(n,i)gcd(n,i)gcd(n,i)也就是我们要求 1n∑i0n−1mgcd(n,i)\frac{1}{n}\sum_{i0}^{n-1}m^{gcd(n,i)}n1i0∑n−1mgcd(n,i) 枚举一下gcd(n,i)gcd(n,i)gcd(n,i) 1n∑d∣nmd∑i1nd[gcd(nd,i)1]\frac{1}{n}\sum_{d|n}m^d\sum_{i1}^{\frac{n}{d}}[gcd(\frac{n}{d},i)1]n1d∣n∑mdi1∑dn[gcd(dn,i)1] 哦对啊好像有mnmnmn 1n∑d∣nndφ(nd)∑d∣nnd−1φ(nd)\frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d})\sum_{d|n}n^{d-1}\varphi(\frac{n}{d})n1d∣n∑ndφ(dn)d∣n∑nd−1φ(dn) 这个时间复杂度大概是O(Tn34)O(Tn^{\frac{3}{4}})O(Tn43)的但是因为约数个数远到不了n\sqrt nn所以你可以把它视为常数比较大的O(Tn)O(T\sqrt n)O(Tn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll P1e97;
ll T,n,ans;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll phi(ll x){ll ansx;for(ll i2;i*ix;i){if(x%i)continue;while(x%i0)x/i;ansans/i*(i-1);}if(x1)ansans/x*(x-1);return ans;
}
ll calc(ll x)
{return phi(x)*power(n,n/x-1)%P;}
signed main()
{scanf(%lld,T);while(T--){scanf(%lld,n);ans0;for(ll i1;i*in;i){if(n%i)continue;ans(anscalc(i))%P;if(i*i!n)ans(anscalc(n/i))%P;}printf(%lld\n,ans);}return 0;
}
