• API
• FAQ
• Tools
• Archive
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.

Top