可可爱爱推式子练习你也来试试吧

AuCodingFrogHoward · 2026-08-09 17:35:25 · 题解

问候

这是一篇另辟蹊径的题解。可以由无显式性质体现的暴力组合计数方法，经过推导得到简洁明了的解法。

做题感悟

不研究性质是不对的。小朋友们不要学蛙哥啊。

析

暴力想法

期望转计数，即计算贡献值和乘以系数 \frac {1} {\binom{r - l + 1} {t_1, t_2, \dots, t_n}} 的值。系数分母表共 n 种 r - l + 1 个元素，全排列的方案数。系数分母也就等于 \frac {(r - l + 1)!}{\prod_{i = 1}^n t_i!}。

首先我们对贡献进行拆解，分别对每一种元素进行计算。然后可以发现，全排列所有元素等价于剔除一些相同的元素，全排剩下元素，再随意归并剔除的元素和剩下的元素。

于是枚举剔除元素的颜色 i 进行计算。然后枚举它被划成的连续段数为 j。我们发现，t_i 个数有 t_i - 1 个内部间隔，我们要选其中 j - 1 个插入元素，即 \binom {t_i - 1} {j - 1}。然后要先将待归并的其他元素全排列，即 \binom{r - l + 1 - t_i} {t_1, t_2, \dots, t_{i - 1}, t_{i + 1}, \dots, t_n}。再乘上单组贡献 j。剩下的其实是将 r - l + 1 - t_i 个元素归并至 j + 1 个间隔里，且其中 j - 1 个内部间隔不许粘连，必须有元素，所以先减去 j - 1 个元素放进去。剩下的为自然数就行。我们先重排过，所以剩下的元素视为同质的。插板得 \binom {r - l + 2 - t_i} {j}。

整合得

于是有代码甲可以得 85 分（在校园模拟赛里），放在代码仓库中，具体细节则不表。

如何满分

推导。

原式

把可重元素全排列舒展并约分得

移形换位，把 j 挪一下位置得

对 j \binom {t_i - 1} {j - 1} 中 j 进行拆分，变动其为和的形式，然后由乘法分配律得

对 (j - 1) \binom {t_i - 1} {j - 1} 应用上指标乘积恒等式，然后去括号，最后拆开和式，并提取公因式 (t_i - 1) 得

对于形如 \binom {t_i - p} {j - p} 的项使用对称恒等式，在对平凡之处调整求和号范围得

对于中括号内两个独立的和式应用范德蒙德恒等式得

已经是优雅又可爱的形式了。我们考虑直接使用乘法分配律拆中括号化简，并约分，然后进一步平凡地拆解化简至更加简洁的形式得

剩余的和式部分可以用莫队增量维护。见代码乙。

码

::::error[甲]

#include<bits/stdc++.h>
#define int long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 100005
#define endl "\n"
#define nullptr 0
#define mod 998244353ll
#define I ios::sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);

using namespace std;

int fac[maxn] ,facny[maxn];

int ksm (int d ,int z)
{
    if (z < 0)
        return ksm (d ,mod + z - 1);
    if (z == 0)
        return 1;
    if (z == 1)
        return d;
    int t = ksm (d ,(z >> 1));
    if (z & 1)
        return t * t % mod * d % mod;
    return t * t % mod;
}

void init (int k)
{
    fac[0] = 1;
    for (int i = 1 ;i <= k ;i ++)
        fac[i] = (fac[i - 1] * i) % mod;
    facny[k] = ksm (fac[k] ,- 1);
    for (int i = k - 1 ;i >= 0 ;i --)
        facny[i] = (facny[i + 1] * (i + 1)) % mod;
    return ;
}

int C (int a ,int b)
{
    if (a < 0 || b < 0 || a < b)
        return 0;
    return fac[a] * facny[b] % mod * facny[a - b] % mod;
}

int fang_cheng (int sumx ,int numx)
{
    return C (sumx + numx - 1 ,numx - 1);
}

int n ,q ,a[maxn] ,t[maxn];

void Gogogo ()
{
    cin >> n >> q;
    for (int i = 1 ;i <= n ;i ++)
        cin >> a[i];
    map <pair <int ,int> ,int> mp;
    while (q --)
    {
        int l ,r;
        cin >> l >> r;
        if (mp[{l ,r}] != 0)
        {
            cout << mp[{l ,r}] << endl;
            continue ;
        }
        for (int i = 1 ;i <= n ;i ++)
            t[i] = 0;
        for (int i = l ;i <= r ;i ++)
            t[a[i]] ++;
        int yjc = 1;
        for (int i = 1 ;i <= n ;i ++)
            yjc = (yjc * facny[t[i]]) % mod;
        int ans = 0 ,prd = 1;
        for (int i = 1 ;i <= n ;i ++)
        {
            if (t[i])
            {
                prd = (prd * fac[t[i]]) % mod;
                for (int j = 1 ;j <= t[i] ;j ++)
                {
                    ans += fang_cheng (r - l + 1 - t[i] - j + 1 ,j + 1) * j % mod * yjc % mod * fac[t[i]] % mod * fac[r - l + 1 - t[i]] % mod * C (t[i] - 1 ,j - 1) % mod;
                    ans %= mod;
                }
            }
        }
        prd = (prd * facny[r - l + 1]) % mod;
        ans = (ans * prd) % mod;
        cout << ans << endl;
        mp[{l ,r}] = ans;
    } 
}

signed main()
{
    I AK CSP

    freopen ("rune.in" ,"r" ,stdin);
    freopen ("rune.out" ,"w" ,stdout);

    int T;
    init (100000);
    cin >> T;
    while (T --)
        Gogogo ();

    return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.

::::

::::success[乙]

#include<bits/stdc++.h>
#define int long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 100005
#define endl "\n"
#define nullptr 0
#define mod 998244353ll
#define I ios::sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);

using namespace std;

// int fac[maxn] ,facny[maxn];

int ksm (int d ,int z)
{
    if (z < 0)
        return ksm (d ,mod + z - 1);
    if (z == 0)
        return 1;
    if (z == 1)
        return d;
    int t = ksm (d ,(z >> 1));
    if (z & 1)
        return t * t % mod * d % mod;
    return t * t % mod;
}

// void init (int k)
// {
//  fac[0] = 1;
//  for (int i = 1 ;i <= k ;i ++)
//      fac[i] = (fac[i - 1] * i) % mod;
//  facny[k] = ksm (fac[k] ,- 1);
//  for (int i = k - 1 ;i >= 0 ;i --)
//      facny[i] = (facny[i + 1] * (i + 1)) % mod;
//  return ;
// }

// int C (int a ,int b)
// {
//  if (a < 0 || b < 0 || a < b)
//      return 0;
//  return fac[a] * facny[b] % mod * facny[a - b] % mod;
// }

// int fang_cheng (int sumx ,int numx)
// {
//  return C (sumx + numx - 1 ,numx - 1);
// }

int B ,n ,q ,a[maxn] ,ans[maxn] ,cur ,t[maxn] ,l ,r;

struct mo
{
    int l ,r ,id;

    friend bool operator < (mo a ,mo b)
    {
        return (a.l / B == b.l / B) ? (a.r / B < b.r / B) : (a.l / B < b.l / B);
    }

} qr[maxn];

void qadd (int pos)
{
    cur += ((t[pos] ++) << 1) + 1;
    return ;
}

void qdlt (int pos)
{
    cur -= ((-- t[pos]) << 1) + 1;
    return ;
}

void shi_pei (int l_ ,int r_)
{
    while (l < l_)
        qdlt (a[l ++]);
    while (l > l_)
        qadd (a[-- l]);
    while (r < r_)
        qadd (a[++ r]);
    while (r > r_)
        qdlt (a[r --]);
    return ;
}

void Gogogo ()
{
    cin >> n >> q;
    for (int i = 1 ;i <= n ;i ++)
        cin >> a[i];
    B = n / (sqrt (q)) + 1;
    for (int i = 1 ;i <= q ;i ++)
        cin >> qr[i].l >> qr[i].r ,qr[i].id = i;
    sort (qr + 1 ,qr + q + 1);
    for (int i = 1 ;i <= n ;i ++)
        t[i] = 0;
    l = 1 ,r = 0 ,cur = 0;
    for (int i = 1 ;i <= q ;i ++)
        shi_pei (qr[i].l ,qr[i].r) ,ans[qr[i].id] = (((qr[i].r - qr[i].l + 2) - (cur % mod * ksm (qr[i].r - qr[i].l + 1 ,- 1) % mod)) % mod + mod) % mod;
    for (int i = 1 ;i <= q ;i ++)
        cout << ans[i] << endl;
}

signed main()
{
    I AK CSP

    freopen ("rune.in" ,"r" ,stdin);
    freopen ("rune.out" ,"w" ,stdout);

    int T;
    // init (100000);
    cin >> T;
    while (T --)
        Gogogo ();

    return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.

::::