首页 > 代码库 > BZOJ 4816 数字表格
BZOJ 4816 数字表格
首先是惯例的吐槽。SDOI题目名称是一个循环，题目内容也是一个循环，基本上过几年就把之前的题目换成另一个名字出出来，喜大普奔亦可赛艇。学长说考SDOI可以考出联赛分数，%%%。
下面放解题报告。并不喜欢打莫比鸟斯的解题报告就是因为公式编辑太鬼。
不知道多少分算法：简单模拟不解释。
正解一眼是莫比鸟斯函数，话说上次考莫比鸟斯就是去年吧，好像题目名也叫数字表格，只不过多了一个前缀"Crash的"。
慢慢推吧，这里公式编辑器好像坏了？雾,贼慢。
假设n<=m;(if(n>m)swap(n,m);)
老套路，枚举(i,j)，看被算了多少次。
//好像不是严格意义上的布尔表达式？差不多就是这个意思吧。
然后提前+替换,变成了
然后上面那一堆东西就是喜闻乐见的莫比鸟斯函数优化
变成这样一个鬼样子
上面那堆就是喜闻乐见的数论分块搞搞。
然后注意到其实下面这一段也可以分块... ...
还是要解释一下：
把指数那一堆设为Get(nn,mm),可以用数论分块算出来。
然后原式就变成了
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#define LL long longusing 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 数字表格
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。