RT，线段树维护矩乘wa...

（我的超长代码一定会有人来看的）

#include<bits/stdc++.h>
#define re register
#define N 201001
#define MAX 2001
#define inf 1e18
using namespace std; 
typedef long long ll;
typedef double db;
const ll mod=998244353;
inline void read(re ll &ret)
{
	ret=0;re char c=getchar();re bool pd=false;
	while(!isdigit(c)){pd|=c=='-';c=getchar();}
	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();};
	ret=pd?-ret:ret;
	return;
}
ll k,p,n,s[N],m,z[N],num;
namespace subtask
{
	ll v[N],x,f[N];
	inline void solve()
	{
		if(n==1)
		{
			puts("0");
			return;
		}
		for(re int i=0;i<N;i++)
		v[i]=-inf;
		for(re int i=0;i<n;i++)
			read(s[i]);
		read(m);
		for(re int i=1;i<=m;i++)
		{
			read(x);
			if(x>=N)
			{
				re ll tmp;
				read(tmp);
				continue;
			}
			read(v[x]);
		}
		f[0]=0,f[1]=1;
		for(re int i=2;i<=k;i++)
		{
			re ll tmp1=s[(i-1)%n],tmp2=s[(i-2)%n];
			if(v[i-1]!=-inf)
				tmp1=v[i-1];
			if(v[i-2]!=-inf)
				tmp2=v[i-2];
			f[i]=tmp1*f[i-1]%p+tmp2*f[i-2]%p;
			f[i]%=p;
		}
		printf("%lld\n",f[k]);
		return;
	}
}
struct matrix
{
	ll a[3][3],x,y;
}c,val,b[N],ans;
inline matrix operator *(re matrix a,re matrix b)
{
	memset(c.a,0,sizeof(c.a));
	c.x=a.x,c.y=b.y;
	for(re int i=1;i<=c.x;i++)
		for(re int j=1;j<=c.y;j++)
			for(re int k=1;k<=a.y;k++)
				c.a[i][j]+=a.a[i][k]*b.a[k][j]%p,c.a[i][j]%=p;
	return c;
}
struct node
{
	ll l,r,mid;
	matrix val;
}seg[N<<2];
inline void pushup(re ll pos)
{
	seg[pos].val=seg[pos<<1|1].val*seg[pos<<1].val;
	return;
}
inline void build(re ll pos,re ll l,re ll r)
{
	seg[pos].l=l;
	seg[pos].r=r;
	seg[pos].mid=l+r>>1;
	if(l==r)
		seg[pos].val=b[l];
	else
	{
		build(pos<<1,l,seg[pos].mid);
		build(pos<<1|1,seg[pos].mid+1,r);
		pushup(pos);
	}
	return;
}
inline void upgrade(re ll pos,re ll x,re matrix num)
{
	if(seg[pos].l==seg[pos].r&&seg[pos].l==x)
	{
		seg[pos].val=num;
		return;
	}
	else if(seg[pos].l>x||seg[pos].r<x)
		return;
	upgrade(pos<<1,x,num);
	upgrade(pos<<1|1,x,num);
	pushup(pos);
	return;
}
struct change
{
	ll pos,num;
	inline friend bool operator <(re change x,re change y)
	{
		return x.pos<y.pos;
	}
}a[N];
inline matrix qpow(re matrix a,re ll b)
{
	b--;
	re matrix ret=a;
	while(b)
	{
		if(b&1)
			ret=ret*a;
		b>>=1;
		a=a*a;
	}
	return ret;
}
signed main()
{
	read(k);
	read(p);
	read(n);
	if(k<=100000)
	{
		subtask::solve();
		exit(0);
	}
	for(re int i=0;i<n;i++)
		read(s[i]);
	read(m);
	re matrix ret;
	ret.a[1][1]=0,ret.a[1][2]=1,ret.a[2][1]=s[0],ret.a[2][2]=s[1];
	ret.x=ret.y=2;
	s[n]=s[0];
	b[0]=ret;
	re matrix tmp;
	for(re int i=1;i<n;i++)
	{
		tmp.a[1][1]=0,tmp.a[1][2]=1,tmp.a[2][1]=s[i],tmp.a[2][2]=s[i+1];
		tmp.x=tmp.y=2;
		b[i]=tmp;
		ret=tmp*ret;
	}
	build(1,0,n-1);
	for(re int i=1;i<=m;i++)
	{
		read(a[i].pos);
		read(a[i].num);
	}
	sort(a+1,a+m+1);
	re ll now=1;
	memcpy(z,s,sizeof(z));
	while(!(a[now].pos/n))
	{
		num=1;
		z[a[now].pos%n]=a[now].num;
		now++;
	}
	for(re int i=1;i<now;i++)
	{
		tmp.a[2][1]=z[(a[i].pos-1+n)%n],tmp.a[2][2]=z[a[i].pos%n];
		if(a[i].pos%n-1>=0)
			upgrade(1,(a[i].pos-1+n)%n,tmp);
		if(i!=now-1||(a[i+1].pos&&a[i+1].pos!=a[i].pos+1))
			tmp.a[2][1]=z[a[i].pos%n],tmp.a[2][2]=z[(a[i].pos+1)%n];
		else
			tmp.a[2][1]=z[a[i].pos%n],tmp.a[2][2]=a[i+1].num;
		upgrade(1,a[i].pos%n,tmp);
	}
	re matrix f;
	f.x=2;
	f.y=1;
	f.a[1][1]=0;
	f.a[2][1]=1;
	ans=seg[1].val;
	for(re int i=1;i<now;i++)
	{
		z[a[i].pos%n]=s[a[i].pos%n];
		tmp.a[2][1]=s[(a[i].pos-1+n)%n],tmp.a[2][2]=s[a[i].pos%n];
		upgrade(1,(a[i].pos-1+n)%n,tmp);
		tmp.a[2][1]=s[a[i].pos%n],tmp.a[2][2]=s[(a[i].pos+1)%n];
		upgrade(1,a[i].pos%n,tmp);
	}
	re matrix temp=ans*f;
	for(re int i=now;i<=m;)
	{
		re ll ss=a[i].pos/n;
		if(ss-a[i-1].pos/n>1)
			ans=qpow(seg[1].val,ss-a[i-1].pos/n-1)*ans;
		if(ss>=k/n)
			break;
		num++;
		now=i;
		re ll from=now;
		while(a[now].pos/n==ss)
		{
			z[a[now].pos%n]=a[now].num;
			now++;
		}
		for(re int j=from;j<now;j++)
		{
			if(j!=from||a[j-1].pos!=a[j].pos-1)
				tmp.a[2][1]=z[(a[j].pos-1+n)%n],tmp.a[2][2]=z[a[j].pos%n];
			else
				tmp.a[2][1]=a[j-1].num,tmp.a[2][2]=z[a[j].pos%n];
			if(a[j].pos%n-1>=0)
				upgrade(1,(a[j].pos-1+n)%n,tmp);
			if(j!=now-1||a[j+1].pos!=a[j].pos+1)
				tmp.a[2][1]=z[a[j].pos%n],tmp.a[2][2]=z[(a[j].pos+1)%n];
			else
				tmp.a[2][1]=z[a[j].pos%n],tmp.a[2][2]=a[j+1].num;
			upgrade(1,a[j].pos%n,tmp);
		}
		ans=seg[1].val*ans;
		for(re int j=from;j<now;j++)
		{
			z[a[j].pos%n]=s[a[j].pos%n];
			tmp.a[2][1]=s[(a[j].pos-1+n)%n],tmp.a[2][2]=s[a[j].pos%n];
			upgrade(1,(a[j].pos-1+n)%n,tmp);
			tmp.a[2][1]=s[a[j].pos%n],tmp.a[2][2]=s[(a[j].pos+1)%n];
			upgrade(1,a[j].pos%n,tmp);
		}
		i=now;
	}
	re ll end=k/n-1-a[m].pos/n;
	if(end)
		ans=qpow(seg[1].val,end)*ans;
	ans=ans*f;
	re ll res1=ans.a[1][1],res2=ans.a[2][1];
	if(!(k%n))
		printf("%lld\n",res1);
	else if(k%n==1)
		printf("%lld\n",res2);
	else
	{
		memcpy(z,s,sizeof(z));
		for(re int i=now;i<=m;i++)
			z[a[i].pos%n]=a[i].num;
		for(re int i=2;i<=k%n;i++)
		{
			re ll ff=res2;
			res2=(res2*z[i-1]%p+res1*z[(i-2+n)%n]%p)%p;
			res1=ff;
		}
		printf("%lld\n",res2);
	}
	exit(0);
}