Hz的计数问题总结

前言

看见 mod1e9 + 7 就跪了，遂写一篇博客把所有的计数问题、组合数学问题都记录下来…

正片

E. Girl Permutation

Some permutation of lengthn nnis guessed.

You are given the indices of its prefix maximums and suffix maximums.

Recall that a permutation of lengthk kkis an array of sizek kksuch that each integer from1 11tok kkoccurs exactly once.

Prefix maximums are the elements that are the maximum on the prefix ending at that element. More formally, the elementa i a_iai​is a prefix maximum ifa i > a j a_i > a_jai​>aj​for everyj < i j < ij<i.

Similarly, suffix maximums are defined, the elementa i a_iai​is a suffix maximum ifa i > a j a_i > a_jai​>aj​for everyj > i j > ij>i.

You need to output the number of different permutations that could have been guessed.

As this number can be very large, output the answer modulo1 0 9 + 7 10^9 + 7109+7.

感觉好经典的模型，没有想出来是因为一直在纠结两部分分开处理的情况下发生重复怎么办。。

实际上我们可以发现，只要先用组合数C CC选出一部分数字放在左边，剩下的部分放在右边，则两部分一定不会发生重复。

但是一定存在一种方案使得它们摆放起来满足方案吗？

答案是YES，这个自己手玩一下就可以发现了，数量够的情况下，排列中的数字两两不同，则总会存在一种方式使得摆放是正确的。

因此分开考虑是合法的。

接下来就是单独考虑左边，我们从右向左（从高到低）遍历p pp数组，可以发现每两个相邻的下标中间存在着一些 gap，我们选择一些比 p[i] 和 p[i + 1] 都要小的数字填充这些 gap（全排列），所以就是comb(p[i + 1] - 2, p[i + 1] - p[i] - 1)；

这里的 -2 是因为最大值和次大值已经放在了 p[i] 和 p[i + 1] 的位置，故，必须-2.

最后代码如下：

intqpow(inta,intk){a%=mod;i64 res=1%mod;while(k){if(k&1)res=(i64)res*a%mod;a=(i64)a*a%mod;k>>=1;}returnres;}intinv(intx){returnqpow(x,mod-2);}structComb{intn;vector<int>fac,invfac,pow2;Comb():n(0){}Comb(int_n):n(0){init(_n);}voidinit(intm){if(m<=n)return;fac.resize(m+1);invfac.resize(m+1);pow2.resize(m+1);pow2[0]=1;for(inti=1;i<=m;i++){pow2[i]=(int)(pow2[i-1]*2LL)%mod;}intstart=n>0?n+1:1;if(n==0){fac[0]=invfac[0]=1;}for(inti=start;i<=m;i++){fac[i]=(int)((i64)fac[i-1]*i%mod);}invfac[m]=qpow(fac[m],mod-2);for(inti=m;i>(n==0?1:n);i--){invfac[i-1]=(int)((i64)invfac[i]*i%mod);}n=m;}// fac[m]intF(intm){if(m>n)init(2*m);returnfac[m];}// invfac[m]intiF(intm){if(m>n)init(2*m);returninvfac[m];}// inv[m] = m^{-1}intinv(intm){returnqpow(m,mod-2);}// pow(2, n)intP2(intm){if(m<=n)returnpow2[m];returnqpow(2,m);}// A(n, m) = n! / (n - m)!intA(intn_,intm_){if(m_<0||m_>n_)return0;if(n_>n)init(2*n_);return(int)((i64)fac[n_]*invfac[n_-m_]%mod);}// C(n, m) = n! / (m! * (n - m)!)intC(intn_,intm_){if(m_<0||m_>n_)return0;if(n_>n)init(2*n_);return(int)((i64)fac[n_]*invfac[m_]%mod*invfac[n_-m_]%mod);}};Combcomb(1e6);voidsolve(){intn,m1,m2;cin>>n>>m1>>m2;vector<int>p(m1+1),s(m2+1);for(inti=1;i<=m1;i++){cin>>p[i];}for(inti=1;i<=m2;i++){cin>>s[i];}if(s[m2]!=n||p[1]!=1||s[1]!=p[m1]){cout<<0<<endl;return;}intans=comb.C(n-1,p.back()-1);for(inti=m1-1;i>=1;i--){intg=p[i+1]-p[i]-1;(ans*=comb.C(p[i+1]-2,g)*comb.F(g)%mod)%=mod;}for(inti=1;i<=m2-1;i++){intg=s[i+1]-s[i]-1;(ans*=comb.C(n-s[i]-1,g)*comb.F(g)%mod)%=mod;}cout<<ans<<endl;}