SHARE
TWEET

CyclesNumber

a guest Mar 29th, 2016 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class CyclesNumber {
  4.   static final int N = 100_000;
  5.   static final int M = 305;
  6.   static final int T = 300;
  7.   static final int mod = 1_000_000_007;
  8.  
  9.   int add(int x, int y) {
  10.     x += y;
  11.     if (x >= mod)
  12.       x -= mod;
  13.     return x;
  14.   }
  15.  
  16.   int mul(int x, int y) {
  17.     return (int) (((long) x * (long) y) % mod);
  18.   }
  19.  
  20.   boolean order(int l, int m, int r) {
  21.     return l <= m && m <= r;
  22.   }
  23.  
  24.   int pow(int x, int to) {
  25.     int ans = 1;
  26.     for (int i = 0; i < to; ++i)
  27.       ans = mul(ans, x);
  28.     return ans;
  29.   }
  30.  
  31.   public String checkData(int[] n, int[] m) {
  32.     if (n.length != m.length)
  33.       return "n and m must contain the same nubmer of elements.";
  34.  
  35.     if (!order(1, n.length, T))
  36.       return "n must contain between 1 and 300 integers, inclusive.";
  37.  
  38.     for (int x : n)
  39.       if (!order(1, x, N))
  40.         return "Each element of n must be between 1 and 100,000, inclusive.";
  41.  
  42.     for (int x : m)
  43.       if (!order(0, x, 300))
  44.         return "Each element of m must be between 0 and 300, inclusive.";
  45.  
  46.     return "";
  47.   }
  48.  
  49.  
  50.   public int[] getExpectation(int[] n, int[] m) {
  51.     int[] ans = new int[n.length];
  52.     int[] ans2 = new int[n.length];
  53.  
  54.     int[] c = new int[M + 1];
  55.     c[1] = 1;
  56.  
  57.     int[][] s = new int[M + 1][M + 1];
  58.     s[0][0] = 1;
  59.  
  60.     for (int i = 1; i <= M; ++i)
  61.       for (int j = 1; j <= M; ++j)
  62.         s[i][j] = add(s[i - 1][j - 1], mul(s[i - 1][j], j));
  63.  
  64.     int[] f = new int[M + 1];
  65.     f[0] = 1;
  66.     for (int i = 1; i <= M; ++i)
  67.       f[i] = mul(i, f[i - 1]);
  68.  
  69.  
  70.     for (int i = 1; i <= N; ++i) {
  71.  
  72.       /*
  73.       for (int k = 0; k < n.length; ++k)
  74.         if (n[k] == i) {
  75.           for (int j = 1; j <= n[k]; ++j)
  76.             ans2[k] = add(ans2[k], mul(c[j], pow(j, m[k])));
  77.         }
  78.       */
  79.  
  80.       for (int j = M; j >= 1; --j)
  81.         c[j] = add(c[j - 1], mul(c[j], i));
  82.  
  83.       for (int k = 0; k < n.length; ++k)
  84.         if (n[k] == i) {
  85.           for (int j = 0; j <= m[k]; ++j)
  86.             ans[k] = add(ans[k], mul(mul(f[j], s[m[k]][j]), c[j + 1]));
  87.         }
  88.     }
  89.  
  90.     /*
  91.     for (int k = 0; k < n.length; ++k)
  92.       if (ans[k] != ans2[k]) {
  93.         System.out.print("Wrong: ");
  94.         System.out.println(ans[k]);
  95.         System.out.print("Correct: ");
  96.         System.out.print(ans2[k]);
  97.         System.out.println();
  98.       }
  99.     */
  100.    
  101.     return ans;
  102.   }
  103.  
  104.   public static void main(String[] args) {
  105.     CyclesNumber solver = new CyclesNumber();
  106.     int[] n = {3, 20, 30};
  107.     int[] m = {0, 20, 30};
  108.     for (int x : solver.getExpectation(n, m))
  109.       System.out.println(x);
  110.   }
  111.  
  112. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top