网站开发常用的谷歌插件,百度大全下载,网站设计报告,庆阳吧题意#xff1a;TTT 组数据#xff0c;每组给定 n,an,an,a#xff0c;求满足下列条件的项链数量#xff1a;
有 nnn 个珠子。每个珠子上有三个 [1,a]∩Z[1,a]\cap \Z[1,a]∩Z 的数#xff0c;且三个数 gcd\gcdgcd 为 111。相邻两个珠子不同。
珠子旋转、翻转同构…题意TTT 组数据每组给定 n,an,an,a求满足下列条件的项链数量
有 nnn 个珠子。每个珠子上有三个 [1,a]∩Z[1,a]\cap \Z[1,a]∩Z 的数且三个数 gcd\gcdgcd 为 111。相邻两个珠子不同。
珠子旋转、翻转同构项链旋转同构。对 109710^971097 取模。
n≤1014,a≤107n\leq 10^{14},a\leq 10^7n≤1014,a≤107
有毒……
显然是道缝合怪题先考虑求有多少个不同的珠子。
设 f(k)f(k)f(k) 表示 kkk 个 [1,a][1,a][1,a] 的数 gcd\gcdgcd 为 111 的方案数用 Polya 定理数一下可知
ansf(3)3f(2)2f(1)6ans\frac{f(3)3f(2)2f(1)}{6}ans6f(3)3f(2)2f(1)
然后就是个简单的反演
f(k)∑i1aμ(i)⌊ai⌋kf(k)\sum_{i1}^a\mu (i)\left\lfloor\frac ai\right\rfloor^kf(k)i1∑aμ(i)⌊ia⌋k
整除分块算就可以了其实直接暴力也可以。
然后第二步数项链。设第一步得到的珠子种数为 kkk众所周知F(n)F(n)F(n) 为 nnn 个珠子不循环同构的方案答案就是 FFF 和 φ\varphiφ 的狄利克雷卷积除以 nnn。
考虑 FFF 怎么算。
考虑一个 nnn 个珠子的合法方案我们删掉编号为 111 的点。如果两边的点不同就对应了一种 F(n−1)F(n-1)F(n−1) 的方案乘上 111 号珠子的方案 (k−2)(k-2)(k−2)。如果相同任意删掉一个后就对应一种 F(n−2)F(n-2)F(n−2) 的方案乘上 111 号珠子的方案 (k−1)(k-1)(k−1)。所以
F(n)(k−2)F(n−1)(k−1)F(n−2)F(n)(k-2)F(n-1)(k-1)F(n-2)F(n)(k−2)F(n−1)(k−1)F(n−2)
注意边界是 F(1)0,F(2)k(k−1)F(1)0,F(2)k(k-1)F(1)0,F(2)k(k−1),倒退出来 F(0)mF(0)mF(0)m。
列出生成函数
F(k−2)xF(k−1)x2Fk−k(k−2)xF(k-2)xF(k-1)x^2Fk-k(k-2)xF(k−2)xF(k−1)x2Fk−k(k−2)x
这里减 k(k−2)xk(k-2)xk(k−2)x 是为了平衡 (k−2)xF(k-2)xF(k−2)xF 对一次项的影响。
即
F−m(m−2)xm(1x)(1−(m−1)x)F\frac{-m(m-2)xm}{(1x)(1-(m-1)x)}F(1x)(1−(m−1)x)−m(m−2)xm
直接待定系数拆掉
Fa1xb1−(k−1)xF\frac{a}{1x}\frac{b}{1-(k-1)x}F1xa1−(k−1)xb
列出方程
a−a(k−1)xbbx−k(k−2)xka-a(k-1)xbbx-k(k-2)xka−a(k−1)xbbx−k(k−2)xk
解得 ak−1,b1ak-1,b1ak−1,b1
所以
Fk−11x11−(k−1)xF\frac{k-1}{1x}\frac{1}{1-(k-1)x}F1xk−11−(k−1)x1
F(n)(k−1)n(−1)n(k−1)F(n)(k-1)^n(-1)^n(k-1)F(n)(k−1)n(−1)n(k−1)
然后就可以算了。
这里有点卡就不用 Polya 模板那个垃圾做法而是把因子预处理出来 dfs可以做到 O(d(n))\Omicron(d(n))O(d(n)) 的优秀复杂度。
然后因为 nnn 很大最后除 nnn 的时候又会有喜闻乐见的除 000 问题。所以要对 (1097)2(10^97)^2(1097)2 取模最后再判一下。
总复杂度 O(nT(ad(n)log))\Omicron(nT(\sqrt ad(n)\log))O(nT(ad(n)log))
#include iostream
#include cstdio
#include cstring
#include cctype
#define int long long
using namespace std;
const int mod1e97,MODmod*mod;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
inline int mul(int a,int b){return (a*b-(int)((long double)a/MOD*b0.5)*MODMOD)%MOD;}
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ansmul(ans,a);amul(a,a),p1;}return ans;
}
int INV6833333345000000041ll;
int n,a;
const int N1e7,MAXNN5;
bool np[MAXN];
signed pl[MAXN],cnt,mu[MAXN];
void init()
{np[1]1,mu[1]1;for (int i2;iN;i){if (!np[i]) mu[pl[cnt]i]-1;for (int j1,x;(xi*pl[j])N;j){np[x]1;if (i%pl[j]0) break;mu[x]-mu[i];}}for (int i2;iN;i) mu[i]mu[i-1];
}
int calc()
{int ans0;for (int l1,r;la;lr1){ra/(a/l);int tmu[r]-mu[l-1];(t0)(tMOD);ansadd(ans,mul(t,add(mul(a/l,mul(a/l,a/l)),3*mul(a/l,a/l)%MOD)));}return ans;
}
int k,ans;
int lis[20005],siz[20005],tot;
void dfs(int pos,int phi,int res)
{if (postot){int tqpow(k,res);if (res1) tdec(t,k);else tadd(t,k);ansadd(ans,mul(phi,t));return;}int tqpow(lis[pos],siz[pos]);dfs(pos1,phi,res*t);t/lis[pos];dfs(pos1,phi*(lis[pos]-1),res*t);t/lis[pos];if (!t) return;for (;t;dfs(pos1,phi*lis[pos],res*t),t/lis[pos]);
}
signed main()
{init();int T;cinT;while (T--){cinna;kdec(mul(calc()2,INV6),1);totans0;int tn;for (int i1;icnt;i)if (t%pl[i]0){lis[tot]pl[i],siz[tot]0;while (t%pl[i]0) t/pl[i],siz[tot];}if (t1) lis[tot]t,siz[tot]1;dfs(1,1,1);if (n%mod0) n/mod,ans/mod;ansmul(ans,qpow(n,mod-2));coutans%mod\n;}return 0;
}
