【题解】递归数列

【题解】递归数列"题目链接"题目大意:给定序列迭代规则,求一段的序列和。特点是要求的序列很长。Solution观察到,由于是求和,我们可以想到前缀和的思想。也就是说,对于求$\sum_{i=

大家好,又见面了,我是你们的朋友全栈君。

题目链接

题目大意:给定序列迭代规则,求一段的序列和。特点是要求的序列很长。

Solution#

观察到,由于是求和,我们可以想到前缀和的思想。也就是说,对于求\(\sum_{i=m}^n a_i\),我们只需要求\(\sum_{i=1}^{m-1}a_i\)\(\sum_{i=1}^n a_i\),然后做差即可。

注意到\(n,m\)的范围,我们线性递推是不现实的。于是我们可以考虑矩阵快速幂。

考虑维护\(k+1\)个值。维护\(k\)个序列基本值,以及一个求和值。我们根据\(k\)个信息推出下一个信息。观察到\(k\)的范围,所以是可以做的。

构造矩阵比较简单。注意一下\(c\)的位置,是倒序的。

由于我们一次维护的是\(k\)个值,所以,如果我们要求\(pos\),则我们求出转移矩阵的\(pos-k\)次方就可以求出。

两次矩阵快速幂加上前缀和思想,这题做完了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
ll n,m,p,s,ss[16],Ans,sss;
inline ll add(ll x,ll y){return (x%p+y%p)%p;}
inline ll mul(ll x,ll y){return (x%p*y%p)%p;}
inline ll del(ll x,ll y){return x-y<0?x+p-y:x-y;}
int k,b[16],c[16];
struct Mat{
	ll A[17][17];
	Mat(){memset(A,0,sizeof(A));}
	Mat operator*(const Mat&B)const{
		Mat res;
		for(int i=1;i<=k+1;++i)
			for(int j=1;j<=k+1;++j)
				for(int l=1;l<=k+1;++l)
					res.A[i][j]=add(res.A[i][j],mul(A[i][l],B.A[l][j]));
		return res;
	}
}w,s1,A2,A1;
inline void Init(Mat &x){for(int i=1;i<=k+1;++i)x.A[i][i]=1;}
Mat qpow(Mat st,ll b){
	Mat c;
	Init(c);
	while(b){
		if(b&1)c=c*st;
		b>>=1;st=st*st;
	}
	return c*s1;
}
signed main(){
	scanf("%lld",&k);
	for(int i=1;i<=k;++i)scanf("%lld",&b[i]);
	for(int i=1;i<=k;++i)scanf("%lld",&c[i]);
	scanf("%lld%lld%lld",&m,&n,&p);
	for(int i=1;i<=k;++i)ss[i]=add(ss[i-1],(ll)b[i]);
	for(int i=1;i<=k;++i)s1.A[i][1]=b[i];
	s1.A[k+1][1]=ss[k];
	for(int i=1;i<k;++i)w.A[i][i+1]=1;
	for(int i=1;i<=k;++i)w.A[k][i]=c[k-i+1],w.A[k+1][i]=c[k-i+1];
	w.A[k+1][k+1]=1;
	if(m-1>=k)A1=qpow(w,m-1-k);
	else A1.A[k+1][1]=ss[m-1];
	if(n>=k)A2=qpow(w,n-k);
	else A2.A[k+1][1]=ss[n];
	Ans=del(A2.A[k+1][1],A1.A[k+1][1]);
	printf("%lld\n",Ans);
	return 0;
} 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155600.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • webdriver.Firefox_web driver

    webdriver.Firefox_web driver1、下载geckodriver(是Firefox的官方webdriver)地址:https://github.com/mozilla/geckodriver/releases2、下载需要的driver后,解压,将geckodriver.exe放置在与python3.exe相同的路径下。demo调试一下:火狐浏览器可以正常执行脚本,pass!…

  • navicat15.0.22注册激活码【在线注册码/序列号/破解码】

    navicat15.0.22注册激活码【在线注册码/序列号/破解码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • axios实现跨域三种方法_react antdesign

    axios实现跨域三种方法_react antdesign1.启动springboot后端,提供接口2.在config文件夹下创建proxy.tx文件,如果存在,在dev中添加axios环境代理,例如在我的demo中添加了/asd映射到http://localhost:8889/***在生产环境代理是无法生效的,所以这里没有生产环境的配置*Theagentcannottakeeffectintheproductionenvironment*sothereisnoconfigurationoftheproduc

  • html精灵图跟img标签,css精灵图怎么使用?

    html精灵图跟img标签,css精灵图怎么使用?什么是css精灵图(sprite)?css精灵图怎么使用?下面本篇文章就来给大家介绍一下css精灵图的使用。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。在了解精灵图怎么使用前,我们要先知道什么是精灵图。只有先知道什么是精灵图,了解精灵图的原理了,我们才可是说使用精灵图。什么是css精灵图(sprite)?css精灵图(sprite)直译为“CSS精灵”,也被称为通常被解释为“C…

  • gis可视化的方法_gis可视化分析

    gis可视化的方法_gis可视化分析前言从去年开始无脑接触Cesium三维GIS可视化,入坑之后一直到到现在,其实已经写了多个项目了,中间也遇到了很多坑点,很早就想分享其中所获了,只是觉得不太专业而且没有太多时间,…

  • Java两整数相除向上取整

    Java两整数相除向上取整前言:Java中两个整数相除,如果不能整除,默认是向下取整的。例如:11除以3的结果是3。然而,某些情况下(eg.把11个糖果,每3个分一堆,不足三个也分成一堆,可以分几堆?),我们需要向上取整,这样的情况该如果处理呢?方式一:添加三目运算符逻辑代码x/y+(x%y!=0?1:0);这种方法逻辑上很简单,如果x可以整除y,就将x/y的结果加0,不能整除y就将x/y的结果加1。方式二:使用ceil函数(int)Math.ceil((double.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号