网站模板怎么用法,商务网站建设需要备案吗,浙江网站怎么做推广,哪个网站可以做店招正题
题目链接:https://ac.nowcoder.com/acm/contest/7745/C 题目大意
求一nnn的排列#xff0c;给mmm个限制pip_ipi表示1∼pi1\sim p_i1∼pi不能是pip_ipi的排列。求方案数。 解题思路
定义fif_ifi表示1∼pi1\sim p_i1∼pi是pip_ipi的排列的情况下1∼pi1\sim …正题
题目链接:https://ac.nowcoder.com/acm/contest/7745/C 题目大意
求一nnn的排列给mmm个限制pip_ipi表示1∼pi1\sim p_i1∼pi不能是pip_ipi的排列。求方案数。 解题思路
定义fif_ifi表示1∼pi1\sim p_i1∼pi是pip_ipi的排列的情况下1∼pi1\sim p_i1∼pi的方案数显然有fipi!f_ip_i!fipi!。但是如果我们用这个计算就会重复所以我们需要容斥。定义fif_ifi表示1∼pi1\sim p_i1∼pi是pip_ipi的排列且1∼pk1\sim p_k1∼pk不是pkp_kpk的排列(ki)(ki)(ki)的情况下1∼pi1\sim p_i1∼pi的方案数那么有转移方程fipi!−∑j1i−1fj∗(pi−pj)!f_ip_i!-\sum_{j1}^{i-1}f_{j}*(p_i-p_j)!fipi!−j1∑i−1fj∗(pi−pj)!
然后答案ansn!−∑i1mfi∗(n−pi)!ansn!-\sum_{i1}^mf_i*(n-p_i)!ansn!−i1∑mfi∗(n−pi)!
时间复杂度O(m2)O(m^2)O(m2) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100,XJQ20000311;
ll n,m,fac[N],p[N],f[N];
int main()
{scanf(%lld%lld,n,m);fac[0]1;for(ll i1;in;i)fac[i]fac[i-1]*i%XJQ;for(ll i1;im;i)scanf(%lld,p[i]);sort(p1,p1m);for(ll i1;im;i){f[i]fac[p[i]]%XJQ;for(ll j1;ji;j)f[i](f[i]-f[j]*fac[p[i]-p[j]]%XJQXJQ)%XJQ;}ll ansfac[n];for(ll i1;im;i)ans(ans-f[i]*fac[n-p[i]]%XJQXJQ)%XJQ;printf(%lld,ans);
}
