网站备案号不存在,建设银行的官方网站积分商场,家用电脑怎么做网站,苏州网络推广哪家好辛勤二更题目题解错排数概念错排数递推公式及其证明代码实现这种题做的时候#xff1a; 做完后#xff1a;正常这就是生活#xff0c;我们要学会习惯
题目
求有多少种长度为 n 的序列 A#xff0c;满足以下条件#xff1a; 1 ~ n 这 n 个数在序列中各出现了一次 若第 i …
辛勤二更题目题解错排数概念错排数递推公式及其证明代码实现这种题做的时候 做完后正常这就是生活我们要学会习惯
题目
求有多少种长度为 n 的序列 A满足以下条件 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多序列数对 10^97取模。
输入格式 第一行一个数 T表示有 T 组数据。 接下来 T 行每行两个整数 n、m。 输出格式 输出 T 行每行一个数表示求出的序列数
输入输出样例 输入 5 1 0 1 1 5 2 100 50 10000 5000 输出 0 1 20 578028887 60695423 说明/提示 测试点 1 ~ 3T1000 n≤8 m≤8 测试点 4 ~ 6 T1000 n≤12m≤12 测试点 7 ~ 9 T1000 n≤100 m≤100 测试点 10 ~ 12 T 1000n≤1000 m≤1000 测试点 13 ~ 14 T 500000 n≤1000 m≤1000 测试点 15 ~ 20 T 500000 n≤1000000m≤1000000。
题解
突然想感慨一番
步入正轨↓我真的很讨厌这种有模数的方案数题
题意很简单n个数固定m个数那么就有n-m个数上的位置是不稳定的 也就是这n-m个数要满足A[i]≠i对于这n-m中的某个位置i就只有n-m-1种填法 错排数概念
这里就引入错排数的概念 n个有序的元素应有n!个不同的排列如若一个排列使得所有的元素不在原来的位置上则称这个排列为错排有的也称之为重排 错排数递推公式及其证明
求n个数的错排数DP[n](n−1)∗(DP[n−1]DP[n−2])DP[n](n-1)*(DP[n-1]DP[n-2])DP[n](n−1)∗(DP[n−1]DP[n−2]) 证明如下 ①考虑第n个元素把它放在某一个位置比如位置k一共有n-1种放法 ②考虑第k个元素这时有两种情况 1把它放到位置n那么对于除n以外的n-1个元素由于第k个元素放到了位置n所以剩下n-2个元素的错排即可有f(n−2)f(n-2)f(n−2)种放法 2第k个元素不放到位置n这时对于这n-1个元素的错排有f(n−1)f(n-1)f(n−1)种放法 运用加法以及乘法原理得证完毕。。。 处理完n-m后我们就要处理m要知道选的m的位置不同算不同的方案哦(⊙o⊙) 这个其实就是排列组合从n个数中选m个的方案数 Cnmn!m!∗(n−m)!C_n^m\frac{n!}{m!*(n-m)!}Cnmm!∗(n−m)!n!
这里写出来后就发现这里面涉及到了除法而取模运算中是不能进行除法运算的 所以我们就要去求m!m!m!和(n−m)!(n-m)!(n−m)!各自的逆元与n!n!n!相乘 有很多方法都可以完成费马小定理扩展欧几里得… 代码实现
#include cstdio
#define mod 1000000007
#define LL long long
#define MAXN 1000000
int T, n, m;
LL sum[MAXN 5], inv[MAXN 5], dp[MAXN 5];
LL qkpow ( LL x, int y ) {LL ans 1;while ( y ) {if ( y 1 )ans ans * x % mod;x x * x % mod;y 1;}return ans % mod;
}
LL getinv ( LL x ) {return qkpow ( x, mod - 2 );
}
int main() {scanf ( %d, T );sum[0] 1;inv[0] 1;for ( int i 1;i MAXN;i ) {sum[i] sum[i - 1] * i % mod;inv[i] getinv ( sum[i] );}dp[0] dp[2] 1;for ( int i 3;i MAXN;i )dp[i] ( dp[i - 1] dp[i - 2] ) % mod * ( i - 1 ) % mod;while ( T -- ) {scanf ( %d %d, n, m );printf ( %lld\n, sum[n] * inv[n - m] % mod * inv[m] % mod * dp[n - m] % mod ); }return 0;
} byebye~~~~~~
