BZOJ 4816 [Sdoi2017]数字表格
发布日期:2021-05-04 16:55:20
浏览次数:49
分类:技术文章
本文共 2302 字,大约阅读时间需要 7 分钟。
题目链接
题解
反演
∏ T = 1 min ( n , m ) ( ∏ d ∣ T f i b ( d ) μ ( d ) ) ⌊ n / d ⌋ ⌊ m / d ⌋ \prod_{T=1}^{\min(n,m)}(\prod_{d|T}fib(d)^{\mu(d)})^{\lfloor n/d\rfloor\lfloor m/d\rfloor} T=1∏min(n,m)(d∣T∏fib(d)μ(d))⌊n/d⌋⌊m/d⌋ 预处理出中间部分,整除分块即可。注意不要暴力算 f i b ( d ) fib(d) fib(d)的逆元,可以预处理出逆元。
代码
#include#include int read(){ int x=0,f=1; char ch=getchar(); while((ch<'0')||(ch>'9')) { if(ch=='-') { f=-f; } ch=getchar(); } while((ch>='0')&&(ch<='9')) { x=x*10+ch-'0'; ch=getchar(); } return x*f;}const int maxn=1000000;const int mod=1000000007;const int pmod=mod-1;int quickpow(int a,int b){ int res=1; while(b) { if(b&1) { res=1ll*res*a%mod; } a=1ll*a*a%mod; b>>=1; } return res;}int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],f[maxn+10],fib[maxn+10],ifib[maxn+10];int getprime(){ p[1]=mu[1]=1; for(int i=2; i<=maxn; ++i) { if(!p[i]) { prime[++cnt]=i; mu[i]=-1; } for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j) { int x=i*prime[j]; p[x]=1; if(i%prime[j]==0) { mu[x]=0; break; } mu[x]=-mu[i]; } } fib[0]=ifib[0]=0; fib[1]=ifib[1]=1; for(int i=2; i<=maxn; ++i) { fib[i]=fib[i-1]+fib[i-2]; if(fib[i]>=mod) { fib[i]-=mod; } ifib[i]=quickpow(fib[i],mod-2); } for(int i=0; i<=maxn; ++i) { f[i]=1; } for(int d=1; d<=maxn; ++d) { for(int T=d; T<=maxn; T+=d) { if(mu[T/d]==1) { f[T]=1ll*f[T]*fib[d]%mod; } else if(mu[T/d]==-1) { f[T]=1ll*f[T]*ifib[d]%mod; } } } for(int i=1; i<=maxn; ++i) { f[i]=1ll*f[i]*f[i-1]%mod; } return 0;}int T,n,m;int main(){ getprime(); T=read(); while(T--) { n=read(); m=read(); int res=1; for(int l=1,r; l<=std::min(n,m); l=r+1) { r=std::min(n/(n/l),m/(m/l)); res=1ll*res*quickpow(1ll*f[r]*quickpow(f[l-1],mod-2)%mod,1ll*(n/l)*(m/l)%pmod)%mod; } printf("%d\n",res); } return 0;}
转载地址:https://blog.csdn.net/wang3312362136/article/details/86062256 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月01日 21时52分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
解决mac里面打开控制台提示 您需要安装JDK才能使用"java"命令行工具
2019-04-28
reactos操作系统实现(92)
2019-04-28
reactos操作系统实现(93)
2019-04-28
使用Python快速实现显示器关闭和锁住桌面
2019-04-28
reactos操作系统实现(94)
2019-04-28
reactos操作系统实现(95)
2019-04-28
reactos操作系统实现(96)
2019-04-28
reactos操作系统实现(97)
2019-04-28
reactos操作系统实现(98)
2019-04-28
reactos操作系统实现(99)
2019-04-28
miniport, port driver,disk.sys 之间的关系(转)
2019-04-28
Python标准库:内置函数tuple([iterable])
2019-04-28
Python标准库:内置函数type(object)
2019-04-28
Python标准库:内置函数vars([object])
2019-04-28
人人都懂的编程课(Python)
2019-04-28
reactos操作系统实现(100)
2019-04-28
reactos操作系统实现(101)
2019-04-28
Python标准库:内置函数zip(*iterables)
2019-04-28
3.2.5.5 一句话中的字随机排列
2019-04-28