CCPC-Wannafly Winter Camp Day4 G---置置置换【递推】【组合数】【逆元】-白红宇

CCPC-Wannafly Winter Camp Day4 G---置置置换【递推】【组合数】【逆元】

阅读量：4557 次

发布时间：2019-06-08

本文共 1660 字，大约阅读时间需要 5 分钟。

置置置换

已经提交已经通过

63.89%

Total Submission：72

Total Accepted：46

题目描述

$\le i \le n)i(2≤i≤n)，若iii为奇数，则a[i−1]<a[i]a[i - 1] < a[i]a[i−1]<a[i]，否则a[i−1]>a[i]a[i - 1] > a[i]a[i−1]>a[i]。请输出答案mod 1e9 + 7。$

输入描述

一行一个整数

$\le n \le 10001≤n≤1000$

输出描述

一行一个整数表示答案。

样例输入 1

样例输出 1

题意：

一个1……n的排列，问有多少种方案可以使得这个排列所有奇数位置的数都比偶数位置上的数要大。

思路：

wls和我们赛场上过的时候的方法都是用dp的。

$dp[i][j]$表示考虑前$i$个位置，第$i$个位置在剩下的数中是第$k$小的。（口胡）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 11 using namespace std;12 typedef long long LL;13 14 const LL mod = 1e9 + 7;15 int n;16 LL C[1005][1005];17 LL A[1005];18 19 void getC()20 {21 for(int i = 1; i <= n; i++){22 C[i][0] = C[i][i] = 1;23 }24 C[1][1] = 1;25 for(int i = 2; i <= n; i++){26 for(int j = 1; j <= i / 2; j++){27 C[i][j] = C[i][i - j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;28 }29 }30 }31 32 void exgcd(LL a,LL b,LL& d,LL& x,LL& y)33 {34 if(!b) { d = a; x = 1; y = 0; }35 else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }36 }37 38 LL inv(LL a, LL p)39 {40 LL d, x, y;41 exgcd(a, p, d, x, y);42 return d == 1 ? (x+p)%p : -1;43 }44 45 LL getA()46 {47 A[0] = A[1] = 1;48 49 for(int i = 2; i <= n; i++){50 for(int k = 0; k <= i - 1; k++){51 A[i] = (A[i] + C[i - 1][k] * A[k] % mod * A[i - 1 - k] % mod) % mod;52 }53 A[i] = A[i] * inv(2, mod) % mod;54 }55 }56 57 int main()58 {59 scanf("%d", &n);60 getC();61 getA();62 cout<
              
               <