foj Problem 2282 Wand-白红宇

foj Problem 2282 Wand

阅读量：5159 次

发布时间：2019-06-13

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

Problem 2282 Wand

Accept: 432 Submit: 1537
Time Limit: 1000 mSec Memory Limit : 262144 KB

Problem Description

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

2 1 1 3 1

Sample Output

1 4

Source

第八届福建省大学生程序设计竞赛-重现赛（感谢承办方厦门理工学院）

题意：有n个法师n根魔法棒,每个法师都有属于自己的1根魔法棒，求至少有k个法师没拿到自己的魔法棒的情况数。

思路：首先题目中k远远小于n，所以可以考虑相反面，考虑只有1,2,...,k-1个法师没拿到自己的魔法棒的情况数，再用n!减去这些情况的情况数即可。

若挑出x个人，这x个人都没拿到自己的魔法棒的情况数记为D(x),即为数量为x个人的错排数，C(n,x)*D(x)就是x个人没拿到魔法棒的总情况数。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;#define N_MAX 10000+4#define MOD 1000000007#define INF 0x3f3f3f3ftypedef long long ll;int n, k;ll dp[N_MAX];//错排数ll C[N_MAX][100 + 2];void init() { dp[0] = 1; dp[1] = 0; dp[2] = 1; for (int i = 3; i < N_MAX; i++) { dp[i] = ((i - 1)*(dp[i - 1] + dp[i - 2]) + MOD) % MOD; }}void C_table() { for (int i = 0; i < N_MAX; i++) { C[i][0] = 1; for (int j = 1; j <= min(100, i); j++) { //!!!j<=i并且数组中j不能超过100 C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD; } }}int main() { init(); C_table(); int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &k); ll num = 0, ans = 1; for (ll i = 1; i <= n; i++) { ans = ans*i%MOD; } for (int i = 0; i <= k - 1; i++) { num = (num + C[n][i] * dp[n - i]) % MOD; } printf("%lld\n", (ans - num + MOD) % MOD); } return 0;}

转载于:https://www.cnblogs.com/ZefengYao/p/9158676.html

你可能感兴趣的文章