CF575A. Fibonotci

题目大意

题解

矩乘线段树

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define ll long long
//#define file
using namespace std;

struct type{ll x;int s;} b[50001];
int a[50001],n,m,i,j,k,l,mod;
ll K,ls,Ls;
struct mat{ll a[2][2];void clear() {memset(a,0,sizeof(a));}} A,I,s,tr[200001],ans;
bool cmp(type a,type b) {return a.x<b.x;}
mat operator * (mat a,mat b)
{
	static mat c;
	int i,j,k;
	fo(i,0,1)
	{
		fo(j,0,1)
		{
			c.a[i][j]=0;
			fo(k,0,1)
			add(c.a[i][j],a.a[i][k]*b.a[k][j]);
		}
	}
	return c;
}
mat qpower(mat a,ll b) {mat ans;ans=I; while (b) {if (b&1) ans=ans*a;a=a*a;b>>=1;} return ans;}
void mt(int t,int l,int r)
{
	int mid=(l+r)/2;
	tr[t]=I;
	if (l==r) return;
	mt(t*2,l,mid),mt(t*2+1,mid+1,r);
}
void change(int t,int l,int r,int x,mat s)
{
	int mid=(l+r)/2;
	tr[t]=tr[t]*s;
	if (l==r) return;
	
	if (x<=mid) change(t*2,l,mid,x,s);
	else change(t*2+1,mid+1,r,x,s);
}
mat find(int t,int l,int r,int x,int y)
{
	int mid=(l+r)/2;
	mat ans=I;
	if (x<=l && r<=y) return tr[t];
	
	if (x<=mid) ans=ans*find(t*2,l,mid,x,y);
	if (mid<y) ans=ans*find(t*2+1,mid+1,r,x,y);
	return ans;
}
mat js(ll x,ll y)
{
	if (x==y) return I;
	return find(1,1,n,x+2,y+1);
}
mat Js(ll x,ll y)
{
	if (x==y) return I;
	if (x/n==y/n) return js(x%n,y%n);
	return ((js(x%n,n-1)*qpower(tr[1],y/n-x/n-1))*A)*js(0,y%n);
}

int main()
{
	#ifdef file
	freopen("CF575A.in","r",stdin);
	#endif
	I.a[0][0]=I.a[1][1]=1;
	
	scanf("%lld%d",&K,&mod);
	scanf("%d",&n);
	fo(i,0,n-1) scanf("%d",&a[i]);
	mt(1,1,n);
	fo(i,0,n-1)
	{
		s.a[0][0]=0,s.a[0][1]=a[(i+n+n-2)%n];
		s.a[1][0]=1,s.a[1][1]=a[(i+n-1)%n];
		if (!i) A=s;
		change(1,1,n,i+1,s);
	}
	ans.a[0][0]=0,ans.a[0][1]=1;
	if (!K) {printf("0
");return 0;}
	
	scanf("%d",&m);
	fo(i,1,m) scanf("%lld%d",&b[i].x,&b[i].s);
	sort(b+1,b+m+1,cmp);
	
	ans=I,ls=1,i=1;
	while (i<=m && b[i].x<=K && ls<K)
	{
		ans=ans*Js(ls,b[i].x),ls=b[i].x,Ls=a[(b[i].x+n-1)%n];
		while (i<=m && b[i].x<=K && ls==b[i].x && ls<K)
		{
			s.a[0][0]=0,s.a[0][1]=Ls;
			s.a[1][0]=1,s.a[1][1]=b[i].s;
			ans=ans*s;
			Ls=b[i].s,++i,++ls;
		}
		if (ls<K)
		{
			s.a[0][0]=0,s.a[0][1]=b[i-1].s;
			s.a[1][0]=1,s.a[1][1]=a[ls%n];
			ans=ans*s,++ls;
		}
		else break;
	}
	if (ls<K) ans=ans*Js(ls,K);
	printf("%lld
",ans.a[1][1]%mod);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}