题解 P4071 【[SDOI2016]排列计数】

# 对于任何一个卡读入的题，我都只能说醉了…… ## 这是一篇通俗的题解，没有多大的技术含量，适合初学者使用 ## 自然也就不用懂什么错不错排啦（我就没听说过） 这道题的题意非常简单，就是说给出n长度的序列，有m个数的大小等于自己的下标，叫我们求合法的方案数。 在没有真正接触容斥原理之前，我对于这类题都是理解错误，可是当真正学了容斥原理之后，我发现了容斥原理的妙用（~~当然是对于我而言~~） 这道题，我们可以很习惯的把序列拆成大小等于数组下标的和大小不等于数组下标的 - 对于大小等于数组下标的 我们明显可以得出一个结论，这就是从n个数里面选出m个数，这m个数的大小等于其数组下标，那么合法的方案数为： $$ ans1=\frac{n!}{m! \times (n-m)!}=C_n^m $$ - 对于大小不等于数组下标的 我一开始想的是先算出其余数的排列(n-m)!,然后减去1就可以了，减去1是因为在其余方案数中，只有一种方案是所有数的大小都等于数组下标，花了 $$ \color{Red}5mins $$ 打出来之后，卡死在样例上。 $$ n=5 $$ $$ m=2 $$ 我的输出是50，但事实上该是20 我仔细一想，对哦，如果在剩下的n-m个数里面，如果有一个数的大小等于数组下标，那么此方案就不合法，因为我在前面已经挑出来了m个数了。 ### 敲黑板 所以我们现在应该想一想，到底该怎么办？ #### 根据某不愿透露姓名的dalao所说，当你碰到一个题，如果你发现你没法直接算出来方案数，而且限制条件是有m个数不满足XX，那么就基本是容斥原理了 所以我们可以发现: 方案数=至少有0个数的数组下标等于大小（的方案数）-至少有1个数的数组下标等于大小+至少2个…… 而至少i个数的数组下标等于大小的方案数等于 $$ C_{n-m}^i \times (n-m-i)! $$ 其中，C代表的是从n-m个数中选出i个数，这i个数的数组下标等于大小（可以类比上面的东西） 而后面的阶乘就是剩下的数的全排列（因为我们说的是至少，所以不用管等不等于） 可能一些同学会问，为什么这个是对的（就是为什么容斥原理是对的），我以前也这样问过，可是最后发现只有自己想出来的才最靠谱，不然都会在考场上爆炸（几位学长学姐**血**的教训） 所以 $$ ans2= \sum\limits_{i=0}^{n-m}C_{n-m}^i \times (n-m-i)! \times (-1)^i $$ ans2 又等于 $$ ans2=\sum\limits_{i=0}^{n-m}\frac{(n-m)!}{i!} \times (-1)^i $$ 所以说，总的方案数就是 $$ ans1\times ans2 = \frac{n!}{m!} \sum\limits_{i=0}^{n-m}\frac{(-1)^i}{i!} $$ 这里是将ans2中的(n-m)!提了出来与ans1中的约掉。 然后我们就走完了80%的路程 $$ {\color{Red}On\;reaching\;the\;last\;leg\;of\;a \;journey,\;you\;are\;only\;half\;way\;there.} $$ 我们现在看看时间复杂度…… 是不是很恐怖，可是 ## 有一种强大的优化，他叫前缀和 前缀和是一种特殊的树状数组，他的功能很少，但是很好用 因此，我们可以把阶乘，逆元（用费马小定理，如果你连这个都不知道，请出门右拐）提前处理出来，然后就可以AC这道例题了。 ## 慢着，我怎么只有60分！ 如果亲爱的你碰到了这个问题，并且后面的是TLE的话，看看最上面的东西 现在贴代码： ```cpp #include<cstdio> #include<iostream> #define Starseven main #define ll long long #define ri register int using namespace std; const ll mod=1e9+7; const int N=1e6+20; ll p[N]; ll merse[N],dda[N]; ll read(){ char ch=getchar(); ll re=0,op=1; while(ch<'0'||ch>'9'){ if(ch=='-') op=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ re=(re<<3)+(re<<1)+ch-'0'; ch=getchar(); } return re*op; } void write(ll x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); return ; } ll Power(ll a,ll b,ll c){ ll re=1; while(b){ if(b&1) re=(re*a)%c; b>>=1; a=(a*a)%c; } return re; } int Starseven(void){ p[0]=1; merse[0]=1; for(ri i=1;i<=N-20;i++){ p[i]=(p[i-1]*i)%mod;//这个是预处理阶乘 p[i]=(p[i]+mod)%mod; ll y; merse[i]=Power(p[i],mod-2,mod);//这个是用费马小定理提前处理逆元 } int t=read(); dda[0]=merse[0]; for(ri i=1;i<=N-20;i++){ if(i&1) dda[i]=dda[i-1]-merse[i]; else dda[i]=dda[i-1]+merse[i];//这个是前缀和，提前把那个求和符号里面的东西弄出来 dda[i]=(dda[i]+mod)%mod; } while(t--){ ll n=read(),m=read(); ll ans=(p[n]*merse[m])%mod*dda[n-m]%mod; write(ans); puts(""); } return 0; } ```