正文

bzoj4816数字表格

Fenghr  Fenghr  2022-08-28  779

关键词：

首先是惯例的吐槽。SDOI题目名称是一个循环，题目内容也是一个循环，基本上过几年就把之前的题目换成另一个名字出出来，喜大普奔亦可赛艇。学长说考SDOI可以考出联赛分数，%%%。

下面放解题报告。并不喜欢打莫比鸟斯的解题报告就是因为公式编辑太鬼。

不知道多少分算法：简单模拟不解释。

正解一眼是莫比鸟斯函数，话说上次考莫比鸟斯就是去年吧，好像题目名也叫数字表格，只不过多了一个前缀"Crash的"。

慢慢推吧，这里公式编辑器好像坏了？雾,贼慢。

假设n<=m;(if(n>m)swap(n,m);)

老套路，枚举(i,j)，看被算了多少次。

$技术分享$

//好像不是严格意义上的布尔表达式？差不多就是这个意思吧。

然后提前+替换,变成了

$技术分享$

然后上面那一堆东西就是喜闻乐见的莫比鸟斯函数优化

变成这样一个鬼样子

$技术分享$

上面那堆就是喜闻乐见的数论分块搞搞。

然后注意到其实下面这一段也可以分块... ...

还是要解释一下：

把指数那一堆设为Get(nn,mm),可以用数论分块算出来。

然后原式就变成了

$\prod_{i = 1}^{n} \prod_{j = 1}^{m} f ((i, j))$

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;

const int N = 1000010;
const int Mod = 1000000007;
const int Nmod = Mod-1;
int n,m,f[N],miu[N],vis[N],P[N/10],tot,Ny[N];
int map[5010][5010];
LL Ans,ans;

inline int gi()
{
    int  x=0,res=1;char ch=getchar();
    while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)res=-res;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-48,ch=getchar();
    return x*res;
}

inline int QPow(int d,int z)
{
    int _ans=1;
    for(;z;z>>=1,d=(LL)d*d%Mod)
        if(z&1)_ans=(LL)_ans*d%Mod;
    return _ans;
}

inline void pre()
{
    f[1]=1;
    for(int i=2;i<N;++i){
        f[i]=f[i-1]+f[i-2];
        if(f[i]>=Mod)f[i]-=Mod;
    }
    f[0]=1;
    for(int i=1;i<N;++i)
        f[i]=(LL)f[i]*f[i-1]%Mod;
	for(int i=0;i<N;++i)
		Ny[i]=QPow(f[i],Mod-2);
}

inline void shai()
{
    miu[1]=1;
    for(int i=2;i<N;++i){
        if(!vis[i])P[++tot]=i,miu[i]=-1;
        for(int j=1;j<=tot;++j){
            int Inc=i*P[j];
            if(Inc>=N)break;
            vis[Inc]=1;
            if(i%P[j]==0)break;
            miu[Inc]=-miu[i];
        }
    }
    for(int i=1;i<=N;++i)
        miu[i]=miu[i-1]+miu[i];
}

inline int Get(int nn,int mm)
{
	if(nn<=5000 && mm<=5000)
	  if(map[nn][mm])return map[nn][mm];
    ans=0;
    for(int l=1,r;l<=nn;l=r+1){
        r=min(nn/(nn/l),mm/(mm/l));
        ans+=1ll*(miu[r]-miu[l-1])*(nn/l)*(mm/l);
    }
	ans%=Nmod;
	if(nn<=5000 && mm<=5000)map[nn][mm]=ans;
    return ans;
}

int main()
{
    pre();shai();int T=gi();
    while(T--){
        Ans=1;n=gi();m=gi();if(n>m)swap(n,m);
        for(int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            Ans=1ll*Ans*QPow(1ll*f[r]*Ny[l-1]%Mod,Get(n/l,m/l))%Mod;
        }
        printf("%lld
",Ans);
    }
    return 0;
}

bzoj4816:[sdoi2017]数字表格

题目链接bzoj4816:[Sdoi2017]数字表格题解满满的反演的套路的味道\[Ans=\prod_i=1^n\prod_j=1^mf[gcd(i,j)]\]常规操作枚举约数\[\prod_d=1^n\prod_i=1^n\prod_j=1^mgcd(i,j)==d\?\f[gcd(i,j)]\]上面的式子可以化为\[\prod_d=1^nf[d]^\su 查看详情

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]数字表格莫比乌斯反演

【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数字表格

...函数，话说上次考莫比鸟斯就是去年吧，好像题目名也叫数字表格，只不过多了一个前缀"Crash的"。慢慢推吧，查看详情

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]数字表格(莫比乌斯反演)(代码片段)

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]数字表格

题面戳我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 查看详情

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

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

思路：$Pi_{i=1}^nPi_{j=1}^mf[gcd(i,j)]$$=Pi_{d=1}^nPi_{i=1}^{lfloorfrac{n}{d} floor}Pi_{j=1}^{lfloorfrac{m}{d} floor}f[d]*(gcd(i,j)==1)$$Sigma_{k=1}^nPi_{d|k}Pi_{i=1}^{lfloorfrac{n}{dk} 查看详情

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

[bzoj2154]crash的数字表格

[BZOJ2154]Crash的数字表格试题描述今天的数学课上，Crash小朋友学习了最小公倍数(LeastCommonMultiple)。对于两个正整数a和b，LCM(a,b)表示能同时被a和b整除的最小正整数。例如，LCM(6,8)=24。回到家后，Crash还在想着课上学的东西，为了研... 查看详情