NC20320. [SDOI2008]递归数列
描述
输入描述
由四行组成。第一行是一个自然数k。第二行包含k个自然数b1, b2,...,bk。第三行包含k个自然数c1, c2,...,ck。第四行包含三个自然数m, n, p。
输出描述
仅包含一行：一个正整数，表示(am + am+1 + am+2 + ... + an) mod p的值。
示例1
输入:
2 1 1 1 1 2 10 1000003
输出:
142
C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 456K, 提交时间: 2023-05-30 14:40:26
#include<iostream>
#include<algorithm>
#include<numeric>//accumulate(be,en,0)
#include<cstring>//find("string"),rfind("string"),s.find(string,begin)!=s.npos
#include<string>//to_string(value)
#include<cstdio>
#include<cmath>
#include<vector>//res.erase(unique(res.begin(), res.end()), res.end())
#include<queue>//priority_queue(big) /priority_queue<int, vector<int>, greater<int>> q(small)
#include<stack>
#include<map>//unordered_map
#include<set>//iterator,insert(),erase(),lower(>=)/upper_bound(>)(value)/find()return end()
#define int long long
#define PII pair<int,int>
#define f first
#define s second
using namespace std;
const int inf=0x3f3f3f3f,K=17;
int b[K],c[K],k,d[K];
int m,n,mod;
void mul(int f[K],int a[K][K])
{
int c[K];
memset(c,0,sizeof c);
for(int i=0;i<k+1;i++){
for(int j=0;j<k+1;j++){
c[i]=(c[i]+f[j]*a[i][j]%mod)%mod;
}
}
memcpy(f,c,sizeof c);
}
void mulself(int a[K][K])
{
int c[K][K];
memset(c,0,sizeof c);
for(int i=0;i<k+1;i++){
for(int j=0;j<k+1;j++){
for(int w=0;w<k+1;w++){
c[i][j]=(c[i][j]+a[i][w]*a[w][j]%mod)%mod;
}
}
}
memcpy(a,c,sizeof c);
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0);
cin>>k;
for(int i=1;i<=k;i++) cin>>b[i];
for(int i=1;i<=k;i++) cin>>c[i];
cin>>m>>n>>mod;
for(int i=1;i<=k;i++) d[i]=(d[i-1]+b[i])%mod;
int a[K][K];
memset(a,0,sizeof a);
a[0][0]=1;
for(int i=1;i<=k;i++){
a[0][i]=c[i];
a[1][i]=c[i];
}
for(int i=2;i<=k;i++){
a[i][i-1]=1;
}
// for(int i=0;i<=k;i++){
// for(int j=0;j<=k;j++){
// cout<<a[i][j]<<' ';
// }
// cout<<'\n';
// }
int f[K];
f[0]=d[k];
for(int i=1;i<=k;i++){
f[i]=b[k-i+1];
}
int x1=0;
if(m-1<=k){
x1=d[m-1];
}else{
int q=m-1-k;
while(q){
if(q&1) mul(f,a);
q>>=1;
mulself(a);
}
x1=f[0];
}
memset(a,0,sizeof a);
a[0][0]=1;
for(int i=1;i<=k;i++){
a[0][i]=c[i];
a[1][i]=c[i];
}
for(int i=2;i<=k;i++){
a[i][i-1]=1;
}
f[0]=d[k];
for(int i=1;i<=k;i++){
f[i]=b[k-i+1];
}
// cout<<"x1:"<<x1<<'\n';
// for(int i=0;i<=k;i++){
// for(int j=0;j<=k;j++){
// cout<<a[i][j]<<' ';
// }
// cout<<'\n';
// }
// for(int i=0;i<=k;i++) cout<<f[i]<<' ';
int x2=0;
if(n<=k){
x2=d[n];
}else{
int q=n-k;
while(q){
if(q&1) mul(f,a);
q>>=1;
mulself(a);
}
x2=f[0];
}
cout<<(x2-x1+mod)%mod;
}
C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 504K, 提交时间: 2019-11-11 20:48:47
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
x *= flag;
}
#if __cplusplus >= 201103l
template<typename T, typename... V>
void read(T &x, V&... v) { read(x), read(v...); }
#endif
const int _ = 19;
int k, b[_], c[_], sl, sr, P; ll m, n;
inline void pls(int &a, int b) { a += b; if(a >= P) a -= P; }
struct matrix {
int a[_][_];
void clear() { memset(a, 0, sizeof a); }
int *operator [] (int x) { return a[x]; }
matrix operator * (matrix b) {
matrix c; c.clear();
for(int i = 1; i <= ::k + 1; ++i)
for(int j = 1; j <= ::k + 1; ++j)
for(int k = 1; k <= ::k + 1; ++k)
pls(c[i][k], 1ll * a[i][j] * b[j][k] % P);
return c;
}
} S, T;
void pow(ll b) {
for(; b; b >>= 1, T = T * T)
if(b & 1) S = S * T;
}
void init() {
S.clear(), T.clear();
for(int i = 1; i < k; ++i) T[i + 1][i] = 1;
T[k + 1][k + 1] = 1;
for(int i = 1; i <= k; ++i) {
T[i][k] = T[i][k + 1] = c[k - i + 1];
pls(S[1][k + 1], b[i]), S[1][i] = b[i];
}
}
int main () {
read(k);
for(int i = 1; i <= k; ++i) read(b[i]);
for(int i = 1; i <= k; ++i) read(c[i]);
read(m, n, P);
if(m - 1 <= k)
for(int i = 1; i <= m - 1; ++i) pls(sl, b[i]);
else init(), pow(m - 1 - k), sl = S[1][k + 1];
if(n <= k)
for(int i = 1; i <= n; ++i) pls(sr, b[i]);
else init(), pow(n - k), sr = S[1][k + 1];
printf("%d\n", (sr + P - sl) % P);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 376K, 提交时间: 2019-12-19 16:05:25
#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
int K,p;LL l,r,sum,ans;
struct node{
int m[17][17];
inline node operator* (const node x) const{
rgt node c;rll res;
rint i,j,k;
for(i=0;i<=K;++i) {
for(j=0;j<=K;++j) {
res=0;
for(k=0;k<=K;k++)
res+=(LL)m[i][k]*x.m[k][j]%p;
c.m[i][j]=res%p;
}
}return c;
}
}E,A,res,a;
inline int Pow(rll b) {
res=E,a=A;
for(;b;b>>=1,a=a*a)
if(b&1) res=res*a;
return res.m[0][0];
}
int main()
{
rint i;scanf("%d",&K);
for(i=1;i<=K;i++) scanf("%d",&E.m[0][K-i+1]),sum+=E.m[0][K-i+1];
for(i=1;i<=K;i++) scanf("%d",&A.m[i][1]);A.m[0][0]=A.m[1][0]=1;
for(i=2;i<=K;i++) A.m[i-1][i]=1;
scanf("%lld%lld%d",&l,&r,&p),--l;E.m[0][0]=(sum-E.m[0][1])%p;
if(l<K) for(i=1;i<=l;i++) ans-=E.m[0][K-i+1];
else ans=-Pow(l-K+1);
if(r<K) for(i=1;i<=r;i++) ans+=E.m[0][K-i+1];
else ans+=Pow(r-K+1);
printf("%d",(ans%p+p)%p);
return 0;
}