正文

bzoj4816:[sdoi2017]数字表格

Nico&11101001  Nico&11101001  2022-10-27  112

关键词：

题目链接

bzoj4816: [Sdoi2017]数字表格

题解

满满的反演的套路的味道
\[Ans= \prod_i=1^n \prod_j=1^m f[gcd(i,j)]\]
常规操作枚举约数
\[\prod_d=1^n\prod_i=1^n\prod_j=1^m gcd(i,j)==d\ ?\ f[gcd(i,j)]\]
上面的式子可以化为
\[\prod_d=1^nf[d]^\sum_i=1^n\sum_j=1^m[gcd(i,j)==d]\]

对于
\[\sum_i=1^n\sum_j=1^m[gcd(i,j)==d]\]
很眼熟...推下式子
\[=\sum_i=1^? \dfracnd?\sum_j=1^?\dfracmd?[gcd(i,j)==1]\]
\[=\sum_i=1^min(\dfracnd,\dfracmd) \mu(i)\sum_i|p,p\leq n/d \sum_i|j,j\leq m/d1\]
\[=\sum_i=1^n/d\mu(i)\left \lfloor \fracnid\right \rfloor \left \lfloor\fracmid \right \rfloor\]
令$p=id$那么原式变成了
\[\prod_p=1^min(n,m) \prod_d|p f[d]^\left \lfloor \fracnp \right \rfloor \left \lfloor \fracmp \right \rfloor \mu(\fracpd) = \prod_p=1^min(n,m) (\prod_d|p f[d]^\mu(\fracpd))^\left \lfloor \fracnp \right \rfloor \left \lfloor \fracmp \right \rfloor\]
对于每个$p$,令$F[p]=\prod_d|p f[d]^\mu(\fracpd)$,$F[p]$的值是固定的，用筛法求出$F[p]$，做前缀积，对与$\left \lfloor \fracnp \right \rfloor \left \lfloor \fracmp \right \rfloor$数论分块一下
复杂度为$O((n+T\sqrtn)log(1e9+7))$

代码

#include<cstdio>
#include<algorithm>
const int maxn = 1000007;
const int mod = 1e9+7;
int f[maxn+7],invf[maxn+7],F[maxn+7];
bool isprime[maxn+7];int mu[maxn+7],prime[maxn+7],num;

int pow(int a,int p) 
    int ret=1;
    for(;p;p>>=1,a=(1LL*a*a)%mod)
        if(p&1) ret=(1LL*ret*a)%mod;
    
    return ret;


void init() 
    f[1]=1;
    for(int i=2;i<maxn;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for(int i=1;i<maxn;++i) 
        invf[i]=pow(f[i],mod-2)%mod;
        //printf("%d %d\n",invf[i],f[i]);
    
    isprime[1]=1;mu[1]=1;F[0]=F[1]=1;
    //printf("%d\n",mu[1]);
    for(int i=2;i<=maxn-7;++i) 
        F[i]=1;
        if(!isprime[i]) prime[++num]=i,mu[i]=-1;
        for(int j=1;j<=num&&prime[j]*i<=maxn-7;++j) 
            isprime[i*prime[j]]=1;
            if(i%prime[j]==0) mu[i*prime[j]]=0;break;
            else mu[i*prime[j]]=-mu[i];
        
    
    for(int i=1;i<=maxn-7;++i) 
        if(mu[i]==0)continue;
        for(int j=i;j<=maxn-7;j+=i) 
            if(mu[i]==1) F[j]=(1ll*F[j]*f[j/i])%mod;
            if(mu[i]==-1) F[j]=(1ll*F[j]*invf[j/i])%mod;
        
    
    for(int i=1;i<=maxn-7;++i) F[i]=(1ll*F[i]*F[i-1])%mod;//,printf("%d\n",F[i]);

int query(int a,int b) 
    int n=std::min(a,b);long long ans=1;
    for(int nxt,i=1;i<=n;i=nxt+1) 
        nxt=std::min(a/(a/i),b/(b/i));
        long long tmp=1ll*F[nxt]*pow(F[i-1],mod-2)%mod;
        ans=(1ll*ans*pow(tmp,1ll*(a/i)*(b/i)%(mod-1)))%mod;
    
    return (ans+mod)%mod;


int main() 
    //freopen("001.out","w",stdout);
    init(); 
    int T;scanf("%d",&T);
    for(int a,b;T--;) 
        scanf("%d%d",&a,&b);
        printf("%d\n",query(a,b));
    
    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的"。慢慢推吧，查看详情

[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 查看详情

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]}$$然后反演得... 查看详情

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... 查看详情