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)(c2gcd(ΔP)1)k=1n(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=1mini=1nmig(c,T)i=1nf(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)=2Tm(Tm+1)T+mTmg(c,T)=dT(c2d1)μ(dT)
观察发现
∏ i = 1 n f ( m i , T ) \prod_{i=1}^n f(m_i,T) i=1nf(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=0naiH(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=1kg(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+n2i=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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 4816 [Sdoi2017]数字表格
下一篇:BZOJ 5332 [Sdoi2018]旧试题

发表评论

最新留言

不错!
[***.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国际化bundle_java语言国际化--ResouceBundle、struts 2019-04-21
java图片延迟加载_jQuery实现图片延迟加载 2019-04-21
java开发加入购物车功能_java web开发——购物车功能实现 2019-04-21
Java虚拟机不能满足_深入理解Java虚拟机--读书笔记1/3 2019-04-21
python 协程 asyncio_python – asyncio.as_completed是否会产生期货或协同程序? 2019-04-21
java设定xml文件的encoding_配置web-xml解决中文乱码问题,及各种乱码问题集结 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
graphql-php enum,php – 如何在不写长查询的情况下查询所有的GraphQL类型字段? 2019-04-21