HDU 4828 Grids

思路：可以转化为卡特兰数，先把前n个人标为0，后n个人标为1，然后去全排列，全排列的数列，如果每个1的前面对应的0大于等于1，那么就是满足的序列，如果把0看成入栈，1看成出栈，那么就等价于n个元素入栈出栈，求符合条件的出栈序列，这个就是卡特兰数了。然后去递推一下解，过程中需要求逆元去计算
代码：

#include 
   
     #include 
    
      const int N = 1000005; const long long MOD = 1000000007; long long extend_gcd(long long a,long long b,long long &x,long long &y) { if(a == 0 && b == 0) return -1; if(b == 0){x = 1; y = 0; return a;} long long d = extend_gcd(b, a % b, y, x); y -= a / b * x; return d; } long long mod_reverse(long long a, long long n) { long long x,y; long long d = extend_gcd(a, n, x, y); if(d == 1) return (x % n + n) % n; else return -1; } int t, n; long long Catalan[N]; int main() { Catalan[1] = Catalan[2] = 1; for (int i = 3; i < N; i++) { long long tmp = mod_reverse((long long) i, MOD); Catalan[i] = Catalan[i - 1] * (4 * i - 6) % MOD * tmp % MOD; } int cas = 0; scanf("%d", &t); while (t--) { scanf("%d", &n); printf("Case #%d:\n", ++cas); printf("%lld\n", Catalan[n + 1]); } return 0; }