ARC124E Pass to Next

tony102

2021 年 11 月 12 日

1409 次浏览

暂无评论

1490字数

题解

[Link](https://atcoder.jp/contests/arc124/tasks/arc124_e)

## Sol

神题

先考虑怎么计算所有合法的 $x$ 的数量。$\prod (a_i+1）$ 会算重。因为可以选 $0$ ，假如一个 $x$ 选了 $0$ 以后相当于多了一个空。所以要减去 $\prod a_i$。

观察样例发现，假如 $\min \{x_i\} \neq 0$ 的话 ，$\prod x_i$ 是一个定值。可以这么考虑：设 $c_i$ 为第 $i$ 个人向右边传递的个数，那么 $c_i \to c'_i = c_i-1$ 对答案没有影响，相当于把 $x_i$ 换了一下位置。

那么我们只需要考虑计算这个 $c_i$。设 $f_{i,0/1}$ 表示：$0$ 表示前 $i-1$ 个人都没传球，$i$ 从自己这里传了一个；$1$ 表示 $i-1 \to i$  传了一个。

转移：

$$
f_{i+1,0} \leftarrow \begin{equation} \left\{ \begin{array}{lr} f_{i,0} \times \sum\limits_{x=1}^{a_i} x, & \\f_{i,1} \times (a_i-1)  \end{array} \right. \end{equation}
$$

$$
f_{i+1,1} \leftarrow \begin{equation} \left\{ \begin{array}{lr} f_{i,0} \times \sum\limits_{x=1}^{a_i} a_i \cdot (a_i-x), & \\f_{i,1} \times \sum\limits_{x=1}^{a_i} x  \end{array} \right. \end{equation}
$$

解释：

1. 假如 $i+1$ 决定从自己这里转，那么有 $i$ 乘上在 $a_i$ 中选 $1 \sim a_i$ 个种方案，也可以是 $i$ 选一个给 $i+1$ 后 $i+1$ 后再选一个，那么 $a_i$ 选了一个后就只有 $(a_i-1)$ 个可以转给 $i+1$ 了。
2. 同理，懒得写了

在代码实现中，$\sum\limits_{x=1}^{a_i} a_i \cdot (a_i-x) = a_i \cdot \sum\limits_{x=1}^{a_i} x - \sum\limits_{x=1}^{a_i} x^2$

## Idea

1. 计数题真没套路。要注意这种会算的东西的性质。
2. dp 转移不能忽视

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 1e5 + 5, mod = 998244353;
const int inv2 = (mod + 1) / 2, inv3 = (mod + 1) / 3, inv6 = inv2 * inv3 % mod;

int n;
int a[SIZE], f[SIZE][2];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

auto s1 = [] (int x) { return x * (x + 1) % mod * inv2 % mod; };
auto s2 = [] (int x) { return x * (x + 1) % mod * (2 * x % mod + 1) % mod * inv6 % mod; };

int dp(int x, int y) {
    memset(f, 0, sizeof(f));
    f[1][x] = 1;
    for (int i = 1, j; i <= n; ++ i) {
        j = i % n + 1;
        f[j][0] = (f[i][0] * s1(a[i] - y) % mod + f[i][1] * (a[i] - y + 1) % mod) % mod;
        f[j][1] = (f[i][0] * (a[i] * s1(a[i]) % mod - s2(a[i]) + mod) % mod + f[i][1] * s1(a[i]) % mod) % mod;
    }
    return f[1][x];
}

signed main() {
    n = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    int ans = (dp(1, 0) + dp(0, 0)) % mod;
    ans = (ans - dp(1, 1) + mod) % mod, ans = (ans - dp(0, 1) + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}
```

最后修改：2021 年 11 月 15 日