problem : https://www.spoj.com/problems/SEQ/
https://ideone.com/vaVWBo
this produce right output for the testcase, but wrong answer , why is that?
i guess i miss some testcase?
#include <vector>
#include <iostream>
#define rep(i,n) for (int i = 1; i <= n; i++)
using namespace std;
typedef long long int ll;
typedef vector<vector<ll> > matrix;
const ll mod = 1000000000;
matrix mul(matrix A,matrix B,int k){
matrix c(k+1,vector<ll>(k+1));
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
for(int l=1;l<=k;l++){
c[i][j]=(c[i][j]+(A[i][l]*B[l][j]))%mod;
}
}
}
return c;
}
matrix pow(matrix A,int p,int k){
if(p==1)
return A;
if(p%2){
return mul(A,pow(A,p-1,k),k);
}
matrix X=pow(A, p/2,k);
return mul(X,X,k);
}
int fib(int N,vector<ll>b1,vector<ll>c1,int k){
vector<ll>bb(k+1);
rep(i,k){
bb[i]=b1[i];
}
matrix T(k+1,vector<ll>(k+1));
for(int y=1;y<=k;y++){
for(int u=1;u<=k;u++){
if(y+1==u)
T[y][u]=1;
}
}
rep(i,k){
int y=c1.back();
c1.pop_back();
T[k][i]=y;
}
if(N<k){
cout<<b1[N]<<endl;
return 0;
}
T=pow(T,N-1,k);
ll res=0;
for(int i=1;i<=k;i++)
res=(res+T[1][i]*bb[i])%mod;
return res;
}
int main(){
int cas,k,b,c,n;
cin>>cas;
rep(i,cas)
{
cin>>k;
vector<ll>b1(k+1);
vector<ll>c2(k+1);
rep(j,k){
cin>>b;
b1[j]=b;
}
rep(o,k){
cin>>c;
c2[o]=c;
}
cin>>n;
int y= fib(n,b1,c2,k);
if(y!=0)
cout<<y<<endl;
}
}