源代码: #include<cstdio> #define LL long long #define INF 1000000007 LL m,n,Num(0),i[100001],Sum[100001]; bool Vis1[100001]={0},Vis2[100001]={0}; LL M(LL t) //取模,注意负数。 { if (t>=0&&t<INF) return t; t%=INF; if (t<0) t+=INF; return t; } LL Count(LL X,LL S) //快速幂。 { LL Number=1; while (S) { if (S&1) Number=(Number*X)%INF; X=(X*X)%INF; S>>=1; } return Number; } LL C(LL n,LL m) { if (n<m||!n) return 0; return i[n]*Sum[n-m]%INF*Sum[m]%INF; } int main() { scanf("%lld%lld",&n,&m); i[0]=1; for (LL a=1;a<=n;a++) i[a]=i[a-1]*a%INF; for (LL a=0;a<=n;a++) Sum[a]=Count(i[a],INF-2); for (LL a=1;a<=m;a++) { LL t1,t2; scanf("%lld%lld",&t1,&t2); if (t1==t2) { printf("0"); return 0; } Vis1[t1]=Vis2[t2]=true; } LL Ans=i[n-m]; for (LL a=1;a<=n;a++) if (!Vis1[a]&&!Vis2[a]) Num++; for (LL a=1;a<=Num;a++) if (a&1) Ans=M(Ans-C(Num,a)*i[n-m-a]); else Ans=(Ans+C(Num,a)*i[n-m-a])%INF; printf("%lld",Ans); return 0; } /* 一道NOIP阶段比较全面的排列组合题。 原始的错排公式: (1)通过CodeVS ⑨要写信 可以得出递推公式: f[i]=(i-1)(f[i-1]+f[i-2]) (2)n个数的全排列个数为n!,其中第k位为k的个数为(n-1)!,那么对于n个数,共有n(n-1)!为放对一个的,则减去; 但会把两个数放对的多减一次,则加上C(n,2)*(n-2)!; 但会把三个数放对的多加一次,则减去C(n,3)*(n-3)!; 以此类推,最终可得错排公式: Ans=n!-C(n,1)*(n-1)!+C(n,2)*(n-2)!-C(n,3)*(n-3)!+...+(-1)^n*C(n,n)*(n-n)! =∑(k=0~n)(-1)^k*C(n,k)*(n-k)! 其实就是容斥原理。 现行的错排公式: 仿照以上,设s为剩下的(n-m)个数仍有可能放到正确位置的个数,则有: Ans=(n-m)!-C(s,1)*(n-m-1)!+C(s,2)*(n-m-2)!+...+(-1)^s*C(s,s)*(n-m-s)! =∑(k=0~s)(-1)^k*C(s,k)*(n-m-k)! 排列组合如此神奇。 */