Code:
struct coefficient
{
int k;
int b;
coefficient( int i, int ii ): k( i ), b( ii ) {}
coefficient(): k( 0 ), b( 0 ) {}
};
coefficient operator*( int a, const coefficient& coef )
{
coefficient temp = coef;
temp.k *= a;
temp.b *= a;
return temp;
}
coefficient operator*( const coefficient& coef, int a )
{
coefficient temp = coef;
temp.k *= a;
temp.b *= a;
return temp;
}
coefficient operator-( const coefficient& lhs, const coefficient& rhs )
{
coefficient temp = lhs;
temp.k -= rhs.k;
temp.b -= rhs.b;
return temp;
}
coefficient operator+( const coefficient& lhs, const coefficient& rhs )
{
coefficient temp = lhs;
temp.k += rhs.k;
temp.b += rhs.b;
return temp;
}
void run( std::vector<int>& result )
{
// X[0] = 1X[0]+0
coefficient last_coef( 1, 0 );
// X[1] = 2X[0]-101
coefficient current_coef( 2, -101 );
// X[i+1] = 2X[i] - X[i-1]
for ( int i = 2; i < 100; i++ )
{
coefficient temp_coef = current_coef * 2 - last_coef;
last_coef = current_coef;
current_coef = temp_coef;
}
// X[99] = current_coef.k*X[0] + current_coef.b;
// X[98] = last_coef.k*X[0] + last_coef.b;
// X[98] = 2X[99];
// 2current_coef-last_coef = 0;
// X[0] = ??
coefficient result_coef = current_coef * 2 - last_coef;
int X0 = -result_coef.b / result_coef.k;
int X1 = 2 * X0 - 101;
result.clear();
result.resize( 100 );
result[0] = X0;
result[1] = X1;
for ( i = 2; i < 100; i++ )
{
result[i] = 2 * result[i-1] - result[i-2];
}
}