AC. 梦想

frank_c1

[SDOI 2016] 排列计数

发布于2016年04月23日 | 2条评论 | 2,842阅读 | 组合数学

题目描述

求有多少长度为n的序列A,满足以下条件:

1 - nn个数在序列中各出现了一次。

若第i个数A[i]的值为i,则称i是稳定的。序列恰好有m个数是稳定的。

满足条件的序列可能很多,序列数对10 ^ 9 + 7取模。

输入格式

第一行一个数T,表示有T组数据。

接下来T行,每行两个整数n,m

输出格式

输出T行,每行一个数,表示求出的序列数。

题目解析

考虑n个位置选m个位置为稳定点,其它n-m个位置错排,有

ans = {n \choose m} D(n - m)

组合数线性预处理逆元即可。时间复杂度O(n + T)

  • lalala

    讲道理这是Round1Day2而不是Round2啊……

    • 多谢神犇指正!不敢乱写了……