题目描述
求有多少长度为的序列
,满足以下条件:
这
个数在序列中各出现了一次。
若第
个数
的值为
,则称
是稳定的。序列恰好有
个数是稳定的。
满足条件的序列可能很多,序列数对取模。
输入格式
第一行一个数,表示有
组数据。
接下来行,每行两个整数
。
输出格式
输出行,每行一个数,表示求出的序列数。
题目解析
考虑个位置选
个位置为稳定点,其它
个位置错排,有
组合数线性预处理逆元即可。时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/************************************************************** Problem: 4517 User: frank_c1 Language: C++ Result: Accepted Time:9104 ms Memory:32524 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=1000005; const int mo=(int)(1e9)+7; LL D[maxn],inv[maxn],fac[maxn],ivf[maxn]; LL C(int n,int m) {return (fac[n]*ivf[n-m]%mo)*ivf[m]%mo;} int main() { int T; read(T); int mx=1000000; D[0]=0;D[1]=0;D[2]=1; REP(i,3,mx) D[i]=(i-1)*(D[i-1]+D[i-2])%mo; fac[0]=ivf[0]=1; inv[1]=fac[1]=ivf[1]=1;D[0]=1; REP(i,2,mx) { fac[i]=fac[i-1]*i%mo; inv[i] = ((-(mo / i) * inv[mo % i]) % mo + mo) % mo; ivf[i]=ivf[i-1]*inv[i]%mo; } while(T--) { int n,m; read(n);read(m); if(m<=n) printf("%lld\n",C(n,m)*D[n-m]%mo); else printf("0\n"); } return 0; } |
-
lalala