[ARC186D] Polish Mania

· · 题解

或许更好的阅读体验。

dhx 牛逼。

思路：

你发现这个条件显然像个树啊，然后 a_i 表示儿子数，找一下充要条件啊，显然：

容易发现这是充要的，满足这个条件一定可以构造出树来。

翻转后，显然 a_1 = 0，后面可以看作走格路计数，初始在 (0, 0)（横坐标表示 i，纵坐标表示 \sum a），每次向右或向上走，不能碰到 y = x + 1，最终走到 (n - 1, n - 1) 的方案数，这显然是卡特兰。

然后考虑字典序的限制，显然枚举 LCP = n - i，再枚举 a_i < h_i，设后面 LCP 部分和为 s；于是限制在 a 上是末尾经过的那些点是已经确定了（如果已经不合法了直接退出），那么答案是：

\sum_{n - s - i \le a_i \le \min(\{h_i - 1, n - 1 - s \})} F(i - 1, n - 1 - s - a_i)

其中 F(x, y) 是 (0, 0) \to (x, y) 不碰到 y = x + 1 的方案数，直接单线反射容斥，用 (0, 0) \to (x, y) 的减去 (0, 0) \to (x + 1, y - 1) 的路径即可，于是：

F(x, y) = \binom{x + y}{x} - \binom{x + y}{x + 1}

于是答案是：

\sum_{L \le a_i \le R} \binom{i - 1 + n - 1 - s - a_i}{i - 1} - \binom{i - 1 + n - 1 - s - a_i}{i}

本质上是 \sum_{0 \le i \le L} \binom{X - i}{Y} = \binom{X + 1}{Y + 1} - \binom{X - L}{Y + 1}，于是可以 O(1) 算。

总时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcountll(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 6e5 + 10, mod = 998244353;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int add(int x, int y){
    return (x + y >= mod) ? (x + y - mod) : (x + y); 
}
inline void getdec(int &x, int y){
    x = (x < y) ? (x - y + mod) : (x - y);
}
inline int dec(int x, int y){
    return (x < y) ? (x - y + mod) : (x - y);
}
inline int qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int n, ans;
int a[N], fac[N], ifac[N];
inline void init(){
    fac[0] = fac[1] = 1;
    for(int i = 2; i < N; ++i)
      fac[i] = 1ll * i * fac[i - 1] % mod;
    ifac[N - 1] = qpow(fac[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; --i)
      ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod;
}
inline int binom(int n, int m){
    if(n < m)
      return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline int get(int X, int Y, int L){
    return dec(binom(X + 1, Y + 1), binom(X - L, Y + 1));
}
int main(){
    init();
    n = read();
    for(int i = 1; i <= n; ++i)
      a[i] = read();
    reverse(a + 1, a + n + 1);
    int s = 0;
    bool flag = 1;
    for(int i = n; i >= 2; --i){
        int L = max(n - s - (i - 1), 0), R = min({a[i] - 1, n - 1 - s});
        if(L <= R){
            // sum F(i - 2, n - 1 - s - a[i])
            getadd(ans, dec(get(i - 2 + n - 1 - s, i - 2, R), get(i - 2 + n - 1 - s, i - 1, R)));
            getdec(ans, dec(get(i - 2 + n - 1 - s, i - 2, L - 1), get(i - 2 + n - 1 - s, i - 1, L - 1)));
        }
        s += a[i];
        if(n - s > i - 1){
            // cerr << s << ' ' << i - 1 << '\n';
            flag = 0;
            break;
        }
    }
    // cerr << ans << ' ' << flag << '\n';
    getadd(ans, (flag && (s == n - 1) && !a[1]));
    write(ans);
    return 0;
}