模拟赛题讲解[24]

来自 s_r_f 2023-08-02 noi.ac #3192

题目描述：

小 B 有一个数字 \(x\)，一开始是 \(0\)。

他会 \(n\) 种加法魔法和 \(m\) 种乘法魔法：第 \(i\) 种加法魔法会让自己的数字 \(x\) 增加 \(a_i\) ，第 \(i\) 种乘法魔法会让自己的数字 \(x\) 变为原来的 \(b_i\) 倍。所有的 \(a_i\) 和 \(b_i\) 都非负。

他想知道，每种魔法必须恰好使用一次的情况下，数字 \(x\) 的最大值是多少，以及有多少种不同的顺序能让 \(x\) 达到这个最大值。

不同编号的魔法，即使效果一样也被看做不同的。

因为答案可能非常大，所以你只需要输出答案对 \(998244353\) 取模的结果。

提示： 在模 \(998244353\) 意义下，对于非零 \(x\)，有 \(x^{-1} \equiv x^{998244351} \pmod {998244353}\)

输入格式：

第一行，两个整数 \(n\) \(m\)。

第二行，\(n\) 个整数 \(a_1, a_2,\cdots, a_n\)

第三行，\(m\) 个整数 \(b_1, b_2,\cdots, b_m\)

输出格式：

输出两行。

第一行一个非负整数 \(\mathrm{Max}\) ，表示 \(x\) 的最大值 对 \(998244353\) 取模的结果。

第二行一个非负整数 \(\mathrm{Ans}\) ，表示顺序数量 对 \(998244353\) 取模的结果。

样例输入1：

2 2
2 3
4 5

样例输出1：

100
4

样例输入2：

2 2
0 1
4 5

样例输出2：

20
8

样例输入3：

2 2
0 1
0 30

样例输出3：

30
4

数据范围：

子任务 1(50pts) : \(n + m \leq 10,0 \leq a_i,b_i \leq 2\)

子任务 2(30pts) \(:\) \(a_i \leq 1\)

子任务 3(20pts) : \(0 \leq n,m \leq 100000,0\leq a_i,b_i \leq 10^3\)

题解：

可以看出我的组合数有多烂。

第一问的话，可以证明最终答案一定形如 \((x\times 0+a_i+\cdots)\times b_i\times \cdots\) ，注意乘 \(0\) 要在一开始就乘掉。

考虑第二问。如果不存在 \(a_i > 0\) ，则所有运算可以任意排序，答案为 \((n + m)!\) 。

如果存在 \(a_i = 0\) ，则

• 只考虑 \(b_i=0,~b_i > 1\) 和 \(a_i > 0\) ，此时的顺序不能乱搞，因此此部分为他们各自的阶乘的乘积。
• 考虑加入 \(b_i = 1\) 和 \(a_i = 0\) 的运算，这些运算就可以放在任何位置。

因此答案为 \[ \dbinom{n+m}{c_1}\times(c_1 !) \times(c_2 !) \times(c_3 !) \times(c_4 !) \] 其中 \(c\) 分别代表 \(b_i=1\) 和 \(a_i=0\) 、\(b_i=0\) 、\(b_i > 1\) 、\(a_i > 0\) 。

时间复杂度 \(\mathcal{O}(n+m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(4e5 + 15))

int n,m,mx,cnt1,cnt2,p1,p2,a1[N],b1[N],a[N],b[N],fac[N << 2],inv[N << 2];
int qpow(int a,int b)
{ 
    int c = 1;
    for(; b; b >>= 1) {
        if(b & 1) { c = c * a % mod; }
        a = a * a % mod;
    }
    return c;
}
int C(int n,int m)
{
    if(n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= N - 10; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = qpow(fac[i], mod - 2);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i]; add(mx, a[i]);
        if(a[i] == 0) ++cnt1; else a1[++p1] = a[i];
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> b[i];
        if(b[i] == 0) ++cnt2;
        else {
            if(b[i] == 1) ++cnt1; else b1[++p2] = b[i];
            mx = mx * b[i] % mod;
        }
    }
    cout << mx << '\n';
    if(!mx) { cout << fac[n + m] << '\n'; } else {
        cout << fac[p1] * fac[p2] % mod * fac[cnt1] % mod * fac[cnt2] % mod * C(p1 + p2 + cnt1 + cnt2, cnt1) % mod << '\n';
    }
    return 0;
}