首页 > 其他分享 >洛谷P5517题解

洛谷P5517题解

时间:2024-07-05 15:20:07浏览次数:18  
标签:frac int 题解 sum P5517 32 洛谷 2i mod

题目解释

现有一数列:\(a_{0}=-3,a_{1}=-6,a_{2}=-12,a_{n}=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n,求T组a_{n}\)mod p 的异或和

题目思路分析

抛开复杂度不谈,这道题可以用矩阵加速(矩阵的快速幂)和通项公式两种方法来做,这两种方法求一个\(a_{n}\)的时间复杂度都是\(log_2(n)\),但矩阵乘法需要更多时间,因此常数略大

总时间复杂度:

矩阵加速:O(\(16Tlog_2n\))
通项公式:O(\(Tlog_2n\))
而本题的T最大范围为[1,5e7],而n的最大可到\(2^{63}-1\),很显然,总时间复杂度的需求为O(n),尽管上述两种做法用快速幂实现都会TLE,但通项公式中的幂的底数固定,可以用光速幂预处理
因此整体思路为:先推通项公式,再用光速幂优化查询

通项公式推导

\(a_{n}=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n\)
\(a_{n}-a_{n-2}=3(a_{n-1}-a_{n-3})+3^n\)
\(设a_{n}-a_{n-2}=b_{n} 得b_{2}=-9\)
\(b_{n}=3b_{n-1}+3^n\)
\(\frac{b_{n}}{3^n}=\frac{b_{n-1}}{3^n-1}+1\)
\(设frac{b_{n}}{3^n}=c_{n} 得c_{2}=-1\)
\(c_{n}=c_{n-1}+1\)
\(c_{n}=c_{0}+n=c_{2}+n-2=-1+n-2=n-3\)
\(b_{n}=(n-3)3^n\)
\(a_{n}-a_{n-2}=(n-3)3^n\)
\(当n为偶数时 a_{n}=a_{0}+\sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i} =-3+\sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i}\)

\(设\sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i}=X\)

\(9X=9sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i}=sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i+2}\)

\(8X=9X-X=sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i+2}-sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i}\)

\(8X=(n-3)3^{(n+2)}+sum_{i=1}^{\frac{n}{2}-1} (2i-3)3^{2i+2}-sum_{i=2}^{\frac{n}{2}} (2i-3)3^{2i}+9\)

\(8X=(n-3)3^{(n+2)}-sum_{i=2}^{\frac{n}{2}} (2i-3-[2(i-1)-3])3^{2i}+9\)

\(8X=(n-3)3^{(n+2)}-sum_{i=2}^{\frac{n}{2}} 2*3^{2i}+9\)

\(8X=(n-3)3^{(n+2)}-\frac{3^(n+2)-3^4}{8}+9\)

\(X=\frac{(4n-13)3^{(n+2)}+117}{32}\)

\(a_{n}=\frac{(4n-13)3^{(n+2)}+117}{32}-3=\frac{(36n-117)3^n+21}{32}\)

\(当n为奇数时 a_{n}=a_{1}+\sum_{i=1}^{\frac{n}{2}} (2i-3)3^{2i}\)

同理\(a_{n}=\frac{(4n-13)3^{(n+2)}+51}{32}=\frac{(36n-117)3^{n}+51}{32}\)

代码实现

由于通项中所有幂的底数均为3,因此可以用光速幂预处理
其实现原理为\(a^{n}=a^{kx+y}=a^{kx}a^y\),分别预处理\(a^{kx}\)和\(a^y\)
具体实施如下

#define Q 32000
//预处理
gsm1[0]=gsm2[0]=1;
for(int i=1;i<=Q;i++)gsm1[i]=1ll*gsm1[i-1]*3%mod;
for(int i=1;i<=Q;i++)gsm2[i]=1ll*gsm2[i-1]*gsm1[Q]%mod;
//调用
int gsm(int n){
	return 1ll*gsm2[n/Q]*gsm1[n%Q]%mod;
} 

由于答案需要取模,除以一个数需改为乘以它的逆元,所以我们可以通过快速幂计算得32在1e9+7下的逆元为281250002(即\(32^{1e9+5} mod 1e9+7\))
而由于有时n过大,我们可以利用\(a^n≡a^{(n-1)mod{p}}(mod{p}))\)来化简
最后,计算时记得乘上1ll,每算一次都要取一次模防止超出long long的范围

AC代码

#include<bits/stdc++.h>
#define mod 1000000007
#define _32 281250002
#define Q 32000
using namespace std;
int gsm1[Q+1],gsm2[Q+1],rst,T;
int gsm(int n){
	return 1ll*gsm2[n/Q]*gsm1[n%Q]%mod;
} 
namespace Mker
{
//  Powered By Kawashiro_Nitori
//  Made In Gensokyo, Nihon
	#include<climits>
	#define ull unsigned long long
	#define uint unsigned int
	ull sd;int op;
	inline void init() {scanf("%llu %d", &sd, &op);}
	inline ull ull_rand()
	{
		sd ^= sd << 43;
		sd ^= sd >> 29;
		sd ^= sd << 34;
		return sd;
	}
	inline ull rand()
	{
		if (op == 0) return ull_rand() % USHRT_MAX + 1;
		if (op == 1) return ull_rand() % UINT_MAX + 1; 
		if (op == 2) return ull_rand();
	}
}
int comput(unsigned long long x){
	if(x&1)return 1ll*(1ll*(36*(x%mod)-117+mod)%mod*gsm(x%(mod-1))+51)%mod*_32%mod;
	return 1ll*(1ll*(36*(x%mod)-117+mod)%mod*gsm(x%(mod-1))+21)%mod*_32%mod;
}
int main(){
	scanf("%d",&T);
	Mker::init();
	gsm1[0]=gsm2[0]=1;
	for(int i=1;i<=Q;i++)gsm1[i]=1ll*gsm1[i-1]*3%mod;
	for(int i=1;i<=Q;i++)gsm2[i]=1ll*gsm2[i-1]*gsm1[Q]%mod;
	while(T--){
		rst^=comput(Mker::rand());
	}
	printf("%d",rst);
}

标签:frac,int,题解,sum,P5517,32,洛谷,2i,mod
From: https://www.cnblogs.com/wanxue/p/18285826

相关文章

  • Kali网卡失效IP不显示问题解决
    因为我的个人习惯,通常为虚拟机配置两个网卡,一个Host-only网卡用于与主机进行通信、一个网络地址转换网卡用于访问网络。然而,在配置Kali主机时,常常遇到网络地址转换网卡断联的现象,导致虚拟机无法正常访问网络。根据先前的经验,问题出在网络配置上。查看/etc/network/interfaces文......
  • [题解]逃离地球
    题意简述有一个星系,共有\(n*m\)个星球,排成\(n\)行\(m\)列。初始星球之间没有道路。接下来给定\(P\)种魔法\(1\),\(Q\)种魔法\(2\):魔法\(1\):第\(i\)种魔法用\(a_i,b_i,c_i\)描述。表示你可以任选星系的一行,在第\(a_i\)和第\(b_i\)个星球之间建立一条航道,消耗\(c_i\)的能量。魔......
  • [题解]P1083 [NOIP2012 提高组] 借教室
    [题解]P1083[NOIP2012提高组]借教室解法\(1\):线段树-\(O((n+m)\logn)\)比较直观的一种做法,但是可能需要卡一下输入(这里没卡也过了,但要注意输入是\(10^6\)级的,为了保险一定要加)。#include<bits/stdc++.h>#definelc(x<<1)#definerc((x<<1)|1)#defineintlonglong......
  • SP15620 POSTERIN - Postering 题解
    题目传送门前置知识单调栈解法容易有每个建筑物的宽度对答案没有影响,故可以将其宽度均看作\(1\)。在最优策略下,对于每张海报,其高度一定等于所覆盖的楼的最小高度。单调栈维护最小高度,记录额外海报数量(与先前高度相等时可以少用一张海报)。最终,用总张数\(n\)减去额外海报......
  • reverse 题解
    reverse题解注意到本题数据范围较大且与数位有关,考虑数位DP。我们发现对于每个询问,我们可以将第一个条件拆开之后差分,可以先从后往前DP,预处理出末尾满足$L\le\operatorname{reverse}(n)\leR$的个数,之后使用试填法填数即可。具体地,在预处理时,处理出顶到上界,顶到下界......
  • 洛谷 P1020 [NOIP1999 提高组] 导弹拦截
    题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所......
  • 洛谷 P1011 [NOIP1998 提高组] 车站
    题目描述火车从始发站(称为第 1 站)开出,在始发站上车的人数为 a,然后到达第 2 站,在第 2 站有人上、下车,但上、下车的人数相同,因此在第 2 站开出时(即在到达第 3 站之前)车上的人数保持为 a 人。从第 3 站起(包括第 3 站)上、下车的人数有一定规律:上车的人数都是前两......
  • Kithara常见问题解答
    目录通用问题我的内核驱动程序已经签名了吗?是否可以在打开驱动程序时防止显示介绍窗口?Windows7仍然支持吗?错误0x10142422(`KSERROR_CANNOT_START_KERNEL`)在`KS_openDriver`时出现?错误10145241(KSERROR_CANNOT_START_KERNEL)在KS_openDriver时出现?可以在C#应用程......
  • javascript url 传递参数中文乱码问题解决方案
    在JavaScript中,传递URL参数时,如果参数包含中文字符,可能会出现乱码问题。解决这一问题可以使用encodeURIComponent和decodeURIComponent函数。这些函数会对URL参数进行编码和解码,确保特殊字符(包括中文字符)能够被正确传递和解析。以下是一个完整的解决方案示例: 1.......
  • [JLU] 数据结构与算法上机题解思路分享-
    前言首先,请务必自己尽全力尝试实现题目,直接看成品代码,思维就被拘束了,也很容易被查重。这里只是思路解析的博客,代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)第三次上机A手撕BST分数50作者朱允刚单位吉林大学对一棵初始为空的二叉查找树(Binary......