skyscrapers/Skyscrapers_artur.java

  1 import java.util.Scanner;
  2 
  3 public class Skyscrapers_artur {
  4 
  5   static final int MAXN = 5010;
  6   static final int mod = 1000000007;
  7   static final long[][] c = new long[MAXN][MAXN];
  8   static final long[][] s = new long[MAXN][MAXN];
  9 
 10   public static void main(String[] args) {
 11     Scanner in = new Scanner(System.in);
 12 
 13     // Combinations: Pascal triangle
 14     c[0][0] = 1;
 15     for (int i = 1; i < c.length; i++)
 16       for (int j = 0; j <= i; j++)
 17         c[i][j] = ((j > 0 ? c[i - 1][j - 1] : 0) + c[i - 1][j]) % mod;
 18 
 19     while (true) {
 20       int n = in.nextInt();
 21       int a = in.nextInt();
 22       int b = in.nextInt();
 23 
 24       if (n == 0 && a == 0 && b == 0)
 25         break;
 26 
 27       // Unsigned Stirling numbers of the first kind
 28       // s[i][j] == # of permutations of length i, with j buildings visible from left (or right)
 29       s[0][0] = 1;
 30       for (int i = 1; i <= n; i++)
 31         for (int j = 1; j <= i; j++)
 32           /*
 33            * For [i][j] consider the placement of the shortest building: 1. At the leftmost position -- it is always visible,
 34            * thus compute for [i-1][j-1] 2. Anywhere else, except the leftmost position -- it is never visible, thus compute for
 35            * [i-1][j]
 36            */
 37           s[i][j] = (s[i - 1][j - 1] + (i - 1) * s[i - 1][j]) % mod;
 38 
 39       long result = 0;
 40       for (int k = 0; k < n; k++)
 41         /*
 42          * All valid permutations are counted: 1. Place the tallest building at position k. 2. Choose k buildings that form a
 43          * configuration with A visible buildings from the left. 3. Rest of the buildings form B visible buildings from the
 44          * right.
 45          */
 46         result = (result + c[n - 1][k] * s[k][a - 1] % mod * s[n - k - 1][b - 1]) % mod;
 47       System.out.println(result);
 48     }
 49   }
 50 }