网站简繁转换,网站 美食频道 建设,黄骅贴吧在线,哪个网站用织梦做的ARC 124 E Pass to Nextproblemsolutioncodeproblem
题目链接
solution
令 ci:c_i:ci: 第 iii 个人传给下一个人球的个数
当 min{ci}≠0\min\{c_i\}\neq 0min{ci}0 时#xff0c;将每一个 cic_ici 都减小 111#xff0c;显然答案序列并不会改变
所以#x…
ARC 124 E Pass to Nextproblemsolutioncodeproblem
题目链接
solution
令 ci:c_i:ci: 第 iii 个人传给下一个人球的个数
当 min{ci}≠0\min\{c_i\}\neq 0min{ci}0 时将每一个 cic_ici 都减小 111显然答案序列并不会改变
所以我们只需要考虑 min{ci}0\min\{c_i\}0min{ci}0 的情况
这样性质的 ccc 序列一共有 ∏i1n(ai1)−∏i1nai\prod_{i1}^n(a_i1)-\prod_{i1}^na_i∏i1n(ai1)−∏i1nai 种每一种都会导致最后不同的结果序列 至少有一个人是不传球的方案数总方案数−-−每个人都传球的方案数将 111 看作不传球 ∏i1nxi∏i1n(xi1):\prod_{i1}^nx_i\prod_{i1}^n\binom{x_i}{1}:∏i1nxi∏i1n(1xi): 理解成每个人传完球后从手里剩下的球中选一个的方案数
所以我们就可以设计 dpi,0/1dp_{i,0/1}dpi,0/1 转移了
dpi,0:dp_{i,0}:dpi,0: 第 iii 个人从自己原有的球上选一个前 i−1i-1i−1 个人的方案数dpi,1:dp_{i,1}:dpi,1: 第 iii 个人从第 i−1i-1i−1 个人给的球中选一个前 iii 个人的方案数
因为是同时一起给下一个人球的所以每个人手中原本的球可以看成时一种来源不同来源球直接的分配是相互独立的前一个人传递过来多少与自己传递多少出去是互不干扰的 dpi1,0←dpi,0⋅ai(ai1)2dp_{i1,0}\leftarrow dp_{i,0}·\frac{a_i(a_i1)}{2}dpi1,0←dpi,0⋅2ai(ai1) 由于 dpi,0dp_{i,0}dpi,0 没有算 iii 的贡献转移时要加上且这种情况 iii 时从自己手上剩的球中选一个 如果剩下 xxx 个就有 xxx 种选法而 x∈[1,ai]x\in[1,a_i]x∈[1,ai]所以方案数为 ∑x1aix\sum_{x1}^{a_i}x∑x1aix dpi1,0←dpi,1⋅(ai1)dp_{i1,0}\leftarrow dp_{i,1}·(a_i1)dpi1,0←dpi,1⋅(ai1) 由于 dpi,1dp_{i,1}dpi,1 已经算了 iii 的贡献转移只需要考虑 i→i1i\rightarrow i1i→i1 的球数且此情况下先不计算 i1i1i1 在自己手上选球的贡献 传递 0,1,...,ai0,1,...,a_i0,1,...,ai 个一共是 ai1a_i1ai1 种方案 dpi1,1←dpi,0⋅(ai⋅ai(ai1)2−ai(ai1)(2ai1)6)dp_{i1,1}\leftarrow dp_{i,0}·\Big(a_i·\frac{a_i(a_i1)}{2}-\frac{a_i(a_i1)(2a_i1)}{6}\Big)dpi1,1←dpi,0⋅(ai⋅2ai(ai1)−6ai(ai1)(2ai1)) 由于 i,i1i,i1i,i1 的贡献都没有计算转移时要一起加上 如果 iii 传递了 xxx 个那么就还剩下 ai−xa_i-xai−x 个iii 是从自己手中选则有 ai−xa_i-xai−x 中选法i1i1i1 是从 iii 传的球中选一个则有 xxx 种选法 所以总方案数为 ∑x1aix(ai−x)ai⋅∑x1ai−∑x1aix2ai⋅ai(ai1)2−ai(ai1)(2ai1)6\sum_{x1}^{a_i}x(a_i-x)a_i·\sum_{x1}^{a_i}-\sum_{x1}^{a_i}x^2a_i·\frac{a_i(a_i1)}{2}-\frac{a_i(a_i1)(2a_i1)}{6}∑x1aix(ai−x)ai⋅∑x1ai−∑x1aix2ai⋅2ai(ai1)−6ai(ai1)(2ai1) dpi1,1←dpi,1⋅ai(ai1)2dp_{i1,1}\leftarrow dp_{i,1}·\frac{a_i(a_i1)}{2}dpi1,1←dpi,1⋅2ai(ai1) 由于已经计算了 iii 的贡献所以只需要考虑 i1i1i1 的贡献 i1i1i1 选的是 iii 传递的球如果 iii 传了 xxx 个那么就有 xxx 种选择方案数为 ∑x1aixai(ai1)2\sum_{x1}^{a_i}x\frac{a_i(a_i1)}{2}∑x1aix2ai(ai1)
最后因为是个环所以初始应该钦定 111 的选择
显然这个 dpdpdp 的过程并没有考虑 min{ci}0\min\{c_i\}0min{ci}0 的限制而是随意转移
所以利用容斥减去强制至少转移一个球的方案数就对应着至少有一个人的 ci0c_i0ci0 的方案数 具体而言 iii 从自己手上剩的球选择剩的球就被限制为了 1,2,...,ai−11,2,...,a_{i-1}1,2,...,ai−1 转移变为 dpi1,0←dpi,0⋅ai(ai−1)2dp_{i1,0}\leftarrow dp_{i,0}·\frac{a_i(a_i-1)}{2}dpi1,0←dpi,0⋅2ai(ai−1) iii 传递给 i1i1i1 至少都是一个球 1,2,...,ai1,2,...,a_i1,2,...,ai 转移变为 dpi1,0←dpi,1⋅aidp_{i1,0}\leftarrow dp_{i,1}·a_idpi1,0←dpi,1⋅ai 而 case3 case4 的转移因为为了使 (x1)\binom{x}{1}(1x) 有意义所以 xxx 自带条件就是 ≥1\ge 1≥1转移不变 code
#include cstdio
#include cstring
#define int long long
#define mod 998244353
#define maxn 300005
const int inv2 ( mod 1 ) / 2;
const int inv6 ( mod 1 ) / 6;
int n;
int a[maxn];
int dp[maxn][2];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}int solve( int o, int k ) {memset( dp, 0, sizeof( dp ) );dp[1][o] 1;for( int i 1, x, g, f;i n;i ) {x a[i] - k;g x * ( x 1 ) % mod * inv2 % mod;dp[i 1][0] ( dp[i][0] * g dp[i][1] * ( x 1 ) ) % mod;x a[i];g x * ( x 1 ) % mod * inv2 % mod;f x * ( x 1 ) % mod * ( x 1 | 1 ) % mod * inv6 % mod;dp[i 1][1] ( ( a[i] * g - f ) % mod * dp[i][0] dp[i][1] * g ) % mod;}return dp[n 1][o];
}signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, a[i] );printf( %lld\n, ( ( solve( 1, 0 ) solve( 0, 0 ) - solve( 0, 1 ) - solve( 1, 1 ) ) % mod mod ) % mod );return 0;
}
