bzoj3231[sdoi2008] 귀속수열

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)modp의 값을 나타내는 정수입니다.

HINT

100%의 테스트 데이터에 대해: 1<=k<=151<=m<=n<=10^18 모든 테스트 데이터에 대해: 0<=b1,b2,...bk,c1,c2,...,ck<=10^91<=p<=10^8
행렬 빠른 멱 누드 문제.우리는 단지 매트릭스를 구성할 때 접두사 하나를 더 유지하면 된다. 이렇게 두 번 빠른 멱을 사용한 다음에 결과를 나쁘게 하면 매트릭스를 구성할 수 있다.
⎡⎣⎢⎢⎢⎢⎢⎢C110...1C201...0C300...0...............CK00...0⎤⎦⎥⎥⎥⎥⎥⎥×⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢AkAk−1Ak−2...A1sumk−1⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥
주의 특판
n, m코드

    #include 
#include 
#include 
#define maxn 18
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline void read(int& x)
{   char c=getchar();x=0;int y=1;
    while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    x*=y;
}
typedef long long ll;
ll sum[maxn],n,m;
int C[maxn],K,mod;
struct matrix
{   int s[maxn][maxn];
    matrix(){mem(s,0);}
    inline void init(){mem(s,0);for(int i=0;ithis->s[i][i]=1;}
    inline int* operator [](int x){return s[x];}
    inline friend matrix operator *(matrix x,matrix y)
    {   matrix z;
        for(int i=0;ifor(int j=0;jfor(int k=0;k1ll*z[i][j]+1ll*x[i][k]*y[k][j]%mod)%mod;
        return z;
    }
}A,ans,F,__backup,__rebackup;
int main()
{   read(K);
    for(int i=1;i<=K;++i) read(F[K-i][0]);
    for(int i=1;i<=K;++i) read(C[i]);
    scanf("%lld%lld%d",&m,&n,&mod);
    for(int i=1;i<=K;++i) F[K-i][0]%=mod,sum[i]=(sum[i-1]+F[K-i][0])%mod;
    sum[K]=(sum[K]-F[0][0]+mod)%mod;++K;
    F[K-1][0]=sum[K-1];
    for(int i=0;iif(i!=K-1) A[0][i]=C[i+1];
    for(int i=1,k=K-1;i1]=1;
    A[K-1][0]=1,A[K-1][K-1]=1;__backup=A;
    ll y=m-K+1;ans.init();
    if(y>=0){for(;y;y>>=1,A=A*A) if(y&1) ans=ans*A;__rebackup=ans*F;}
    else __rebackup[K-1][0]=sum[m-1];
    y=n-K+1;A=__backup;ans.init();
    if(y>=0){for(;y;y>>=1,A=A*A) if(y&1) ans=ans*A;F=ans*F;}
    else F[K-1][0]=sum[n];
    printf("%d",((ll)F[K-1][0]+F[0][0]-__rebackup[K-1][0]+mod)%mod);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CF1117D Magic Gems dp 매트릭스 곱셈

[ d p [ n − m − 1 ] d p [ n − m ] . d p [ n − 1 ] ] ∗\begin{bmatrix} dp[n-m-1] & dp[n-m] & ... & dp[n-1]\end{bmatrix}* [...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

bzoj3231[sdoi2008] 귀속수열

Description

Input

Output

HINT

좋은 웹페이지 즐겨찾기