从零开始的数数大学习
2026-04-12 17:16:38
发布于：广东
60阅读
0回复
0点赞
我真零基础啊
由于数组大多数都以 命名，所以排列数以形如 表示。
置顶立马删帖。
P6146
Difficulty：3.2 / Easy
这题我怎么都做这么吃力啊。
拆成上半部分和下半部分。
注意到上半部分所有放 个的情况等价。所以考虑枚举 。
上半部分的情况数是 ，下半部分情况数是 ，乘起来即可。
namespace cjdst{
const ll N = 2000, mod = 100003;
ll frac[N + 5], invfrac[N + 5];
ll ksm(ll x, ll y){
ll ans = 1;
while(y){
if(y & 1) ans = ans * x % mod;
x = x * x % mod, y >>= 1;
}
return ans;
}
void init(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
frac[0] = 1;
for(int i = 1; i <= N; i++){
frac[i] = frac[i - 1] * i % mod;
}
invfrac[N] = ksm(frac[N], mod - 2);
for(int i = N - 1; i >= 0; i--){
invfrac[i] = invfrac[i + 1] * (i + 1) % mod;
}
}
ll A(ll n, ll m){
if(m > n) return 0;
return frac[n] * invfrac[n - m] % mod;
}
ll C(ll n, ll m){
if(m > n) return 0;
return frac[n] * invfrac[m] % mod * invfrac[n - m] % mod;
}
void solve(){
int a, b, c, d, k;
std::cin >> a >> b >> c >> d >> k;
ll ans = 0;
for(int i = 0; i <= k; i++){
ans += A(a, i) * C(b, i) % mod * A(a + c - i, k - i) % mod * C(d, k - i) % mod;
ans %= mod;
}
std::cout << ans << '\n';
}
}
时间复杂度：。
P16256
场切，爽！
Difficulty: 4.0 / Easy+
考虑每一个 的贡献。注意到这个贡献是独立的，不受前面（除 ）贡献情况的影响。因此可以单独计算。
定义 为 ，显然如果满足 或 ，则会产生 的贡献。把它们分别计作情况 1，情况 2。
情况 1
显然前 要在 之间选， 要在 之间选，剩下的随便选。总情况数为 。
情况 2
前 都要在 选，但必须至少有一个要大于 。这太难了。
考虑反向统计，总方案数为 ，不合法的有 ，所以合法的有 。
再用方案 1 同种方法考虑后面的，总贡献数为 。
时间复杂度：。
有帮助，赞一个