Wand FZU - 2282 全错位重排-白红宇

Wand FZU - 2282 全错位重排

阅读量：4611 次

发布时间：2019-06-09

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

N wizards are attending a meeting. Everyone has his own magic wand. N magic wands was put in a line, numbered from 1 to n(Wand_i owned by wizard_i). After the meeting, n wizards will take a wand one by one in the order of 1 to n. A boring wizard decided to reorder the wands. He is wondering how many ways to reorder the wands so that at least k wizards can get his own wand.

For example, n=3. Initially, the wands are w1 w2 w3. After reordering, the wands become w2 w1 w3. So, wizard 1 will take w2, wizard 2 will take w1, wizard 3 will take w3, only wizard 3 get his own wand.

Input

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Two number n and k.

1<=n <=10000.1<=k<=100. k<=n.

Output

For each test case, output the answer mod 1000000007(10^9 + 7).

Sample Input

21 13 1

Sample Output

14 现在一群 wizard 在开会，进入会议室的时候，每个人将自己的 wand 放到了桌子上，现在开会结束了， 在 wizard 们将要离开的时候，将 wand 原来的摆放顺序打乱，那 wizard 将桌子上的 wang 拿走时：  要求：至少有 K 个人拿到的是自己原来的 wand 。问，有多少种打乱顺序的方法 首先在 n 个中拿出 k 到 n 个，是放在原来的位置，方法有 C(n,i)种，然后将剩下的那些 wand 错排 预处理阶乘逆元

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #define pi acos(-1.0)13 #define eps 1e-614 #define fi first15 #define se second16 #define lson l,m,rt<<117 #define rson m+1,r,rt<<1|118 #define bug printf("******\n")19 #define mem(a,b) memset(a,b,sizeof(a))20 #define fuck(x) cout<<"["<
                
                 <<"]"<
                 
                  = b; i--)29 #define FRL(i,a,b) for(i = a; i < b; i++)30 #define FRLL(i,a,b) for(i = a; i > b; i--)31 #define FIN freopen("DATA.txt","r",stdin)32 #define gcd(a,b) __gcd(a,b)33 #define lowbit(x) x&-x34 #pragma comment (linker,"/STACK:102400000,102400000")35 using namespace std;36 typedef long long LL;37 const int INF = 0x7fffffff;38 const int mod = 1e9 + 7;39 const int maxn = 1e5 + 10;40 int n, k, t;41 LL ans[maxn], a = 0, b = 1;42 void init() {43 ans[1] = a, ans[2] = b;44 for (int i = 3 ; i <= 10010 ; i++) {45 ans[i] = (((i - 1) % mod) * ((a + b) % mod)) % mod;46 a = b;47 b = ans[i];48 }49 }50 LL C(int k, int n) {51 LL ret = 1;52 for (int i = n - k + 1; i <= n; i++) ret *= i;53 for (int i = 2; i <= k; i++) ret /= i;54 return ret;55 }56 LL c[20000010];57 58 long long modexp(long long a, long long b, int mod) {59 long long res = 1;60 while(b > 0) {61 if (b & 1) res = res * a % mod;62 b = b >> 1;63 a = a * a % mod;64 }65 return res;66 }67 68 void cal() {69 LL ans = 1;70 for(int i = 1; i <= 1e7; i ++) {71 ans *= i;72 ans %= mod;73 c[i] = ans;74 }75 }76 int main() {77 cal();78 c[0] = 1;79 init();80 sf(t);81 while(t--) {82 sff(n, k);83 LL ret = 1;84 for (int i = k ; i <= n ; i++) {85 LL fz = c[n];86 LL fm = (c[i] * c[n - i]) % mod;87 LL a1 = (fz * (modexp(fm, mod - 2, mod) % mod)) % mod;88 ret = (ret + a1 * ans[n - i] % mod) % mod;89 }90 printf("%lld\n", ret % mod);91 }92 return 0;93 }

转载于:https://www.cnblogs.com/qldabiaoge/p/9514821.html

你可能感兴趣的文章