企业官网建设流程全解析

专做负面的网站,沈阳广告设计公司,p2p网站开发文档,韩国今天新闻前言 看见 mod1e9 7 就跪了#xff0c;遂写一篇博客把所有的计数问题、组合数学问题都记录下来… 正片 E. Girl Permutation Some permutation of length nnn is guessed. You are given the indices of its prefix maximums and suffix maximums. Recall that a permu…前言看见 mod1e9 7 就跪了遂写一篇博客把所有的计数问题、组合数学问题都记录下来…正片E. Girl PermutationSome 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 iji.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 iji.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 71097.感觉好经典的模型没有想出来是因为一直在纠结两部分分开处理的情况下发生重复怎么办。。实际上我们可以发现只要先用组合数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 res1%mod;while(k){if(k1)res(i64)res*a%mod;a(i64)a*a%mod;k1;}returnres;}intinv(intx){returnqpow(x,mod-2);}structComb{intn;vectorintfac,invfac,pow2;Comb():n(0){}Comb(int_n):n(0){init(_n);}voidinit(intm){if(mn)return;fac.resize(m1);invfac.resize(m1);pow2.resize(m1);pow2[0]1;for(inti1;im;i){pow2[i](int)(pow2[i-1]*2LL)%mod;}intstartn0?n1:1;if(n0){fac[0]invfac[0]1;}for(intistart;im;i){fac[i](int)((i64)fac[i-1]*i%mod);}invfac[m]qpow(fac[m],mod-2);for(intim;i(n0?1:n);i--){invfac[i-1](int)((i64)invfac[i]*i%mod);}nm;}// fac[m]intF(intm){if(mn)init(2*m);returnfac[m];}// invfac[m]intiF(intm){if(mn)init(2*m);returninvfac[m];}// inv[m] m^{-1}intinv(intm){returnqpow(m,mod-2);}// pow(2, n)intP2(intm){if(mn)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;cinnm1m2;vectorintp(m11),s(m21);for(inti1;im1;i){cinp[i];}for(inti1;im2;i){cins[i];}if(s[m2]!n||p[1]!1||s[1]!p[m1]){cout0endl;return;}intanscomb.C(n-1,p.back()-1);for(intim1-1;i1;i--){intgp[i1]-p[i]-1;(ans*comb.C(p[i1]-2,g)*comb.F(g)%mod)%mod;}for(inti1;im2-1;i){intgs[i1]-s[i]-1;(ans*comb.C(n-s[i]-1,g)*comb.F(g)%mod)%mod;}coutansendl;}