C++

Forum

 
spoj SEQ problem runtime error

surfersss (46)
im trying to solve spoj problem SEQ - Recursive Sequence , https://www.spoj.com/problems/SEQ/ i compile and get right answer using g++ in terminal, but when i submit it , it produce runtime error (SIGSEGV) , why this happen? i really want to know the cause of error and i want to know why i need to do mod also inside the matrix?
https://ideone.com/naYBuD
stderr
copy

free(): double free detected in tcache 2




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
#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;
cout<<res<<endl;

}

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;

      fib(n,b1,c2,k);
      
   }


}


i guess this is because i change the array size every testcase?
Repeater (3046)

1
2
 
#define rep(i,n) for (int i = 1; i <= n; i++)
typedef long long int ll;


STOP MAKING YOUR CODE DELIBERATELY HARD TO READ
Enoizat (1343)
Following Repeater’s advice, this is a perhaps more readable version of surfersss code.

Function fib() is patently wrong, since it misses a final return instruction.
I’ve changed int y=c1.back(); into long long y { c1.back() };, and few other marginal details.

If given the test input, the program outputs the expected result:
8
714
257599514


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
#include <iostream>
#include <vector>


using matrix = std::vector< std::vector<long long> >;
constexpr long long mod = 1000000000;   // 1,000,000,000


int fib( int N, const std::vector<long long>& b1, std::vector<long long> c1, int k );
matrix mul( const matrix& lhs, const matrix& rhs, int k );
// Beware! pow() is already defined in the standard library:
matrix pow( const matrix& base, int e, int k );


int main()
{
    int cas;
    std::cin >> cas;

    for ( int i { 1 }, k; i <= cas; ++i) {
        std::cin >> k;
        std::vector<long long> b1 ( k + 1 );
        std::vector<long long> c2 ( k + 1 );

        for ( int j { 1 }, b; j <= k; ++j ) {
            std::cin >> b;
            b1[j] = b;
        }

        for( int o { 1 }, c; o <= k; ++o ) {
            std::cin >> c;
            c2[o] = c;
        }

        int n;
        std::cin >> n;
        fib( n, b1, c2, k );
    }
}


matrix mul( const matrix& lhs, const matrix& rhs, int k )
{
    matrix result( k + 1, std::vector<long long>(k + 1) );
    for ( int i { 1 }; i <= k; ++i ) {
        for ( int j { 1 }; j <= k; ++j ) {
            for ( int m { 1 }; m <= k; ++m ) {
                result[i][j] = ( result[i][j] + ( lhs[i][m] * rhs[m][j] ) ) % mod;
            }
        }
    }
    return result;
}


matrix pow( const matrix& base, int e, int k )
{
    if ( e == 1 ) {
        return base;
    }

    if ( e % 2 ) {
        return mul( base,
                    pow( base, e - 1, k ),
                    k );
    }

    matrix result = pow( base, e/2, k ); 
    return mul( result, result, k );
}


int fib( int N, const std::vector<long long>& b1, std::vector<long long> c1, int k )
{
    std::vector<long long> result ( k + 1 );

    for (int i { 1 }; i <= k; ++i) {
        result[i] = b1[i];
    }

    matrix tmp( k + 1, std::vector<long long>( k + 1 ) );

    for ( int y { 1 }; y <= k; ++y ) {
        for ( int u { 1 }; u <= k; ++u ) {
            if ( y + 1 == u ) {
                tmp[y][u] = 1;
            }
        }
    }

    for ( int i { 1 }; i <= k; ++i ) {
        long long y { c1.back() };
        c1.pop_back();
        tmp[k][i] = y;
    }

    if ( N < k ) {
        std::cout << b1[N] << '\n';
        return 0;
    }

    tmp = pow ( tmp, N - 1, k );

    long long res {};
    for ( int i { 1 }; i <=k ; ++i ) {
        res = ( res + tmp[1][i] * result[i] ) % mod;
    }
    std::cout << res << '\n';
}

surfersss (46)
@Enoizat thankyou for the revise my code to become readable, after fix some edge case , i manage to get accepted thanks!!!
Topic archived. No new replies allowed.