NOI.AC CSP-S 模拟 Round 2 T1 Count (组合数学) (容斥)

本文主要是介绍NOI.AC CSP-S 模拟 Round 2 T1 Count (组合数学) (容斥)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
题意：给定两个整数 $n, m$ 求 k 元组 $(a 1, a 2, \dots, a k)$ 的个数，满足 $a 1, a 2, \dots, a k$ 为正整数
$\sum a_i=n$ 且 $a 1, a 2, \dots, a k$ 均不是 $m$ 的倍数
$n\le 1e18,m\le5e3,k\le2e3$

首先，如果没有 $m$ 的限制，答案为 $\binom{n-1}{k-1}$ ，插板，先全部减去1
考虑 $m$ 的限制，发现不好容斥
发现最后的序列一定没有 m 的倍数，并且如果一个数 $\ge m$ ，可以将它表示为 $r + k m$
于是我们可以将最后的序列抽象为先选好 $a_1,a_2,...,a_k$ ，并强制让 $a_i<m$ ，再对 $a_i$ 随便加几个 $m$
枚举 $\sum r_i = S$ ， $r$ 为上文所述的 $r$ ，那么先选好的 $a_1,a_2,...,a_k$ 的条件可以抽象为：

$\sum a_i = S$
$a_i \le m-1$

然后在对几个 $a_i$ 加上 $m$ 的倍数，假设 $\le n$ 的范围内有 $c$ 个 m 的倍数
发现这个过程等价于把 $c$ 分到 k 个集合，可以为空，方案数为 $\binom{c+k-1}{k-1}$
如何求第一个，一下令 $m$ 为 $m - 1$ ，考虑容斥，强制 $i$ 个 $> m$
但如何求强制 $i$ 个 $> m$ 的个数呢，发现这个问题等价于选 i 个位置出来 $> m$ ，然后将 $n - i * m$ 分配给这 $k$ 个集合，最后再将这 $i$ 个加上 $m$ ，于是有
$f(n,m,k)=\sum_{i=0}^k(-1)^i\binom{k}{i}\binom{n-i*m-1}{k-1}$

最后的答案
$ans=\sum_{i=0}^k f(i*m+n\%m,m-1,k)*\binom{\frac{n}{m}-i+k-1}{k-1}$
$n\le 1e18$ ，组合数暴力乘，有些不像 $T 1$

#include<bits/stdc++.h>
#define cs const
using namespace std;
typedef long long ll;
ll read(){ll cnt = 0, f = 1; char ch = 0;while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt * f;
}
cs int N = 1e7 + 5;
cs int Mod = 998244353;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b;}
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a, b);}
ll n; int m, k, fac[N], inv[N];
int C(ll n, int m){if(n < 0 || m < 0 || n < m) return 0;if(n < N) return mul(fac[n], mul(inv[m], inv[n - m]));else{int ret = inv[m];for(ll i = n; i >= n - m + 1; i--) ret = mul(ret, i % Mod);return ret;}
}
int g(ll n, int m){// devide n into m group and the group can be emptyif(n < 0) return 0;return C(n + m - 1, m - 1);
}
int f(int n, int m, int k){ // devide n into m group that the size of each group is less than k// can not be empty n -= m; if(n < 0) return 0;int ans = 0;for(int i = 0; i <= m; i++){int ret = mul(g(n - i * k, m), C(m, i));(i & 1) ? Add(ans, Mod - ret) : Add(ans, ret); } return ans;
}
int main(){n = read(), m = read(), k = read();fac[0] = fac[1] = inv[0] = inv[1] = 1;for(int i = 2; i < N; i++) fac[i] = mul(fac[i-1], i);for(int i = 2; i < N; i++) inv[i] = mul(Mod-Mod/i, inv[Mod%i]);for(int i = 2; i < N; i++) inv[i] = mul(inv[i], inv[i-1]);// 枚举 < m 的数的和  ll r = n % m; int ans = 0;for(int i = 0; i < k; i++){Add(ans, mul(f(i * m + r, k, m - 1), g((n - r) / m - i, k))); } cout << ans; return 0;
}