bzoj3907: 网格

http://www.cnblogs.com/Tunix/p/4354348.html

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 void setIO(const string& s) {

     freopen((s + ".in").c_str(), "r", stdin);

     freopen((s + ".out").c_str(), "w", stdout);

 }

 template<typename Q> Q read(Q& x) {

     static char c, f;

     for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;

     for(x = ; isdigit(c); c = getchar()) x = x *  + c - '';

     if(f) x = -x;

     return x;

 }

 template<typename Q> Q read() {

     static Q x; read(x); return x;

 }

 struct LL {

     const static int N = , base = ;

     int da[N], n;

     void init(int n) {

         this->n = n;

         memset(da, , sizeof(da[]) * n);

     }

     void clear_zero() {

         while(n && !da[n-]) n--;

     }

     LL operator * (const int &rhs) const {

         static LL c;

         c.init(n + );

         for(int i = ; i < c.n; i++) {

             if(i < n) c.da[i] += da[i] * rhs;

             c.da[i+] += c.da[i] / base;

             c.da[i] %= base;

         }

         c.clear_zero();

         return c;

     }

     void print() const {

         if(n == ) putchar('');

         else for(int i = n - ; i >= ; i--) {

             putchar(da[i] + '');

         }

     }

 }res;

 const int LIM = , N = ;

 int mi[LIM+], primes[N], tot;

 bool flag[LIM+];

 void get_primes(int n) {

     for(int i = ; i <= n; i++) {

         if(!flag[i]) primes[tot] = i, mi[i] = tot++;

         for(int j = ; j < tot; j++) {

             int k = primes[j];

             if(i * k > n) break;

             flag[i * k] = ;

             if(i % k == ) break;

         }

     }

 }

 int num[N];

 void add(int x, int sign) {

     for(int i = , k; k = primes[i], k * k <= x; i++) {

         while(x % k == ) {

             num[i] += sign;

             x /= k;

         }

     }

     if(x ^ ) num[mi[x]] += sign;

 }

 int main() {

 #ifdef DEBUG

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif

     int n, m;

     scanf("%d%d", &n, &m);

     get_primes(n + m);

     for(int i = n + m; i > m; i--) add(i, );

     for(int i = n; i > ; i--) add(i, -);

     add(n - m + , ), add(n + , -);

     res.da[] = res.n = ;

     for(int i = ; i < tot; i++) {

         while(num[i]--) res = res * primes[i];

     }

     res.print(); puts("");

     return ;

 }