BZOJ 3434 [Wc2014]时空穿梭
发布日期:2021-05-04 16:55:19
浏览次数:40
分类:技术文章
本文共 4139 字,大约阅读时间需要 13 分钟。
题目链接
题解
枚举选取的第一个点和最后一个点的坐标差
∑ Δ P = ( Δ x 1 , Δ x 2 , ⋯   , Δ x n ) ( gcd ( Δ P ) − 1 c − 2 ) ∏ k = 1 n ( m i − Δ x i + 1 ) \sum_{\Delta P=(\Delta x_1,\Delta x_2,\cdots,\Delta x_n)}\binom{\gcd(\Delta P)-1}{c-2}\prod_{k=1}^n (m_i-\Delta x_i+1) ΔP=(Δx1,Δx2,⋯,Δxn)∑(c−2gcd(ΔP)−1)k=1∏n(mi−Δxi+1) 反演得到 ∑ T = 1 min i = 1 n m i g ( c , T ) ∏ i = 1 n f ( m i , T ) \sum_{T=1}^{\min_{i=1}^n m_i}g(c,T)\prod_{i=1}^n f(m_i,T) T=1∑mini=1nmig(c,T)i=1∏nf(mi,T) 其中 f ( m , T ) = − ⌊ m T ⌋ ( ⌊ m T ⌋ + 1 ) 2 T + m ⌊ m T ⌋ g ( c , T ) = ∑ d ∣ T ( d − 1 c − 2 ) μ ( T d ) f(m,T)=-\frac{\lfloor\frac{m}{T}\rfloor(\lfloor\frac{m}{T}\rfloor+1)}{2}T+m\lfloor\frac{m}{T}\rfloor\\ g(c,T)=\sum_{d|T}\binom{d-1}{c-2}\mu(\frac{T}{d}) f(m,T)=−2⌊Tm⌋(⌊Tm⌋+1)T+m⌊Tm⌋g(c,T)=d∣T∑(c−2d−1)μ(dT) 观察发现 ∏ i = 1 n f ( m i , T ) \prod_{i=1}^n f(m_i,T) i=1∏nf(mi,T) 可以看作一个关于 T T T的 n n n次多项式,每一项的系数最多只有 ∑ i = 1 n m i \sum_{i=1}^n \sqrt{m_i} ∑i=1nmi种,因此可以整除分块分别求系数。假设求出的系数分别为 a 0 , a 1 , ⋯   , a n a_0,a_1,\cdots ,a_n a0,a1,⋯,an,那么答案就是 ∑ i = 0 n a i H ( c , i , min i = 1 n m i ) \sum_{i=0}^n a_i H(c,i,\min_{i=1}^n m_i) i=0∑naiH(c,i,i=1minnmi) 其中 H ( c , i , k ) = ∑ T = 1 k g ( c , T ) T i H(c,i,k)=\sum_{T=1}^k g(c,T)T^i H(c,i,k)=T=1∑kg(c,T)Ti 可以预处理出 H H H。时间复杂度 O ( n c m + ∑ n 2 ∑ i = 1 n m i ) O(ncm+\sum n^2\sum_{i=1}^n \sqrt{m_i}) O(ncm+∑n2∑i=1nmi)。
代码
#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=11;const int maxc=20;const int maxm=100000;const int mod=10007;const int inf=0x3f3f3f3f;int p[maxm+10],prime[maxm+10],cnt,mu[maxm+10],C[maxm+10][maxc+2],g[maxc+2][maxm+10],h[maxc+2][maxn+2][maxm+10],power[maxm+10][maxn+2];int getprime(){ p[1]=mu[1]=1; for(int i=2; i<=maxm; ++i) { if(!p[i]) { prime[++cnt]=i; mu[i]=mod-1; } for(int j=1; (j<=cnt)&&(i*prime[j]<=maxm); ++j) { int x=i*prime[j]; p[x]=1; if(i%prime[j]==0) { mu[x]=0; break; } mu[x]=mod-mu[i]; } } for(int i=0; i<=maxm; ++i) { C[i][0]=1; for(int j=1; (j<=maxc)&&(j<=i); ++j) { C[i][j]=C[i-1][j]+C[i-1][j-1]; if(C[i][j]>=mod) { C[i][j]-=mod; } } } for(int i=1; i<=maxm; ++i) { power[i][0]=1; for(int j=1; j<=maxn; ++j) { power[i][j]=power[i][j-1]*i%mod; } } for(int c=2; c<=maxc; ++c) { for(int d=1; d<=maxm; ++d) { for(int T=d; T<=maxm; T+=d) { g[c][T]=(g[c][T]+C[d-1][c-2]*mu[T/d])%mod; } } } for(int c=2; c<=maxc; ++c) { for(int i=0; i<=maxn; ++i) { for(int k=1; k<=maxm; ++k) { h[c][i][k]=(h[c][i][k-1]+g[c][k]*power[k][i])%mod; } } } return 0;}int T,n,c,m[maxn+2],minm,a[maxn+2];int main(){ getprime(); T=read(); while(T--) { n=read(); c=read(); minm=inf; for(int i=1; i<=n; ++i) { m[i]=read(); minm=std::min(minm,m[i]); } int ans=0; for(int l=1,r; l<=minm; l=r+1) { r=inf; for(int i=1; i<=n; ++i) { r=std::min(r,m[i]/(m[i]/l)); } for(int i=0; i<=n; ++i) { a[i]=(i==0); } for(int i=1; i<=n; ++i) { int k=m[i]/l,x=1ll*m[i]*k%mod,y=(1ll*k*(k+1)/2)%mod*(mod-1)%mod; for(int j=n; j; --j) { a[j]=(x*a[j]+y*a[j-1])%mod; } a[0]=a[0]*m[i]%mod*k%mod; } for(int i=0; i<=n; ++i) { ans=(ans+a[i]*(h[c][i][r]-h[c][i][l-1]+mod))%mod; } } printf("%d\n",ans); } return 0;}
转载地址:https://blog.csdn.net/wang3312362136/article/details/86062166 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年03月28日 10时41分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java程序有连接数据库_Java程序连接数据库
2019-04-21
java reduce.mdn_reduce高级用法
2019-04-21
java shape用法_Java PShape.scale方法代码示例
2019-04-21
java字符串三目_java字符串连接运算符和三目运算符
2019-04-21
java 堆内存 非堆内存_JVM 堆内存和非堆内存
2019-04-21
Java新手写什么demo_通过入门demo简单了解netty使用方法
2019-04-21
java图片延迟加载_jQuery实现图片延迟加载
2019-04-21
java开发加入购物车功能_java web开发——购物车功能实现
2019-04-21
Java虚拟机不能满足_深入理解Java虚拟机--读书笔记1/3
2019-04-21
hanlp java api_java分词工具hanlp介绍
2019-04-21
nginx php 源码安装,Nginx1.12.2加php7.2.0的编译安装
2019-04-21
php 删除字节,php – 删除无效/不完整的多字节字符
2019-04-21
php 实现版本号对比,如何在PHP中实现比较版本号
2019-04-21
php sql 给数据库追加内容,php如何向数据库中的某串数据后追加内容【急】
2019-04-21
php微信小程序获取用户信息,微信小程序授权获取用户详细信息openid的实例详解...
2019-04-21
Java三元运算和if,Java三元运算符与<JDK8兼容性中的if / else
2019-04-21