微信步数C++

题目：

 

样例解释：

【样例 #1 解释】

从 (1,1) 出发将走 2 步，从 (1,2) 出发将走 4 步，从 (1,3) 出发将走 4 步。
从 (2,1) 出发将走 2 步，从 (2,2) 出发将走 3 步，从 (2,3) 出发将走 3 步。
从 (3,1) 出发将走 1 步，从 (3,2) 出发将走 1 步，从 (3,3) 出发将走 1 步。
共计 21 步。

 

思路：

先考虑O(nkw)O(nkw)的30分暴力。

显然，每个维度上走过的位置是一个区间。

只要走的步数确定，那么这个区间关于起点位置的相对位置也就确定了。

只要先算出每个循环向左/右所走的最远距离，以及一个循环的移位即可。

这样，考虑一个算法：

枚举走了多少步结束，并算出贡献（就是算出满足条件的起点数目）。

先枚举走出区域的上一步，走到了循环节中的哪个位置，以及走了多少循环节。

由于不能走出区域，于是可以根据每个维度的区间来算出这个维度的起点所在区间。

设下一步修改的维度为cc。根据对应的dd，容易算出这个维度的起点位置。

那么，这个位置必须在起点区间内。

满足这个条件的基础上，把其他维度的起点区间长度相乘就是起点数目。

考虑优化：

这个算法的主要瓶颈在于对循环节数的枚举。

设走过的循环节数目为xx。

那么，不难发现，每个维度的区间的相对位置（即左右端点与起点的距离）是关于xx的一次函数。

由于这一维度的方案数等于w+1w+1减去区间长度，因此这也是关于xx的一次函数。

根据这个区间长度为正数，可以得出xx的取值范围。

同时，维度cc的起点位置也是关于xx的一次函数。

根据这个位置必须在起点区间内部，进一步缩小xx的取值范围。

这样，答案就是对于每个xx，这些一次函数在xx处的值的乘积的和。

暴力进行多项式乘法并用自然数幂前缀和即可。

时间复杂度O(nk2)O(nk2)。

注意这个写法，可能要对x=0x=0进行特判。

 

 

代码：

#include <stdio.h>
#define inf 1999999999
#define md 1000000007
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
int az[12],al[12],ar[12],w[12],aa[500010][12];
int B[12],C[500010],D[500010],la[500010][12],ra[500010][12];
int ksm(int a,int b) {
	int jg=1;
	while(b>0) {
		if(b&1)
			jg=1ll*jg*a%md;
		a=1ll*a*a%md;
		b=(b>>1);
	}
	return jg;
}
int Cc[12][12],xs[12][12];
void GetB(int k)//伯努利数 
{
	B[0]=1;
	for (int i=1;i<=k+1;i++) {
		for (int j=0;j<=i;j++) {
			if(j==0||j==i)Cc[i][j]=1; 
			else Cc[i][j]=(Cc[i-1][j]+Cc[i-1][j-1])%md;
		}
	}
	for (int i=1;i<=k;i++) {
		int h=0;
		for (int j=0;j<i;j++)
			h=(h+1ll*Cc[i+1][j]*B[j])%md;
		B[i]=1ll*(md-h)*ksm(i+1,md-2)%md;
	}
	for (int i=1;i<=k;i++) {
		int ny=ksm(i+1,md-2);
		for (int j=0;j<=i;j++)
			xs[i][i+1-j]=1ll*Cc[i+1][j]*B[j]%md*ny%md;
	}
}
struct SLi//一次函数 
{
	int k,b;
	SLi() {}
	SLi(int K,int B) {
		k=K;b=B;
	}
	SLi(int Z) {
		k=0;b=Z;
	}
};
SLi operator-(const SLi &x,const SLi &y) {
	return SLi(x.k-y.k,x.b-y.b);
}
int Sum(int k,int n) {
	if(k==0)
		return n+1;
	int jg=0;
	for (int i=0,j=1;i<=k+1;i++) {
		jg=(jg+1ll*j*xs[k][i])%md;
		j=1ll*j*(n+1)%md;
	}
	return jg;
}
struct DXS//多项式 
{
	int sz[12],n;
	void operator=(const DXS &a) {
		n=a.n;
		for (int i=0;i<=n;i++)
			sz[i]=a.sz[i];
	}
	void clear() {
		for (int i=1;i<=10;i++)
			sz[i]=0;
		sz[0]=1;n=0;
	}
	int sum(int l,int r) {
		int ans=0;
		for (int i=0;i<=n;i++) {
			int t=(Sum(i,r)-Sum(i,l-1)+md)%md;
			ans=(ans+1ll*sz[i]*t)%md;
		}
		return ans;
	}
};
DXS operator*(const DXS&x,const SLi&y) {
	DXS rt;
	rt.n=x.n+1;
	rt.sz[rt.n]=0;
	for (int i=0;i<=x.n;i++)
		rt.sz[i]=1ll*y.b*x.sz[i]%md;
	for (int i=0;i<=x.n;i++)
		rt.sz[i+1]=(rt.sz[i+1]+1ll*y.k*x.sz[i])%md;
	return rt;
}
struct SQj//维护区间 
{
	int l,r;
	SQj() {}
	SQj(int L,int R) {
		l=L;r=R;
	}
};
SQj jiao(const SQj&a,const SQj&b) {
	return SQj(max(a.l,b.l),min(a.r,b.r));
}
int floor(int,int);
int ceil(int x,int y) {
	if(y<0)x=-x,y=-y;
	if(x>=0)return (x+y-1)/y;
	return -floor(-x,y);
}
int floor(int x,int y) {
	if(y<0)x=-x,y=-y;
	if(x>=0)return x/y;
	return -ceil(-x,y);
}
SQj Less(SLi a,SLi b) {
	int x=a.k-b.k,y=b.b-a.b;
	if(x==0)return y>=0?SQj(-inf,inf):SQj(inf,-inf);
	if(x>0)return SQj(-inf,floor(y,x));
	return SQj(ceil(y,x),inf);
}
SQj More(SLi a,SLi b) {
	int x=a.k-b.k,y=b.b-a.b;
	if(x==0)return y<=0?SQj(-inf,inf):SQj(inf,-inf);
	if(x>0)return SQj(ceil(y,x),inf);
	return SQj(-inf,floor(y,x));
}
int cal0(int n,int i,int k) {
	int l[12],r[12],jg=1;
	for (int c=1;c<=k;c++)
		l[c]=la[i][c],r[c]=ra[i][c];
	for (int c=1;c<=k;c++) {
		int zl=1-l[c],zr=w[c]-r[c];
		if(c!=C[(i+1)%n]) {
			int s=zr-zl+1;
			if(s<0)s=0;
			jg=1ll*jg*s%md;
		} 
		else {
			int t=aa[i][c],s=0;
			if(D[(i+1)%n]==1) {
				int o=w[c]-t;
				if(o>=zl&&o<=zr)s=1;
			} 
			else {
				int o=1-t;
				if(o>=zl&&o<=zr)s=1;
			}
			jg=1ll*jg*s%md;
		}
	}
	return 1ll*(i+2)*jg%md;
}
int main() {
	int n,k;
	scanf("%d%d",&n,&k);GetB(k);
	for (int i=1;i<=k;i++)
		scanf("%d",&w[i]);
	for (int i=0;i<n;i++) {
		scanf("%d%d",&C[i],&D[i]);
		if(i>0) {
			for (int j=1;j<=k;j++)
				aa[i][j]=aa[i-1][j];
		}
		aa[i][C[i]]+=D[i];//循环节中某一前缀的偏移量
		az[C[i]]+=D[i];
		if(az[C[i]]<al[C[i]])//最左移位
			al[C[i]]=az[C[i]];
		if(az[C[i]]>ar[C[i]])//最右移位
			ar[C[i]]=az[C[i]];
		for (int j=1;j<=k;j++) {
			la[i][j]=al[j];ra[i][j]=ar[j];
		}
	}
	bool zd=false;
	for (int i=1;i<=k;i++) {
		if(az[i]!=0||ar[i]-al[i]>=w[i]) {
			zd=true;break;
		}
	}
	if(!zd)//走不出去 
	{
		printf("-1");
		return 0;
	}
	int ans=1;
	for (int i=1;i<=k;i++) {
		if(i!=C[0])
			ans=1ll*ans*w[i]%md;
	}
	for (int i=0;i<n;i++) {
		ans=(ans+cal0(n,i,k))%md;//特殊处理x=0的情况
		SLi l[12],r[12],d[12];
		for (int c=1;c<=k;c++)//算出对应维度的一次函数 
		{
			if(az[c]>=0) {
				l[c]=al[c];
				int t=az[c]+ra[i][c];
				if(ar[c]>t)t=ar[c];
				r[c]=SLi(az[c],t-az[c]);
			} 
			else {
				r[c]=ar[c];
				int t=az[c]+la[i][c];
				if(al[c]<t)t=al[c];
				l[c]=SLi(az[c],t-az[c]);
			}
			d[c]=r[c]-l[c];
		}
		int tc=C[(i+1)%n];
		SLi o;SLi tz=SLi(az[tc],aa[i][tc]);
		if(D[(i+1)%n]==1)o=w[tc]-tz; 
		else o=1-tz;
		SLi zl=1-l[tc],zr=w[tc]-r[tc];//tc这一维度起点的范围
		SQj qj=jiao(More(o,zl),Less(o,zr));//tc这一维度起点是确定的，需要满足条件
		for (int i=1;i<=k;i++) {
			d[i]=w[i]-d[i];
			qj=jiao(qj,More(d[i],1));//方案数>0
		}
		qj=jiao(qj,SQj(1,inf));
		if(qj.l>qj.r)continue;
		DXS ji;ji.clear();ji=ji*SLi(n,i+2);
		for (int c=1;c<=k;c++)//对应维度相乘 
		{
			if(c!=tc)
				ji=ji*d[c];
		}
		ans=(ans+ji.sum(qj.l,qj.r))%md;
	}
	printf("%d",(ans%md+md)%md);
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/888004.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于基于微信小程序的社区订餐系统

基于基于微信小程序的社区订餐系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…
阅读更多...
ElasticSearch备考 -- Async search

ElasticSearch备考 -- Async search

一、题目 通过异步方式查询earthquakes索引下Magnitude大于5的数据 二、思考 正常的查询大家可能会用的多一点&#xff0c;这种异步查询为数据量比较大的查询在后台执行&#xff0c;不用同步等待结果&#xff0c;待执行完成在获取结果。 三、解题 Step 1、准备基础数据 # D…
阅读更多...
Sping源码：三级缓存

Sping源码：三级缓存

目录 一、概念1、三级缓存的作用2、循环依赖的含义 二、代码1、代码下载2、文件功能介绍3、源码分析3.1、找到获取A对象的位置&#xff0c;打断点进行debug操作3.2、一步步找到在A对象中注入B对象的位置3.3、一步步找到B对象注入A对象的位置3.4、往下找到通过三级缓存解决循环依…
阅读更多...
YouTube音视频合并批处理基于 FFmpeg的

YouTube音视频合并批处理基于 FFmpeg的

专门针对YouTube高品质分享处理的&#xff0c;将音频和视频合并。 首先下载ffmpeg.exe网上随便下载。 echo off title YouTube 音视频合并 20241004 echo 作者&#xff1a;xiaoshen echo 网站&#xff1a;http://www.xiaoshen.cn/ echo. set /p audio请将【音频】文件拖拽到此…
阅读更多...
六、Java 基础语法（下）

六、Java 基础语法（下）

一、变量 1、变量的定义与使用 变量就是内存中的存储空间&#xff0c;空间中存储着经常发生改变的数据变量定义格式&#xff1a; 数据类型 变量名 数据值使用时根据变量名使用举例如下&#xff0c;上面是代码&#xff0c;下面是输出 2、变量的注意事项 变量名不允许重复…
阅读更多...
Vue入门-指令学习-v-show和v-if

Vue入门-指令学习-v-show和v-if

v-show&#xff1a; 作用&#xff1a;控制元素的显示隐藏 语法&#xff1a;v-show"表达式" 表达式值true显示&#xff0c;false隐藏 v-if 作用&#xff1a;控制元素的显示隐藏&#xff08;条件渲染&#xff09; 语法&#xff1a; vif"表达式" 表达式tr…
阅读更多...
字节跳动收购Oladance耳机：强化音频技术，加速VR/AR生态布局

字节跳动收购Oladance耳机：强化音频技术，加速VR/AR生态布局

字节跳动收购Oladance耳机&#xff1a;加码VR/AR领域布局 近日&#xff0c;字节跳动宣布已完成对开放式耳机品牌Oladance的收购&#xff0c;实现了对该品牌的100%控股。这一收购标志着字节跳动在AI硬件领域的进一步扩展和深化&#xff0c;特别是对其VR/AR领域布局的重要加码。 …
阅读更多...
STM32使用Keil5 在运行过程中不复位进入调试模式

STM32使用Keil5 在运行过程中不复位进入调试模式

一、选择Options for Target进入设置 二、选择所使用的调试器&#xff0c;这里以ST-Link为例。取消勾选Load Application at Startup 可以在进入调试模式的时候不会从新加载程序&#xff01;从而不破坏现场 三、点击Setting进入 四、取消勾选Reset after Connect 使得调试器连接…
阅读更多...
DotNetty ChannelRead接收数据为null

DotNetty ChannelRead接收数据为null

问题&#xff1a;C#使用Dotnetty和Java netty服务器通讯&#xff0c;结果能正确发送数据到服务器&#xff0c;却始终接收不到服务器返回的数据。 解决&#xff1a;一定一定要注意服务器和客户端使用的编码一定要完全一样才行 我先前在客户端添加了StringDecoder,服务器却没有…
阅读更多...
malloc源码分析之 ----- 你想要啥chunk

malloc源码分析之 ----- 你想要啥chunk

文章目录 malloc源码分析之 ----- 你想要啥chunktcachefastbinsmall binunsorted binbin处理top malloc源码分析之 ----- 你想要啥chunk tcache malloc源码&#xff0c;这里以glibc-2.29为例&#xff1a; void * __libc_malloc (size_t bytes) {mstate ar_ptr;void *victim;vo…
阅读更多...
Windows安装Linux子系统报错：WslRegisterDistribution failed with error: 0x8007019e

Windows安装Linux子系统报错：WslRegisterDistribution failed with error: 0x8007019e

WslRegisterDistribution failed with error: 0x8007019e 报错截图如下图&#xff1a; 该处是由于没有安装Linux内核&#xff0c;因此需要安装。可前往官网查看详情&#xff1a;https://aka.ms/wslinstall 需要解决该问题&#xff0c;可参照官网方法&#xff08;我没试过官网…
阅读更多...
【优选算法之队列+宽搜/优先级队列】No.14--- 经典队列+宽搜/优先级队列算法

【优选算法之队列+宽搜/优先级队列】No.14--- 经典队列+宽搜/优先级队列算法

文章目录 前言一、队列宽搜示例&#xff1a;1.1 N 叉树的层序遍历1.2 ⼆叉树的锯⻮形层序遍历1.3 ⼆叉树最⼤宽度1.4 在每个树⾏中找最⼤值 二、优先级队列&#xff08;堆&#xff09;示例&#xff1a;2.1 最后⼀块⽯头的重量2.2 数据流中的第 K ⼤元素2.3 前 K 个⾼频单词2.4 …
阅读更多...
Android车载——VehicleHal初始化（Android 11）

Android车载——VehicleHal初始化（Android 11）

1 概述 VehicleHal是AOSP中车辆服务相关的hal层服务。它主要定义了与汽车硬件交互的标准化接口和属性管理&#xff0c;是一个独立的进程。 2 进程启动 VehicleHal相关代码在源码树中的hardware/interfaces/automotive目录下 首先看下Android.bp文件&#xff1a; cc_binary …
阅读更多...
Maven的生命周期与依赖作用域介绍

Maven的生命周期与依赖作用域介绍

说明&#xff1a;本文介绍Maven的生命周期&#xff0c;以及在pom.xml文件中每个依赖&#xff08;dependency标签内&#xff09;scope标签的内容。 Maven生命周期 在IDEA项目中&#xff0c;右侧边栏&#xff0c;点Maven&#xff0c;可以看到以下生命周期。 其中&#xff0c; c…
阅读更多...
Spring MVC 常用注解

Spring MVC 常用注解

目录 基础概念 常用注解介绍 基础概念 1、MVC &#xff1a;代表一种软件架构设计思想&#xff0c;通俗的理解&#xff1a;客户端发送请求到后台服务器的Controller(C)&#xff0c;控制器调用Model(M)来处理业务逻辑&#xff0c;处理完成后&#xff0c;返回处理后的数据到Vie…
阅读更多...
Deformable Transformer论文笔记

Deformable Transformer论文笔记

原文链接 [2010.04159] Deformable DETR: Deformable Transformers for End-to-End Object Detection (arxiv.org)https://arxiv.org/abs/2010.04159 原文笔记 What 作者结合了可变形卷积的稀疏空间采样和 Transformer 的关系建模能力的优点。提出了Deformable Detr Defor…
阅读更多...
文心一言 VS 讯飞星火 VS chatgpt （359）-- 算法导论24.3 1题

文心一言 VS 讯飞星火 VS chatgpt （359）-- 算法导论24.3 1题

一、在图 24-2上运行Dijkstra算法&#xff0c;第一次使用结点 s s s作为源结点&#xff0c;第二次使用结点 z z z作为源结点。以类似于图 24-6 的风格&#xff0c;给出每次while循环后的 d d d值和 π π π值&#xff0c;以及集合 S S S中的所有结点。如果要写代码&#xff0c…
阅读更多...
CSRF | GET 型 CSRF 漏洞攻击

CSRF | GET 型 CSRF 漏洞攻击

关注这个漏洞的其他相关笔记&#xff1a;CSRF 漏洞 - 学习手册-CSDN博客 0x01&#xff1a;GET 型 CSRF 漏洞攻击 —— 理论篇 GET 型 CSRF 漏洞是指攻击者通过构造恶意的 HTTP GET 请求&#xff0c;利用用户的登录状态&#xff0c;在用户不知情的情况下&#xff0c;诱使浏览器…
阅读更多...
PCIe配置篇（1）——如何进行配置操作（一）

PCIe配置篇（1）——如何进行配置操作（一）

一、功能的唯一标识——BDF 首先我们简单回顾一下总线&#xff08;Bus&#xff09;、设备&#xff08;Device&#xff09;、功能&#xff08;Function&#xff09;这几个概念&#xff1a; 功能&#xff08;function&#xff09;&#xff1a;是PCI设备中独立的功能单元&#xff…
阅读更多...
【GitHub】上传文件到GitHub

【GitHub】上传文件到GitHub

参考视频&#xff1a;手把手教你在github上传文件_哔哩哔哩_bilibili 1.找到文件夹右键&#xff0c;选择open git bash here 2.完成指令 git initgit add *git commit -m "first commit"3.打开该文件夹&#xff0c;打开隐藏文件.git/config 编辑输入邮箱和GitHub用…
阅读更多...
最新文章

Copyright @ 2022~2023