Count of Array Problem(codechef)

Count of Array Problem(codechef)

#includeusing namespace std;typedef long long ll;#define endl "\n"const int mod = 1e9 + 7;const int N = 4e5 + 1;#define int long long int fac[N], infac[N];int n, m;int qmi (int a, int b) { int ans = 1; while(b) { if (b & 1) ans = ans * a % mod; b >>= 1; a = a * a % mod; } return ans;}void pre () { fac[0] = 1; for (int i =1; i < N; i ++) fac[i] = fac[i - 1] * i % mod; infac[0] = 1; for (int i = 1; i < N; i ++) { infac[i] = infac[i - 1] * qmi(i, mod - 2) % mod; }}int C(int a, int b) { if (b >a) return 0; return (fac[a] * (infac[a - b] % mod * infac[b] % mod))%mod;}void solve() { pre(); cin >> n >> m; vector a; int p = 0; for (int i = 0; i < n; i ++) { int t; cin >> t; a.push_back(t); if (t >= 1 && t <= m) p ++; } if (m < n) { cout << 0 << endl; return ; } int ans = C(m, n) * fac[n] % mod; for (int i = 1; i <= p; i ++) { int val = C(p, i) % mod; val = val * C(m - i, n - i) % mod; val = val * fac[n - i] % mod; ans %= mod; if (i & 1) ans -= val; else ans += val; ans += mod; ans %= mod; } cout << ans << endl;}signed main(){ int t; t = 1; // cin >>t; while (t --) solve();}

注意用减法的地方先+再取mod； 这里有逆元求组合数 这道题是先求满足第一个和第二个约束条件的组合数C(m, n) * fac[n] 然后用容斥原理。求一个位置不满足第三个条件的。。。x个位置不满足第三个条件的。然后奇数减去偶数加上 C(m, n) * fac[n] - C(p, 1) * C(m - 1, n - 1) * fac[n - 1] . 乘上的意义是进行排列因为已经确定了一个位置C(p ,1)所以还剩下n - 1个位置

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。