2025年810975（组合数学+容斥原理）

科技前沿 • 2025-03-30 13:57 • 阅读 57

大家好，我是讯享网，很高兴认识大家。

[Link](Problem - M - Codeforces)

题意

给你一个长度为 $n$ 的 $01$ 串，有 $m$ 个 $1$ ，求最长 $1$ 连续段长度恰好为 $k$ 的方案数。

题解

先容斥转化为算 $\le k$ 的方案数。我们把两个连续的 $0$ 中间视为一个长度为 $0$ 的 $1$ 连续段，问题转化为求一共 $n - m + 1$ 个 $1$ 连续段，每段长度 $\le k$ ，长度和为 $m$ 的方案数，假设为 $f (n, m, k)$ ，那么我们的答案就是 $f (n, m, k) - f (n, m, k - 1)$ 。对于 $f$ 的求法我们可以容斥枚举有多少个段违反了 $\le k$ 这个限制就可。容斥枚举多少个 $1$ 连续段不满足 $\le k$ 即可。

Code

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <set> #include <queue> #include <vector> #include <map> #include <bitset> #include <unordered_map> #include <cmath>  #include <stack> #include <iomanip> #include <deque>  #include <sstream> #define x first #define y second #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long double ld; typedef long long LL; typedef pair<int, int> PII; typedef pair<double, double> PDD; typedef unsigned long long ULL; const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = ; const double eps = 1e-8, pi = acos(-1), inf = 1e20; #define tpyeinput int inline char nc() { 
   static char buf[],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,,stdin),p1==p2)?EOF:*p1++;} inline void read(tpyeinput &sum) { 
   char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();} int dx[] = { 
   -1, 0, 1, 0}, dy[] = { 
   0, 1, 0, -1}; int h[N], e[M], ne[M], w[M], idx; void add(int a, int b, int v = 0) { 
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++; } int n, m, k; LL fact[N], infact[N]; LL C(LL n, LL m) { 
    if (m > n || m < 0) return 0; return fact[n] * infact[m] % mod * infact[n - m] % mod; } void init() { 
    fact[0] = infact[0] = infact[1] = 1; for (int i = 1; i < N; i ++ ) fact[i] = fact[i - 1] * i % mod; for (int i = 2; i < N; i ++ ) infact[i] = (mod - mod / i) * infact[mod % i] % mod; for (int i = 2; i < N; i ++ ) infact[i] = infact[i] * infact[i - 1] % mod; } LL f(int n, int m, int k) { 
    if (!k) { 
    if (!m) return 1; else return 0; } if (k > m) return 0; int p = n - m + 1; LL res = 0; for (int i = 0; i <= p; i ++ ) { 
    int op = i & 1 ? -1 : 1; res += op * C(p, i) * C(m - i * (k + 1) + p - 1, p - 1) % mod; } res = (res + mod) % mod; return res; } int main() { 
    ios::sync_with_stdio(false), cin.tie(0); cin >> n >> m >> k; init(); if (!k || k > m) cout << f(n, m, k) << endl; else cout << (f(n, m, k) - f(n, m, k - 1) + mod) % mod << endl; return 0; }

讯享网

2025年810975（组合数学+容斥原理）

题意

题解

Code

相关推荐