bzoj3907: 网格

http://www.cnblogs.com/Tunix/p/4354348.html
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 #include<iostream>
  6 
  7 using namespace std;
  8 
  9 void setIO(const string& s) {
 10     freopen((s + ".in").c_str(), "r", stdin);
 11     freopen((s + ".out").c_str(), "w", stdout);
 12 }
 13 template<typename Q> Q read(Q& x) {
 14     static char c, f;
 15     for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;
 16     for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
 17     if(f) x = -x;
 18     return x;
 19 }
 20 template<typename Q> Q read() {
 21     static Q x; read(x); return x;
 22 }
 23 
 24 struct LL {
 25     const static int N = 5000, base = 10;
 26     int da[N], n;
 27     
 28     void init(int n) {
 29         this->n = n;
 30         memset(da, 0, sizeof(da[0]) * n);
 31     }
 32     
 33     void clear_zero() {
 34         while(n && !da[n-1]) n--;
 35     }
 36     
 37     LL operator * (const int &rhs) const {
 38         static LL c;
 39         c.init(n + 5);
 40         for(int i = 0; i < c.n; i++) {
 41             if(i < n) c.da[i] += da[i] * rhs;
 42             c.da[i+1] += c.da[i] / base;
 43             c.da[i] %= base;
 44         }
 45         c.clear_zero();
 46         return c;
 47     }
 48     
 49     void print() const {
 50         if(n == 0) putchar('0');
 51         else for(int i = n - 1; i >= 0; i--) {
 52             putchar(da[i] + '0');
 53         }
 54     }
 55 }res;
 56 
 57 const int LIM = 10000, N = 5000;
 58 
 59 int mi[LIM+1], primes[N], tot;
 60 bool flag[LIM+1];
 61 
 62 void get_primes(int n) {
 63     for(int i = 2; i <= n; i++) {
 64         if(!flag[i]) primes[tot] = i, mi[i] = tot++;
 65         for(int j = 0; j < tot; j++) {
 66             int k = primes[j];
 67             if(i * k > n) break;
 68             flag[i * k] = 1;
 69             if(i % k == 0) break;
 70         }
 71     }
 72 }
 73 
 74 int num[N];
 75 
 76 void add(int x, int sign) {
 77     for(int i = 0, k; k = primes[i], k * k <= x; i++) {
 78         while(x % k == 0) {
 79             num[i] += sign;
 80             x /= k;
 81         }
 82     }
 83     if(x ^ 1) num[mi[x]] += sign;
 84 }
 85 
 86 int main() {
 87 #ifdef DEBUG
 88     freopen("in.txt", "r", stdin);
 89     freopen("out.txt", "w", stdout);
 90 #endif
 91     
 92     int n, m;
 93     scanf("%d%d", &n, &m);
 94     get_primes(n + m);
 95     for(int i = n + m; i > m; i--) add(i, 1);
 96     for(int i = n; i > 1; i--) add(i, -1);
 97     add(n - m + 1, 1), add(n + 1, -1);
 98     
 99     res.da[0] = res.n = 1;
100     
101     for(int i = 0; i < tot; i++) {
102         while(num[i]--) res = res * primes[i];
103     }
104     
105     res.print(); puts("");
106     
107     return 0;
108 }
View Code