4816: [Sdoi2017]数字表格
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 1259 Solved: 625[][][]Description
Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项,那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算机生成了一个n×m的表格,第i行第j列的格子中的数是f[gcd(i,j)],其中gcd(i,j)表示i,j的最大公约数。Doris的表格中共有n×m个数,她想知道这些数的乘积是多少。答案对10^9+7取模。Input
有多组测试数据。
第一个一个数T,表示数据组数。接下来T行,每行两个数n,mT<=1000,1<=n,m<=10^6Output
输出T行,第i行的数是第i组数据的结果Sample Input
3 2 3 4 5 6 7Sample Output
1 6 960HINT
Source
[ ][ ][ ]
不知道为什么要用fibonacci,感觉既没有用到矩乘又没有用到$gcd(f[i],f[j])=f[gcd(i,j)]$的性质。
首先列出连乘式,可以发现很像莫比乌斯反演,先试着推一下式子,从每个数出现的次数入手。
$$Ans(n,m)=\prod_{d}f(d)^{\sum_{i=1}^{n}\sum_{j=1}^m[(i,j)=d]}=\prod_{d=1}^{\min(n,m)}f(d)^{\sum_{p=1}^{\frac{\min(n,m)}{d}}\mu(d)\lfloor \frac{n}{pd}\rfloor \lfloor\frac{m}{pd}\rfloor}$$到这里,有一种想法(可以拿60分):设$$g(n,m,d)=\sum_{i=1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i}\rfloor$$这样$$Ans(n,m)=\prod_{d=1}^{\lfloor \frac{\min(n,m)}{d} \rfloor}f(d)^{g(\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor,d)}$$这个看上去用分块优化可以做到$$\begin{aligned}O(T\int_1^n\sqrt{\frac{n}{x}}dx)& =O(T\sqrt{n}\int_1^n\sqrt{\frac{1}{x}}dx)\\ & =O(2T\sqrt{n}\sqrt{n})\\ & =O(Tn)\end{aligned}$$
于是就有60分了。那么我们继续化简刚才的式子:$$\begin{aligned}Ans(n,m)& =\prod_{d=1}^{\min(n,m)}f(d)^{\sum_{d|T}^{\min(n,m)}\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor}\\ & =\prod_{T=1}^{\min(n,m)}\prod_{d|T}f(d)^{\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor\lfloor\frac{m}{T}\rfloor}\\ & =\prod_{T=1}^{\min(n,m)}g(T)^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}\end{aligned}$$ $g(T)$可以预处理出来,这样总复杂度就是$O(n\log n+T\sqrt{\min(n,m)})$了。注意$\mu$在指数上时会有$-1$,这个要求逆元,如果先预处理所有$f[i]$的逆元的话会快一倍。这道题总体并不难,主要就是将莫比乌斯反演中的一些套路从加法变成乘法了,实现的时候有几个细节注意一下就好。
(以后再也不手写LaTeX莫比乌斯反演的题解了)
1 #include2 #include 3 #define rg register int 4 #define rep(i,l,r) for (rg i=l; i<=r; i++) 5 typedef long long ll; 6 using namespace std; 7 8 const int N=1000100,mod=1000000007; 9 bool b[N];10 int n,m,T,ans,tot,p[N],f[N],g[N],G[N],G1[N],miu[N],F[N][3];11 12 int ksm(int a,int b){13 int res;14 for (res=1; b; a=1ll*a*a%mod,b>>=1)15 if (b & 1) res=1ll*res*a%mod;16 return res;17 }18 19 void pre(){20 miu[1]=1;21 for (rg i=2; i m) swap(n,m); ans=1;44 for (rg i=1; i<=n; i=lst+1){45 lst=min(n/(n/i),m/(m/i));46 ans=1ll*ans*ksm(1ll*G[lst]*G1[i-1]%mod,1ll*(n/i)*(m/i)%(mod-1))%mod;47 }48 printf("%d\n",ans);49 }50 return 0;51 }