搭建网站首页,资讯网站的好处,免费自己做网站,网站游戏怎么制作正题
题目链接:https://www.luogu.com.cn/problem/CF960G 题目大意
求有多少个长度为nnn的排列#xff0c;使得有AAA个前缀最大值和BBB个后缀最大值。 0≤n,A,B≤1050\leq n,A,B\leq 10^50≤n,A,B≤105 解题思路
显然的是把最大的数两边然后左边的是前缀最大值#xff0c;…正题
题目链接:https://www.luogu.com.cn/problem/CF960G 题目大意
求有多少个长度为nnn的排列使得有AAA个前缀最大值和BBB个后缀最大值。
0≤n,A,B≤1050\leq n,A,B\leq 10^50≤n,A,B≤105 解题思路
显然的是把最大的数两边然后左边的是前缀最大值右边的是前缀最小值。
然后考虑两个前缀最大值之间其实可以插任何数字但是最大的一定要排在前面。
其实就是这些数字分成若干个圆排列的个数就是第一类斯特林数。
枚举左右两边的数量就有 ∑i0n−1[ia−1][n−i−1b−1](n−1i)\sum_{i0}^{n-1}\begin{bmatrix}i\\a-1\end{bmatrix}\begin{bmatrix}n-i-1\\b-1\end{bmatrix}\binom{n-1}{i}i0∑n−1[ia−1][n−i−1b−1](in−1) 然后组合意义理解一下我们可以考虑直接分成ab−2ab-2ab−2个环然后再依次排列到左右就是 [n−1ab−2](ab−2a−1)\begin{bmatrix}n-1\\ab-2\end{bmatrix}\binom{ab-2}{a-1}[n−1ab−2](a−1ab−2)
这个看起来就好做很多先考虑怎么求第一类斯特林数。
考虑递推式 [nm][n−1m−1][n−1m]×(n−1)\begin{bmatrix}n\\m\end{bmatrix}\begin{bmatrix}n-1\\m-1\end{bmatrix}\begin{bmatrix}n-1\\m\end{bmatrix}\times(n-1)[nm][n−1m−1][n−1m]×(n−1) 可以理解为0∼n−10\sim n-10∼n−1个里面选出mmm个数的乘积之和。
用生成函数做就是 ∏i0n−1(xi)\prod_{i0}^{n-1}(xi)i0∏n−1(xi)
用分治NTTNTTNTT算就好了当然推式子还有更快的方法
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510,P998244353;
struct Poly{ll f[N];ll n;
}F[20];
ll n,a,b,f[N],g[N],r[N];bool use[20];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void NTT(ll *f,ll n,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll tmppower(3,(P-1)/p),lenp1;if(op-1)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttf[ilen]*buf%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(n,P-2);for(ll i0;in;i)f[i]f[i]*invn%P;}return;
}
void mul(Poly x,Poly y){ll n1;while(nx.ny.n)n1;for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);for(ll i0;in;i)f[i]x.f[i],g[i]y.f[i];NTT(f,n,1);NTT(g,n,1);for(ll i0;in;i)f[i]f[i]*g[i]%P;NTT(f,n,-1);for(ll i0;in;i)x.f[i]f[i],y.f[i]0;x.nx.ny.n-1;return;
}
ll FindE(){for(ll i0;i20;i)if(!use[i])return i;
}
ll solve(ll l,ll r){if(lr){ll pFindE();F[p].f[0]l;F[p].f[1]1;F[p].n2;use[p]1;return p;}ll mid(lr)1;ll lssolve(l,mid),rssolve(mid1,r);mul(F[ls],F[rs]);use[rs]0;return ls;
}
ll C(ll n,ll m){ll ans1,fac1;for(ll im1;in;i)ansans*i%P;for(ll i1;in-m;i)facfac*i%P;return ans*power(fac,P-2)%P;
}
signed main()
{scanf(%lld%lld%lld,n,a,b);if(!a||!b||ab-2n-1)return puts(0)0;if(n1)return puts(1)0;ll psolve(0,n-2);printf(%lld\n,F[p].f[ab-2]*C(ab-2,a-1)%P);return 0;
}
