题目描述

Description

一个由自然数组成的数列按下式定义：
对于i <= k：ai = bi
对于i > k: ai = c1ai-1 + c2ai-2 + ... + ckai-k
其中bj和 cj （1<=j<=k）是给定的自然数。写一个程序，给定自然数m <= n, 计算am + am+1 + am+2 + ... + an, 并输出它除以给定自然数p的余数的值。

Input

由四行组成。
第一行是一个自然数k。
第二行包含k个自然数b1, b2,...,bk。
第三行包含k个自然数c1, c2,...,ck。
第四行包含三个自然数m, n, p。

Output

仅包含一行：一个正整数，表示(am + am+1 + am+2 + ... + an) mod p的值。

Sample Input

2
1 1
1 1
2 10 1000003

Sample Output

142

HINT

对于100%的测试数据：
1<= k<=15
1 <= m <= n <= 10^18

题目分析

很明显矩阵乘法

差分一下[m,n]=[1,n]-[1,m-1] 最后注意一下单独计算m,n小于k的部分

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int k;
long long n,m,p;
long long a[20],b[20][20],c[20],f[20];
void init()
{
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    for(int i=1;i<=k;i++) a[i]=f[i];
    for(int i=1;i<=k;i++) a[k+1]=(a[k+1]+f[i])%p;
    for(int i=1;i<=k-1;i++) b[i+1][i]=1;
    for(int i=1;i<=k;i++) b[k-i+1][k]=c[i];
    for(int i=1;i<=k;i++) b[k-i+1][k+1]=c[i];
    b[k+1][k+1]=1;
}
long long e[20],d[20][20];
void doit()
{
    memset(e,0,sizeof e);
    for(int i=1;i<=k+1;i++)
        for(int j=1;j<=k+1;j++)
            e[i]=(e[i]+a[j]*b[j][i])%p;
    for(int i=1;i<=k+1;i++) a[i]=e[i]%p;
}
void work()
{
    memset(d,0,sizeof d);
    for(int i=1;i<=k+1;i++)
        for(int j=1;j<=k+1;j++)
            for(int z=1;z<=k+1;z++)
                d[i][j]=(d[i][j]+b[i][z]*b[z][j])%p;
    for(int i=1;i<=k+1;i++)
        for(int j=1;j<=k+1;j++)
            b[i][j]=d[i][j]%p;
}
void ksm(long long y)
{
    while(y)
    {
        if(y&1) doit();
        y>>=1;
        work();
    }
}
long long nans,mans;
int main()
{
    scanf("%d",&k);
    for(int i=1;i<=k;i++) scanf("%lld",&f[i]);
    for(int i=1;i<=k;i++) scanf("%lld",&c[i]);
    scanf("%lld%lld%lld",&m,&n,&p);
    if(m-1<=k) for(long long i=1;i<m;i++) mans=(mans+a[i])%p;
    if(n<=k) for(long long i=1;i<=n;i++) nans=(nans+a[i])%p;
    if(m-1>k)
        init(),ksm(m-1-k),mans=a[k+1]%p;
    if(n>k)
        init(),ksm(n-k),nans=a[k+1]%p;
    long long ans=nans-mans;
    while(ans<0) ans+=p;
    printf("%lld",(ans)%p);
    return 0;
}