BZOJ 4816 数字表格

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

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

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

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

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

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

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

$\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}f[d]*[gcd(i,j)=d]$

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

然后提前+替换,变成了

$\prod_{d=1}^{n}f[d]^{\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[gcd(i,j)=1]}$

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

变成这样一个鬼样子

$\prod_{d=1}^{n}f[d]^{\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\mu (i)*\left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor}$

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

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

还是要解释一下：

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

然后原式就变成了

$\prod_{d=1}^{n}f[d]^{Get(\left \lfloor \frac{n}{d} \right \rfloor,\left \lfloor \frac{m}{d} \right \rfloor)}$

又可以喜闻乐见数论分块。

现在大概是O(n^1/2(n^1/2)^1/2)=O(n^3/4)*T;

然后直接肛正面应该只有60分。

100分的话卡卡常数，加点记忆化就过去了...就过去了...（大雾）。

然后还要预处理前缀积什么的，还要用逆元和欧拉函数降幂大法... ...

这题出的还是不错的。

然后好像逆元预处理比爆算要慢一点？雾。

其实可以离线后再省一点预处理的时间（丧心病狂）。

无所谓了。在B站上应该稳定40s以内吧。

把long long 改成int 是最好的常数优化。

#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\n",Ans);

    }

    return 0;

}

巴特西

BZOJ 4816 数字表格

最新文章

热门文章