[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
数学苦手……一通推,无法可行……
于是只能想没有办法的办法:打表……

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 typedef long long Long;
 6 
 7 int arr[20];
 8 Long ans = 0;
 9 int n;
10 
11 void dfs(int now,int sum) {
12     if (sum < 0return;
13     if (now == n) {ans ++return;}
14     dfs (now + 1, sum + (1 << arr[now] ));
15     dfs (now + 1, sum - (1 << arr[now] ));
16 }
17 
18 int main() {
19     for (n = 1; n <= 10; n++) {
20         for (int i = 0; i < n; i++) {
21             arr[i] = i;
22         }
23         Long cnt = 0;
24         ans = 0;
25         do {
26              dfs(0,0);           
27              cnt ++;
28         } while (next_permutation(arr,arr + n));
29         printf("%lld ",ans);
30         printf("%lld\n",cnt << n);
31     }
32     return 0;
33 }
输出:
1 2
3 8
15 48
105 384
945 3840
10395 46080
135135 645120
2027025 10321920
34459425 185794560
654729075 3715891200
然后大家都懂了……
 1 import java.util.*;
 2 import java.io.*;
 3 import java.math.BigInteger;
 4 
 5 
 6 class Main {
 7 
 8     BigInteger[] ans1 = new BigInteger [501];
 9     BigInteger[] ans2 = new BigInteger [501];
10     final BigInteger TWO = BigInteger.valueOf(2);
11 
12     void solve() throws Exception {
13         MyReader in = new MyReader();
14         int nn = in.nextInt();
15         ans1[1= BigInteger.ONE;
16         ans2[1= TWO;
17         for (int i = 2; i <= 500; i++) {
18             ans1[i] = ans1[i - 1].multiply(BigInteger.valueOf(i + i - 1));
19             ans2[i] = ans2[i - 1].multiply(BigInteger.valueOf(i)).multiply(TWO);
20             BigInteger gcd = ans1[i].gcd(ans2[i]);
21             ans1[i] = ans1[i].divide(gcd);
22             ans2[i] = ans2[i].divide(gcd);
23         }
24         PrintWriter out = new PrintWriter(System.out);
25         while (nn-- > 0) {
26             int n = in.nextInt();
27             out.print(ans1[n]);
28             out.print("/");
29             out.println(ans2[n]);
30         }
31         out.flush();
32     }
33 
34     public static void main(String args[]) throws Exception {
35         new Main().solve();
36     }
37 
38     void debug(Objectx) {
39         System.out.println(Arrays.deepToString(x));
40     }
41 }
42 
43 class MyReader {
44     BufferedReader br = new BufferedReader (
45             new InputStreamReader (System.in));
46     StringTokenizer in;
47     String next() throws Exception {
48         if (in == null || !in.hasMoreTokens()) {
49             in = new StringTokenizer(br.readLine());
50         }
51         return in.nextToken();
52     }
53     int nextInt() throws Exception {
54         return Integer.parseInt(next());
55     }
56 }
posted on 2011-09-18 20:40 sweetsc 阅读(647) 评论(1)  编辑  收藏

Feedback

# re: 2011ACM北京网络预选赛D题: FXTZ II (BUPT 235) 2011-09-19 01:12 sxj_program
It is not hard to understand that if the n-th power is shot then the game will be over.

If it is shot at the i-th time, the possibility is (n-i)/n* f(i) * 1/(n-i)*1/2, which is 1/(2n)*f(i)

So f(n) = 1/(2n)*sum( f(i) ), 1<=i<n

f(n)*2n = sum( f(i) )
=> f(n)*2n - f(n-1)*2*(n-1) = f(n-1)
=> f(n) = (2n-1)/(2n)*f(n-1) = ... = (2n-1)!! / (2n)!! * f(0), f(0)=1  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: