Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- public class Permutant {
- public int mod = 1000000007;
- public int counthis(int[] a) {
- int n = a.length;
- int m = 0;
- for (int x : a) m += x;
- long[][] comb = new long[m+1][m+1];
- comb[0][0] = 1;
- for (int i = 1; i <= m; i++) {
- comb[i][0] = 1;
- for (int j = 1; j <= i; j++) {
- comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod;
- }
- }
- long[] fact = new long[m+1];
- fact[0] = 1;
- for (int i = 1; i <= m; i++) {
- fact[i] = fact[i-1] * i % mod;
- }
- long ret = 0;
- for (int last = 0; last < n; last++) {
- // dp[i] = number of ways given there are i balls to the right of the first occurrence of a ball of the last color.
- long[] dp = new long[m+1];
- // can freely arrange all the balls of the last color
- dp[a[last] - 1] = fact[a[last]];
- int cursum = a[last]-1;
- for (int i = 0; i < n; i++) {
- if (last == i) continue;
- long[] next = new long[m+1];
- // need to put at least one ball to the left
- for (int left = 1; left <= a[i]; left++) {
- int right = a[i] - left;
- for (int curright = 0; curright <= cursum && curright+right <= m; curright++) {
- int curleft = cursum - curright;
- // since the first occurrence of each color needs to be label 1, this is fact[a[i]-1] instead of fact[a[i]].
- long y = fact[a[i]-1] * comb[curleft+left][left] % mod * comb[curright+right][right] % mod;
- next[curright+right] = (next[curright+right] + dp[curright] * y) % mod;
- }
- }
- dp = next;
- cursum += a[i];
- }
- for (int i = 0; i <= m; i++)
- ret = (ret + dp[i]) % mod;
- }
- return (int)ret;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement