JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions SPOJ SEQ
 SPOJ SEQ | Reply Hi Guys, i am trying to solve https://www.spoj.pl/problems/SEQ/ i came with a O(NK) solution, below one ```#include typedef long long int LL; int main() { int t,i,k,j; LL a[11]; LL c[11]; LL n; LL n2; LL temp; LL mod=1000000000ll; scanf("%d",&t); while(t--) { scanf("%d",&k); for(i=1;i<=k;i++) scanf("%lli",&a[i]); for(i=1;i<=k;i++) scanf("%lli",&c[i]); scanf("%lli",&n); n2=(long long int)k; if(n<=k) { printf("%lli\n",a[n]); } else { while(n2
 Re: SPOJ SEQ (response to post by javasoul) | Reply The problem is not the code, but the idea of simulating each step. Write a matrix A such that A * v_i = v_(i+1), where v_i is the vector (a_i, a_(i-1), ..., a_(i-k+1)), then use exponentiation by squaring to calculate A^(n-k); finally, compute A^(n-k) * v_k to get the desired answer in O(k^3 log n) time.Edit: The Wikipedia article to which I linked is needlessly complicated. Reading the "Underlying idea" section should be enough (and perhaps the "Example implementations" section if you want examples).
 Re: SPOJ SEQ (response to post by MauricioC) | Reply Hi MauricioC,``` Here i am trying to understand it, Take this example 3 1 2 3 4 5 6 6 Here n=6,k=3,a1=1,a2=2,a3=3,a4=28,a5=139,a6=714(ans) so to take AXv_1=v_2; so A={4, 5, 6} &v_1=[3,2,1] so v_2={12, 10, 6} =28? so i have the correct A? then A^(6-3)=A^3 = [64,125,216] v_k =? ????? ```sorry, i didnt get it.. -;)
 Re: SPOJ SEQ (response to post by javasoul) | Reply I think you have some misconceptions - check this tutorial, maybe it will clear the things for you a little bit:http://www.topcoder.com/tc?module=Static&d1=features&d2=010408Before that you should probably read a bit about matrices and matrix multiplication.
 Re: SPOJ SEQ (response to post by darko_aleksic) | Reply ok. Let me try it.. Thanks.yes i did a wrong mat mul, a[3X1] & v1[1X3] = v2[3X3] is not required should be a[1X3] & v1[3X1] = v2[1X1]??i am reading.. thanks..
 Re: SPOJ SEQ (response to post by javasoul) | Reply A must be [KxK] in order to satisfy A * v_i = v_i+1 (where vectors are kx1)
 Re: SPOJ SEQ (response to post by darko_aleksic) | Reply Thanks for the help.Here is my program:```#include #define end scanf("%s",read)   typedef long long int LL; LL mat[11][11]; LL mat2[11][11]; LL tempmat[11][11];   LL v0[11]; LL mod=1000000000ll; int k;   //multiply the matrix with the base vector v0 void mulwithbase() { int a,b,c; LL temp[11]; for(a=0;a1ll){ if(p%2ll==1ll) { monce=1; p--; }else monce=0; if(p%2ll==0ll) { for(a=0;a
 Re: SPOJ SEQ (response to post by javasoul) | Reply Your algorithm seems to exponentiate to the wrong power. For example, is your power is (in base 2) 110000, you start with A, then square it (A^2), square it again (A^4), square it again (A^8), then again (A^16), then square and multiply by A (A^33) then stop, but 33 is not 110000. That is mostly because you're thinking of bits in the wrong order. You're actually exponentiating to 100001, which is a number obtained by reversing all but the most significant digit of the intended exponent.
 Re: SPOJ SEQ (response to post by MauricioC) | Reply Thank you MauricioC. Thank you so much. Got AC!!!Thanks to darko_aleksic also.
 Re: SPOJ SEQ (response to post by javasoul) | Reply hey there I am also trying to implement the same logic. Still getting WA.long long mat[11][11];long long res[11][11];long long previous[11]={0};//code to raise a matrix res to the power nvoid mulmat(long long res[11][11],int n){if(n==1)return ;if(n==2){long long temp[11][11];for(int i=0;i<11;i++)for(int j=0;j<11;j++)temp[i][j]=0;for(int i=0;i<11;i++)for(int j=0;j<11;j++){for(int k=0;k<11;k++){temp[i][j]+=(res[i][k]*res[k][j])%mod;temp[i][j]%=mod;}}for(int i=0;i<11;i++)for(int j=0;j<11;j++)res[i][j]=temp[i][j];return ; }if(n%2==0){ mulmat(res,n/2);mulmat(res,2);} else{mulmat(res,(n-1)/2);mulmat(res,2);long long temp[11][11];for(int i=0;i<11;i++)for(int j=0;j<11;j++)temp[i][j]=0;for(int i=0;i<11;i++)for(int j=0;j<11;j++){for(int k=0;k<11;k++){temp[i][j]+=(res[i][k]*mat[k][j])%mod;temp[i][j]%=mod;}}for(int i=0;i<11;i++)for(int j=0;j<11;j++)res[i][j]=temp[i][j];return; } }int main(){int n;cin>>n;while(n--){ for(int i=1;i<11;i++){previous[i]=0;for(int j=0;j<11;j++){if(j+1!=i){res[i][j]=0;mat[i][j]=0;}else{res[i][j]=1;mat[i][j]=1;}}}previous[0]=0;int order;cin>>order;int loo=order;while(loo){ cin>>previous[loo-1];loo--; }loo=order;while(loo){ cin>>mat[0][order-loo];res[0][order-loo]=mat[0][order-loo];loo--; }int nth;cin>>nth;long long ans=0;if(nth<=order){cout<<<
 Re: SPOJ SEQ (response to post by javasoul) | Reply whats the concept behind using temp=011 ..??actually i'm new this is my first dp prob..!!
 Re: SPOJ SEQ (response to post by javasoul) | Reply SIR CAN U PLZ ELABOTATE //tempmat[a][b]=(tempmat[a][b]+((mat2[a][c]*mat2[c][b])%mod))%mod; WHY USING 10^9+011
 Re: SPOJ SEQ (response to post by javasoul) | Reply Can you please find why my code is giving WA.#include using namespace std;int test, k, n;int b[10], c[10];static long long int matrix[10][10];long long int res[10][10];long long int MOD = 1000000000ll;//This is a customized matrix multiplication, result is stored again in matrix avoid matrixMultiplication(long long int a[][10], long long int b[][10]){ long long int c[k][k]; for(int i = 0; i < k; ++i){ for(int j = 0; j < k; ++j){ c[i][j] = 0; for(int l = 0; l < k; ++l) c[i][j] = (c[i][j] + (a[i][l] * b[l][j]) % MOD) % MOD; } } for(int i = 0; i < k; ++i) for(int j = 0; j < k; ++j) a[i][j] = c[i][j];}//Here base matrix is "matrix" and power is "n"void matrixExponentiation(){ while(n > 0){ if(n & 1) matrixMultiplication(res, matrix); //res = res * base; matrixMultiplication(matrix, matrix); //base = base * base; n = n / 2; }}long long int compute(){ if(n <= k) return b[n - 1]; n = n - k; matrixExponentiation(); long long int ans = 0; for(int i = 0; i < k; ++i) ans = (ans + (res[0][i] * b[k - i - 1]) % MOD) % MOD; return ans;}int main(){ ios_base::sync_with_stdio(false); for (int i = 1; i < 10; ++i) matrix[i][i - 1] = 1; cin >> test; while(test--){ cin >> k; for(int i = 0; i < k; ++i) cin >> b[i]; for(int i = 0; i < k; ++i){ cin >> c[i]; matrix[0][i] = c[i]; } cin >> n; for(int i = 0; i < k; ++i) for(int j = 0; j < k; ++j) res[i][j] = (i == j); cout << compute() << endl; } return 0;}
 Forums Round Tables External Competitions SPOJ SEQ Previous Thread  |  Next Thread