Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.io.PrintWriter;
- import java.math.BigInteger;
- import java.util.Scanner;
- public class Main {
- public static BigInteger ONE = BigInteger.ONE;
- public static BigInteger ZERO = BigInteger.ZERO;
- public static BigInteger TWO = BigInteger.valueOf(2);
- static class frac{
- BigInteger num , den;
- frac(){ num = den = ZERO;}
- public frac( BigInteger a , BigInteger b ){
- if( b.equals( ZERO ) ) {
- num = ONE;
- den = ZERO;
- } else if( a.equals( ZERO ) ){
- num = ZERO;
- den = ONE;
- }else{
- if( b.compareTo(ZERO) == -1 ){
- a = a.negate();
- b = b.negate();
- }
- BigInteger g = (a.abs()).gcd(b.abs());
- num = a.divide(g) ;
- den = b.divide(g);
- }
- }
- };
- public static boolean Less( frac a , frac b ){
- return ( a.num.multiply( b.den ) ).compareTo( b.num.multiply( a.den ) ) == -1;
- }
- public static boolean Higher( frac a , frac b ){
- return ( a.num.multiply( b.den ) ).compareTo( b.num.multiply( a.den ) ) == 1;
- }
- boolean equals ( frac A , frac B ){ return A.num.equals(B.num) && A.den.equals(B.den);}
- public static frac sum( frac A , frac B ){ return new frac( A.num .multiply( B.den ).add( B.num .multiply( A.den ) ) , A.den.multiply( B.den ) ) ;}
- public static frac resta( frac A , frac B ){ return new frac( A.num .multiply( B.den ).subtract( B.num .multiply( A.den ) ) , A.den.multiply( B.den ) ) ;}
- public static frac mult( frac A , frac B ){ return new frac( A.num.multiply( B.num ) , A.den.multiply( B.den ) ) ;}
- public static frac div( frac A , frac B ){ return new frac( A.num.multiply( B.den ) , A.den.multiply( B.num ) ) ;}
- public static frac abs( frac A ){ return new frac( A.num.abs() , A.den.abs() );}
- public static void invert( frac A[][] , frac B[][] , int n ){
- for( int i = 0 ; i < n ; ++i ){
- int jmax = i ;
- for( int j = i + 1 ; j < n ; ++j )
- if( Higher( abs( A[ j ][ i ] ) , abs( A[ jmax ][ i ] ) ) ) jmax = j;
- for( int j = 0 ; j < n ; ++j ){
- frac temp;
- temp = A[ i ][ j ];
- A[ i ][ j ] = A[ jmax ][ j ];
- A[ jmax ][ j ] = temp;
- temp = B[ i ][ j ];
- B[ i ][ j ] = B[ jmax ][ j ];
- B[ jmax ][ j ] = temp;
- }
- frac tmp = A[ i ][ i ];
- for( int j = 0 ; j < n ; ++j ){
- A[ i ][ j ] = div( A[ i ][ j ] , tmp );
- B[ i ][ j ] = div( B[ i ][ j ] , tmp );
- }
- for( int j = 0 ; j < n ; ++j ){
- if( i == j )continue;
- tmp = A[ j ][ i ];
- for( int k = 0 ; k < n ; ++k ){
- A[ j ][ k ] = resta( A[ j ][ k ] , mult( A[ i ][ k ] , tmp ) );
- B[ j ][ k ] = resta( B[ j ][ k ] , mult( B[ i ][ k ] , tmp ) );
- }
- }
- }
- }
- public static String input = "divide.in";
- public static String output = "divide.out";
- public static void main(String[] args) throws FileNotFoundException {
- Scanner cin = new Scanner( new File(input) );
- int n = cin.nextInt();
- cin.close();
- PrintWriter wt = new PrintWriter(output);
- frac A[][] = new frac[ n + 1 ][ n + 1 ];
- for( int i = 0 ; i <= n ; ++i )
- for( int j = 0 ; j <= n ; ++j ) A[ i ][ j ] = new frac( ONE , ONE );
- frac B[][] = new frac[ n + 1 ][ n + 1 ];
- for( int i = 0 ; i <= n ; ++i )
- for( int j = 0 ; j <= n ; ++j ) B[ i ][ j ] = new frac( ONE , ONE );
- for( int i = 0 ; i <= n ; ++i ) A[ i ][ n ] = new frac( ONE , ONE );
- for( int i = 0 ; i <= n ; ++i )
- for( int j = n - 1 ; j >= 0 ; --j )
- A[ i ][ j ] = mult( new frac( BigInteger.valueOf(i) , ONE ) , A[ i ][ j + 1 ] );
- B[ 0 ][ 0 ] = new frac( ONE , ONE );
- for( int i = 1 ; i <= n ; ++i ) B[ i ][ 0 ] = mult( new frac( TWO , ONE ) , B[ i - 1 ][ 0 ] );
- invert( A , B , n + 1 );
- wt.println( n );
- for( int i = 0 ; i <= n ; ++i ){
- wt.print( B[ i ][ 0 ].num + "/" + B[ i ][ 0 ].den );
- if( i == n ) wt.println("");
- else wt.print(" ");
- }
- wt.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement