排列组合求助

学术版

alpharchmage @ 2025-01-10 20:39:18

P10986

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n = 0 , m = 0;
array<int , 100100> fact , fact_inv;
int quick_pow(int x , int y , int p)
{
    int res = 1;
    while(y)
    {
        if(y & 1)
        {
            res *= x;
            res %= p;
        }
        x *= x;
        x %= p;
        y /= 2;
    }
    return res;
}
int get_inv(int x)
{
    return quick_pow(x , mod - 2 , mod);
}
int C(int n , int m)
{
    return fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    fact[0] = 1;
    for(int i = 1;i <= n;++ i) fact[i] = fact[i - 1] * i % mod;
    for(int i = 0;i <= n;++ i) fact_inv[i] = get_inv(fact[i]);
    if(n - 4 * m <= 3)
    {
        cout << quick_pow(10 , n - 4 * m , mod) * C(n - 4 * m + m , m) % mod << endl;
        return 0;
    }
    else
    {
        cout << (quick_pow(10 , n - 4 * m , mod) * C(n - 4 * m + m , m) % mod - quick_pow(10 , n - 4 * m - 4 , mod) * C(n - 4 * m - 4 + m + 1 , m + 1) % mod + mod) % mod % mod << endl;
    }
    return 0;
}

这道题为什么不能用至少(m + 1)个的情况减去至少m个的情况?


by Winston12321_ @ 2025-01-10 21:10:30

因为你的代码算的并不是至少出现m次的字符串数。

例如某个出现了m+2次的串,你理应计算1次,而实际上你计算了 \binom {m+2} {m} 次。


by Winston12321_ @ 2025-01-10 21:13:13

@alpharchmage


by zhouyuhang @ 2025-01-10 21:14:25

实际上这就是二项式反演的意义所在。你以为你求出的“至少 m 个的方案数”,但是实际上你求出的是“钦定 m 个的方案数”。这两者的区别在哪里呢?从数学语言来讲,如果记恰好 i 个的方案数为 f_i,这也是一般我们想要求出的东西,至少 m 个就是简单的后缀和 \sum _ {i = m} ^ n f_i,但钦定 m 个则是在所有元素中选择 m 个强制满足条件,并不对剩余元素做任何限制的方案数,而对于一个恰好 i 个满足条件的方案,有 \binom i m 种选出这 m 个元素的方案,因此其实际上为 \sum _ {i = m} ^ n \binom i m f_i。在这道题种,你以为你算出来的是前者,但实际上确是后者,这也就导致了答案于实际不符。


by alpharchmage @ 2025-01-10 21:29:43

@Winston12321_哦,谢谢


by alpharchmage @ 2025-01-10 21:45:27

@zhouyuhang谢谢


|