skyscrapers/skyscrapers_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to The n Days of Christmas
  8  * 
  9  * @author vanb
 10  */
 11 public class skyscrapers_vanb
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     public static final long MOD = 1000000007L;
 17     public static final int MAX = 5000;
 18     
 19     public long memo[][] = new long[MAX+1][MAX+1];
 20     public long cmemo[][] = new long[MAX+1][MAX+1];
 21     public long fact[] = new long[MAX+1];
 22     
 23     /**
 24      * Combinations. This is a little different - it's combinations of a+b things taken a at a time.
 25      * 
 26      * @param a A number
 27      * @param b Another number
 28      * @return Combinations of a+b things taken a at a time
 29      */
 30     public long combs( int a, int b )
 31     {
 32         if( cmemo[a][b]==0 )
 33         {
 34             long result = combs( a-1, b ) + combs( a, b-1 );            
 35             cmemo[a][b] = cmemo[b][a] = result % MOD;
 36         }
 37         
 38         //System.out.println(  combs(  + a +  ,  + b +  )=  + cmemo[a][b] );
 39         return cmemo[a][b];
 40     }
 41     
 42     /**
 43      * The number of ways to arrange n things so that k of them 
 44      * can be seen from one side.
 45      * 
 46      * @param n Size of permutation
 47      * @param k Number of things that can be seen
 48      * @return The number of ways as specified above
 49      */
 50     public long ways( int n, int k )
 51     {
 52         if( memo[n][k]<0L )
 53         {
 54             long result = 0L;
 55             result += (n-1)*ways( n-1, k );
 56             result %= MOD;
 57             result += ways( n-1, k-1 );
 58             result %= MOD;
 59 //            for( int i=k-1; i<n; i++ )
 60 //            {
 61 //                long w = ways( i, k-1 );
 62 //                w *= fact[n-i-1];
 63 //                w %= MOD;
 64 //                w *= combs( i, n-i-1 );
 65 //                w %= MOD;
 66 //                result += w; 
 67 //                result %= MOD;
 68 //            }
 69             memo[n][k] = result;
 70         }
 71         //System.out.println(  ways(  + n +  ,  + k +  )=  + memo[n][k] );
 72         return memo[n][k];
 73     }
 74      
 75     /**
 76      * Driver.
 77      * @throws Exception
 78      */
 79     public void doit() throws Exception
 80     {
 81         sc = new Scanner( new File( "skyscrapers.judge" ) );
 82         ps = new PrintStream( new FileOutputStream( "skyscrapers.solution" ) );
 83         
 84         fact[0] = 1L;
 85         fact[1] = 1L;
 86         for( int i=2; i<=MAX; i++ )
 87         {
 88             fact[i] = i*fact[i-1] % MOD;   
 89         }
 90         
 91         for( int i=0; i<=MAX; i++ )
 92         {
 93             Arrays.fill( memo[i], -1 );
 94             memo[i][i] = 1L;
 95             memo[i][0] = 0L;
 96             if( i>0 ) memo[i][1] = fact[i-1];
 97             cmemo[i][0] = cmemo[0][i] = 1L;
 98         }
 99         cmemo[0][0] = memo[0][0] = 1L;
100         
101         for(;;)
102         {
103             int n = sc.nextInt();
104             int left = sc.nextInt();
105             int right = sc.nextInt();
106             if( n==0 ) break;
107             
108             //System.out.println(  n=  + n +  , left=  + left +  , right=  + right );
109             
110             long allways = 0L;
111             for( int i=left-1; i<=n-right; i++ )
112             {
113                 long result = ways( i, left-1 );
114                 result *= ways( n-i-1, right-1 );
115                 result %= MOD;
116                 result *= combs( i, n-i-1 );
117                 result %= MOD;
118                 
119                 allways += result;
120                 allways %= MOD;
121             }
122             
123             ps.println( allways );
124             System.out.println( allways );
125         }
126     }
127     
128     /**
129      * @param args
130      */
131     public static void main( String[] args ) throws Exception
132     {
133         long start = System.currentTimeMillis();
134         new skyscrapers_vanb().doit();        
135         System.out.println( System.currentTimeMillis() - start );
136     }   
137 }