牛客网暑期ACM多校训练营(第八场)B.Filling pools
这题算的实际上是 nth Schrder number
如果不直接打算看oeis的递推式,可以看下下面的wiki以及递推式(推广)证明论文
对于这个问题你需要知道Narayana number
然后Generalized Small Schr¨oder numbers
这篇论文是对 nth Schrder number
做了一点小推广得到 5-colored Dyck paths and small Schrder path
最后得到
对于这道题我们将推广稍微修改一下便可得到正解
至于为什么,emmmmm,其实不似很懂,还需要仔细看下上面的那篇论文.
下面挂一下队友(Wisdom+.+/lzh)写的代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MOD = 998244353; const int N = 3e5 + 5; LL C[N], NN[N], inv[N], p[N], ans = 0; LL q_pow(LL n, LL k) { LL ans = 1; while(k) { ans = (ans * n) % MOD; n = (n * n) % MOD; k >>= 1; } return ans; } void init(int n) { n--; inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD; p[0] = 1; for (int i = 1; i <= n; i++) p[i] = (p[i-1] * 2) % MOD; C[0] = 1; for (int i = 1; i <= n; i++) C[i] = ((C[i-1] * (n-i+1)) % MOD * inv[i]) % MOD; for (int i = 1; i <= n; i++) NN[i] = (C[i] * C[i-1]) % MOD * inv[n] % MOD; for (int i = 1; i <= n; i++) ans = (ans + NN[i] * p[n-i+1]) % MOD; } int main() { int n; scanf("%d", &n); if(n == 1) return 0*puts("1"); init(n); printf("%lld\n", ans); return 0; }
发表评论