Advertisement
Guest User

Untitled

a guest
May 6th, 2012
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.22 KB | None | 0 0
  1.     static final long MOD = 1000000007;
  2.  
  3.     public void solve () throws Exception {
  4.         int n = nextInt();
  5.         int t = nextInt();
  6.        
  7.         long c [][] = new long [n + 1][n + 1];
  8.         for (int i = 0; i <= n; i++) {
  9.             c[i][0] = c[i][i] = 1;
  10.             for (int j = 1; j < i; j++) {
  11.                 c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  12.             }
  13.         }
  14.        
  15.         int a [] = new int [n];
  16.         int count [] = new int [5001];
  17.         for (int i = 0; i < n; i++) {
  18.             a [i] = nextInt();
  19.             count [a[i]]++;
  20.         }
  21.         int p = a[nextInt() - 1];
  22.         int pos = nextInt();
  23.        
  24.         int pleft = pos - 1;
  25.         int pright = t - pos;
  26.        
  27.         int countLeft = 0;
  28.         int countRight = 0;
  29.        
  30.         for (int i = 0; i < p; i++) {
  31.             countLeft += count [i];
  32.         }
  33.         for (int i = p + 1; i <= 5000; i++) {
  34.             countRight += count [i];
  35.         }
  36.        
  37.         long answer = 0;
  38.        
  39.         for (int left = 0; left <= count [p] - 1; left++) {
  40.             for (int right = 0; right + left <= count [p] - 1 && left <= pleft && right <= pright; right++) {
  41.                 long cur = c[count[p] - 1][left + right];
  42.                 long la = (c[countLeft][pleft - left]) % MOD;
  43.                 cur = (cur * la) % MOD;
  44.                 long ra = (c[countRight][pright - right]) % MOD;
  45.                 cur = (cur * ra) % MOD;
  46.                 answer = (answer + cur) % MOD;
  47.             }
  48.         }
  49.        
  50.         out.println(answer);
  51.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement