关键词:
题目链接
总感觉博客园的\(Markdown\)很。。\(gouzhi\),可以看这的。
这个好像简单些啊,只要不犯sb错误
\(Description\)
用\(f[i]\)表示\(Fibonacci\)数列的第\(i\)项,求\[\prod_i=1^n\prod_j=1^mf[\gcd(i,j)]\mod (10^9+7)\]
\(Solution\)
\[ \beginaligned
Ans &=\prod_i=1^n\prod_j=1^mf[(i,j)]\ &=\prod_d=1^n\prod_i=1^n\prod_j=1^m[(i,j)=d]*f[d]\ &=\prod_d=1^nf[d]^\sum_i=1^n\sum_j=1^m[(i,j)=d]\ &=\prod_d=1^nf[d]^\sum_i=1^\lfloor\fracnd\rfloor\sum_j=1^\lfloor\fracmd\rfloor[(i,j)=1]\ &=\prod_d=1^nf[d]^\sum_i=1^min\mu(i)\lfloor\fracnid\rfloor\lfloor\fracmid\rfloor\ &=\prod_d=1^nf[d]^\sum_d\mid T\mu(\fracTd)\lfloor\fracnT\rfloor\lfloor\fracmT\rfloor
\endaligned
\]
直接去枚举\(T\),
\[ \beginaligned
Ans &=\prod_d=1^nf[d]^\sum_d\mid T\mu(\fracTd)\lfloor\fracnT\rfloor\lfloor\fracmT\rfloor\ &=\prod_T=1^n\prod_d\mid Tf[d]^\mu(\fracTd)\lfloor\fracnT\rfloor\lfloor\fracmT\rfloor\ &=\prod_T=1^n\prod_d\mid T(f[d]^\mu(\fracTd) )^\lfloor\fracnT\rfloor\lfloor\fracmT\rfloor
\endaligned
\]
同之前,枚举约数暴力更新\(\prod_d\mid Tf[d]^\mu(\fracTd)\),复杂度\(O(n\log n)\)。(\(\prod_d\mid Tf[\fracTd]^\mu(d)\))
注意次幂不能直接取模,利用费马小定理可以对\(mod-1\)取模。
然后注意\(f[0]=0\)。。
小结:
套路1:把\(\prod\)换到幂上去,这样就有\(\sum\)了。
套路2:令\(T=id\),在最外层枚举\(T\)。
另外常见的就不再写了。
F[]
用int,FP()
中的长式子放到外面,优化还是比较明显有的。
//17912kb 35060ms
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod (1000000007)
typedef long long LL;
const int N=1e6+2;
int cnt,P[N>>3],mu[N+2],f[N+2],inv_f[N+2],F[N+2];
bool Not_p[N+2];
inline int read()
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
int FP(LL x,int k)
LL t=1;
for(; k; k>>=1,x=x*x%mod)
if(k&1) t=t*x%mod;
return t;
void Init()
mu[1]=f[1]=inv_f[1]=1;//f[0]=0!
for(int i=2; i<N; ++i)
f[i]=(f[i-1]+f[i-2])%mod, inv_f[i]=FP(f[i],mod-2);
for(int i=2; i<N; ++i)
if(!Not_p[i]) P[++cnt]=i,mu[i]=-1;
for(int v,j=1; j<=cnt&&(v=i*P[j])<N; ++j)
Not_p[v]=1;
if(i%P[j]) mu[v]=-mu[i];
else mu[v]=0; break;
for(int i=0; i<N; ++i) F[i]=1;//F[0]=1
for(int i=1; i<N; ++i)
if(mu[i]==1)
for(int d=1,T=0; (T+=i)<N; ++d) F[T]=1ll*F[T]*f[d]%mod;
else if(mu[i]==-1)
for(int d=1,T=0; (T+=i)<N; ++d) F[T]=1ll*F[T]*inv_f[d]%mod;
for(int i=2; i<N; ++i) F[i]=1ll*F[i]*F[i-1]%mod;
inline int inv(int x)
return FP(x,mod-2);
int Calc(int n,int m)
if(n>m) std::swap(n,m);
int res=1;
for(int nxt,tmp,i=1; i<=n; i=nxt+1)
nxt=std::min(n/(n/i),m/(m/i)),
tmp=1ll*F[nxt]*inv(F[i-1])%mod,//存次数就没用啦?大概是留一个式子比较好?
res=1ll*res*FP(tmp,1ll*(n/i)*(m/i)%(mod-1))%mod;//注意次幂是模(mod-1)。
return res;
int main()
Init();
int T,n,m; scanf("%d",&T);
while(T--)
scanf("%d%d",&n,&m),printf("%d\n",Calc(n,m));
return 0;
bzoj4816[sdoi2017]数字表格(代码片段)
题面https://www.lydsy.com/JudgeOnline/problem.php?id=4816题解显然是莫比乌斯反演首先得出然后发现我们要把d提出去这样就好做了跟SDOI2015的一道题类似因为$leftlfloorfracnpightfloorleftlfloorfracmpightfloor$只有$(sqrtn+sqrtm)$种取 查看详情
[bzoj4816][sdoi2017]数字表格
[BZOJ4816][Sdoi2017]数字表格试题描述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的最... 查看详情
bzoj4816:[sdoi2017]数字表格
问题: [n/k]/d==[n/(kd)]; 线性筛正确性证明 这么求逆元Right?a=k*p; 1LL转化作用域 longlong做数组下标#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongLint;constintmaxn=100 查看详情
bzoj4816:[sdoi2017]数字表格
DescriptionDoris刚刚学习了\(fibonacci\)数列。用\(f[i]\)表示数列的第\(i\)项,那么\[\beginalignf[0]&=0\\f[1]&=1\\f[n]&=f[n-1]+f[n-2],n>=2\endalign\]Doris用老师的超级计算机生成了一个\(n\timesm\)的表格,第\(i\)行第\(j\)列的格子中的 查看详情
[bzoj4816][sdoi2017]数字表格(莫比乌斯反演)(代码片段)
4816:[Sdoi2017]数字表格TimeLimit:50Sec MemoryLimit:128MBSubmit:1259 Solved:625[Submit][Status][Discuss]DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项,那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2] 查看详情
bzoj4816[sdoi2017]数字表格
TimeLimit: 50Sec MemoryLimit: 128MBSubmit: 646 Solved: 296DescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项,那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2],n>=2Doris用老师的超级计算 查看详情
bzoj4816[sdoi2017]数字表格莫比乌斯反演
【BZOJ4816】[Sdoi2017]数字表格DescriptionDoris刚刚学习了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,... 查看详情
bzoj4816:[sdoi2017]数字表格
题面戳我Sol摆公式:(ans=Pi_{i=1}^{n}Pi_{j=1}^{m}f[gcd(i,j)])考虑每个gcd的贡献,设n<m则就是(Pi_{d=1}^{n}Pi_{i=1}^{lfloorfrac{n}{d}
floor}Pi_{j=1}^{lfloorfrac{m}{d}
floor}f[d]*[gcd(i,j)==1])(=Pi_{d=1}^{ 查看详情
bzoj4816[sdoi2017]数字表格
题目链接以下除法均指下取整[prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))=prod_{x}f(x)^{sum_isum_j[gcd(i,j)=x]}=prod_{x}f(x)^{sum_{x|d}mu(frac{d}{x})frac{n}{d}frac{m}{d}}=prod_{d}(prod_{x|d}f(x)^{mu(frac{d 查看详情
bzoj.4816.[sdoi2017]数字表格(莫比乌斯反演)(代码片段)
题目链接总感觉博客园的\(Markdown\)很。。\(gouzhi\),可以看这的。这个好像简单些啊,只要不犯sb错误\(Description\) 用\(f[i]\)表示\(Fibonacci\)数列的第\(i\)项,求\[\prod_i=1^n\prod_j=1^mf[\gcd(i,j)]\mod(10^9+7)\]\(Solution\)\[\beginalignedAns& 查看详情
bzoj4816sdoi2017数字表格(代码片段)
一开始只推出O(TN)的做法,后来看了看发现再推一步就好了。我们只需要枚举gcd就可以啦。然后我们改变一下枚举顺序 设T为dk预处理中间那部分前缀积就好了。1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e6+10,mod=1e9+7;4intn,m,... 查看详情
sdoi2017round1day1题解(bzoj4816bzoj4817bzoj4818)
不知道有几个AK的,除了出题人SB搬了个BZOJ3779以外,应该没什么因素阻碍AK吧。要是SCOI考这套题多好。BZOJ4816数字表格SB反演,推出$ans=prod_{i=1}^nf^{sum_{j=1}^{leftlfloorfracni
ight
floor}mu(j)leftlfloorfracn{ij}
ight
floorleftlfloorfrac 查看详情
bzoj4816数字表格
...函数,话说上次考莫比鸟斯就是去年吧,好像题目名也叫数字表格,只不过多了一个前缀"Crash的"。慢慢推吧, 查看详情
bzoj4816数字表格(莫比乌斯反演)
【BZOJ4816】数字表格(莫比乌斯反演)题面BZOJ求[prod_{i=1}^nprod_{j=1}^mf[gcd(i,j)]]题解忽然不知道这个要怎么表示。。。就写成这样吧。。[prod_{d=1}^nprod_{i=1}^nprod_{j=1}^mif(gcd(i,j)==d)f[gcd(i,j)]]直接把(f[d])提出来[prod_{d=1}^{n}f[d]^ 查看详情
[bzoj4816]数字表格莫比乌斯反演
第一次见到这种形式,推了两步就被卡住了。没想到还能这么迁移QAQ,真强!题目设$f(i)$为第$i$项斐波那契数列要求计算$$ans=prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))$$枚举$d=gcd$得到$$ans=prod_{d=1}^nf(d)^{sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==d]}$$然后反演得... 查看详情
[sdoi2017]数字表格
[Sdoi2017]数字表格http://www.lydsy.com/JudgeOnline/problem.php?id=4816TimeLimit: 50Sec MemoryLimit: 128MBDescriptionDoris刚刚学习了fibonacci数列。用f[i]表示数列的第i项,那么f[0]=0f[1]=1f[n]=f[n-1]+f[n-2 查看详情
p3704[sdoi2017]数字表格
#include<iostream>#include<cstdio>#include<cstring>#defineLLlonglong#definemaxn1000009#defineNmaxn+10#defineM1000000007usingnamespacestd;intn,m;intq;LLksm(LLa,LLp){ LLans=1; for(;p;p 查看详情
学术篇sdoi2017数字表格
======传======送======门======在======里======面======去年忘记可以预处理了...然后就打了10pts的暴力...现在学了莫比乌斯反演就可以来做了=======================================这个题目看着非常的简单,就是要求这个式子[prod_{i=1}^Nprod_{j=1}^Mf[gcd... 查看详情