BZOJ 4816 數字表格，bzoj4816數字表格

BZOJ 4816 數字表格，bzoj4816數字表格

首先是慣例的吐槽。SDOI題目名稱是一個循環，題目內容也是一個循環，基本上過幾年就把之前的題目換成另一個名字出出來，喜大普奔亦可賽艇。學長說考SDOI可以考出聯賽分數，%%%。

下面放解題報告。並不喜歡打莫比鳥斯的解題報告就是因為公式編輯太鬼。

不知道多少分算法：簡單模擬不解釋。

正解一眼是莫比鳥斯函數，話說上次考莫比鳥斯就是去年吧，好像題目名也叫數字表格，只不過多了一個前綴"Crash的"。

慢慢推吧，這裡公式編輯器好像壞了？霧,賊慢。

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

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

//好像不是嚴格意義上的布爾表達式？差不多就是這個意思吧。

然後提前+替換,變成了

然後上面那一堆東西就是喜聞樂見的莫比鳥斯函數優化

變成這樣一個鬼樣子

上面那堆就是喜聞樂見的數論分塊搞搞。

然後注意到其實下面這一段也可以分塊... ...

還是要解釋一下：

把指數那一堆設為Get(nn,mm),可以用數論分塊算出來。

然後原式就變成了

又可以喜聞樂見數論分塊。

現在大概是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;
}