2020-2021:teams:legal_string:组队训练比赛记录:contest16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/18 17:05] lgwza [补题情况] |
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/28 08:50] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ||
| - | | A | 2 | 0 | 0 | | + | | A | 2 | 2 | 0 | |
| | B | 0 | 0 | 0 | | | B | 0 | 0 | 0 | | ||
| - | | C | 0 | 0 | 0 | | + | | C | 2 | 2 | 0 | |
| - | | D | 2 | 0 | 0 | | + | | D | 2 | 1 | 0 | |
| | E | 0 | 0 | 0 | | | E | 0 | 0 | 0 | | ||
| | G | 2 | 1 | 0 | | | G | 2 | 1 | 0 | | ||
| - | | I | 0 | 0 | 0 | | + | | I | 2 | 1 | 0 | |
| | J | 2 | 0 | 2 | | | J | 2 | 0 | 2 | | ||
| - | | K | 0 | 0 | 0 | | + | | K | 2 | 1 | 0 | |
| ====== 题解 ===== | ====== 题解 ===== | ||
| 行 131: | 行 131: | ||
| </hidden> | </hidden> | ||
| - | ===== D. Diameter Counting ===== | + | ===== C. Dance Party ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| - | 输出所有 $n$ 标号树的直径和。 | + | 给定 $n\times 2$ 的二分图。对左部每个点，仅和右部 $k_i$ 个点不连边。求二分图最大匹配。 |
| ==== 题解 ==== | ==== 题解 ==== | ||
| + | |||
| + | 设 $k=\max_{i=1}^n k_i$。 | ||
| + | |||
| + | 先进行预匹配，每个左部点任选一个还未被匹配且有连边的右部点匹配，可以用 $\text{set}$ 维护所有未匹配的右部点，时间复杂度 $O(nk\log n)$。 | ||
| + | |||
| + | 接下来剩下的未匹配的点一定不超过 $k$ 个，对每个点考虑匈牙利算法匹配， 总时间复杂度为 $O(km)$。 | ||
| + | |||
| + | $O(m)\sim O(n^2)$，考虑优化。假定现在需要对点 $i$ 进行匈牙利算法，将右部与点 $i$ 不相邻的点染黑，其余右部点染白。 | ||
| + | |||
| + | 对除点 $i$ 以外的左部点，仅保留与黑点相关的连边，这样 $O(m)\sim O(nk)$，总时间复杂度 $O\left(nk^2\right)$ 足以通过此题。 | ||
| + | |||
| + | 关于算法的正确性，假设在原图上存在一条从 $i$ 出发的增广路，且增广路上除了 $i$ 以外有其他点的失配边指向白点。 | ||
| + | |||
| + | 找到增广路上的最后一个白点，直接将 $i$ 的失配边指向该点然后保留原增广路的剩余部分也可以一条增广路。 | ||
| + | |||
| + | 同时该增广路上除了 $i$ 其他点的失配边都指向黑点。因此只要原图存在一条从 $i$ 出发的增广路则只保留与黑点相关的连边也可以得到一条增广路。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e4+5,MAXK=105; | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | }edge[MAXN*MAXK]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | bitset<MAXN> bt[MAXN]; | ||
| + | vector<int> g[MAXN]; | ||
| + | namespace KM{ | ||
| + | set<int> s; | ||
| + | int match[MAXN],vis[MAXN]; | ||
| + | bool dfs(int u,int k){ | ||
| + | if(vis[u]==k) | ||
| + | return false; | ||
| + | vis[u]=k; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(!match[v]||dfs(match[v],k)) | ||
| + | return match[v]=u,true; | ||
| + | } | ||
| + | return false; | ||
| + | } | ||
| + | bool get_pair(int n){ | ||
| + | _rep(u,1,n) | ||
| + | s.insert(u); | ||
| + | vector<int> vec; | ||
| + | _rep(u,1,n){ | ||
| + | bool flag=true; | ||
| + | for(int v:s){ | ||
| + | if(!bt[u][v]){ | ||
| + | match[v]=u; | ||
| + | s.erase(v); | ||
| + | flag=false; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | if(flag) | ||
| + | vec.push_back(u); | ||
| + | } | ||
| + | for(int i:vec){ | ||
| + | mem(head,0); | ||
| + | edge_cnt=0; | ||
| + | _rep(u,1,n){ | ||
| + | for(int v:g[i]){ | ||
| + | if(!bt[u][v]) | ||
| + | Insert(u,v); | ||
| + | } | ||
| + | } | ||
| + | _rep(v,1,n){ | ||
| + | if(!bt[i][v]) | ||
| + | Insert(i,v); | ||
| + | } | ||
| + | if(!dfs(i,i)) | ||
| + | return false; | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | } | ||
| + | int ans[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | _rep(u,1,n){ | ||
| + | int k=read_int(); | ||
| + | while(k--){ | ||
| + | int v=read_int(); | ||
| + | g[u].push_back(v); | ||
| + | bt[u][v]=1; | ||
| + | } | ||
| + | } | ||
| + | if(KM::get_pair(n)){ | ||
| + | _rep(i,1,n) | ||
| + | ans[KM::match[i]]=i; | ||
| + | _rep(i,1,n) | ||
| + | space(ans[i]); | ||
| + | } | ||
| + | else | ||
| + | puts("-1"); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== D. Diameter Counting ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 求所有 $n$ 标号树的直径和。 | ||
| + | |||
| + | ==== 题解1 ==== | ||
| 考虑求树的直径的过程，可以先删去所有叶子结点，得到一棵新树，称为一次操作。然后再不断对新树进行操作，知道最后剩下一个或两个结点。 | 考虑求树的直径的过程，可以先删去所有叶子结点，得到一棵新树，称为一次操作。然后再不断对新树进行操作，知道最后剩下一个或两个结点。 | ||
| 行 175: | 行 287: | ||
| $$ | $$ | ||
| - | 另外所有 $h(i+k,k)\gets 2f(i,j)g(i,j,k){i+k\choose i}$ 也可以等价于 $h(i,j)\gets 2f(i,j)$。时间复杂度 $O\left(n^3\right)$。 | + | 另外所有 $h(i+k,k)\gets 2f(i,j)g(i,j,k){i+k\choose i}$ 也可以等价于 $h(i,j)\gets 2f(i,j)$。时空间复杂度 $O\left(n^3\right)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 223: | 行 335: | ||
| _rep(i,1,n) | _rep(i,1,n) | ||
| ans=(ans+h[n][i])%mod; | ans=(ans+h[n][i])%mod; | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 题解2 ==== | ||
| + | |||
| + | 设 $f(i,j)$ 表示深度为 $j$ 的 $i$ 标号树个数，$g(i,j)$ 表示深度不超过 $j$ 的 $i$ 标号树个数。 | ||
| + | |||
| + | 对一个直径为 $2d+1$ 的 $n$ 标号无根树，可以沿着直径的中心边切开，得到两个深度为 $d$ 的有根树。 | ||
| + | |||
| + | 设 $1$ 号点所在的有根树大小为 $i$，考虑为他分配 $i-1$ 个编号，于是直径为 $2d+1$ 的 $n$ 标号无根树个数为 | ||
| + | |||
| + | $$ | ||
| + | \sum_{i=1}^{n-1}f(i,d)f(n-i,d){n-1\choose i-1} | ||
| + | $$ | ||
| + | |||
| + | 对一个直径为 $2d$ 的 $n$ 标号无根树，可以认为是根节点连接至少两个深度等于 $d-1$ 的有根树。 | ||
| + | |||
| + | 利用容斥，用深度为 $d$ 的 $n$ 标号有根树个数减去根节点仅连接一个深度为 $d-1$ 的有根树个数的情况。 | ||
| + | |||
| + | 根节点仅连接一个深度为 $d-1$ 的有根树可以认为是由一个深度不超过 $d-1$ 的有根树根节点连接一个深度等于 $d-1$ 的有根树得到的。 | ||
| + | |||
| + | 于是直径为 $2d$ 的 $n$ 标号无根树个数为 | ||
| + | |||
| + | $$ | ||
| + | f(n,d)-\sum_{i=1}^{n-1}f(i,d-1)g(n-i,d-1){n\choose i} | ||
| + | $$ | ||
| + | |||
| + | 接下来考虑计算 $f(i,j),g(i,j)$。$f(i,j)$ 难以直接计算，但显然有 $f(i,j)=g(i,j)-g(i,j-1)$，于是只需要计算 $g(i,j)$。 | ||
| + | |||
| + | 对于深度不超过 $j$ 的 $i$ 标号树个数，可以先分配一个编号给根结点，然后从与根节点相连的子树中找到编号最小的结点所在的子树。 | ||
| + | |||
| + | 设子树大小为 $k$，对该子树，他深度不超过 $j-1$，显然有 $g(k,j-1)$ 种。另外需要从剩余 $i-2$ 个编号再分配 $k-1$ 个编号给子树。 | ||
| + | |||
| + | 对于余下的 $n-k$ 个点，深度仍然不超过 $j$，但根节点编号已经分配，所以总数为 $\frac {g(i-k,j)}{i-k}$。于是有 | ||
| + | |||
| + | $$ | ||
| + | g(i,j)=\sum_{k=1}^{i-1}i{i-2\choose k-1}g(k,j-1)\frac {g(i-k,j)}{i-k} | ||
| + | $$ | ||
| + | |||
| + | 时间复杂度 $O\left(n^3\right)$，空间复杂度 $O\left(n^2\right)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=505; | ||
| + | int mod; | ||
| + | int quick_pow(int n,int k){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*n%mod; | ||
| + | n=1LL*n*n%mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int frac[MAXN],invf[MAXN],inv[MAXN]; | ||
| + | int C(int n,int m){ | ||
| + | return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod; | ||
| + | } | ||
| + | int f[MAXN][MAXN],g[MAXN][MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | mod=read_int(); | ||
| + | frac[0]=1; | ||
| + | _for(i,1,MAXN)frac[i]=1LL*frac[i-1]*i%mod; | ||
| + | invf[MAXN-1]=quick_pow(frac[MAXN-1],mod-2); | ||
| + | for(int i=MAXN-1;i;i--){ | ||
| + | invf[i-1]=1LL*invf[i]*i%mod; | ||
| + | inv[i]=1LL*invf[i]*frac[i-1]%mod; | ||
| + | } | ||
| + | g[1][0]=1; | ||
| + | _rep(i,1,n){ | ||
| + | _for(j,1,i)_for(k,1,i) | ||
| + | g[i][j]=(g[i][j]+1LL*g[k][j-1]*g[i-k][j]%mod*C(i-2,k-1)%mod*i%mod*inv[i-k])%mod; | ||
| + | _rep(j,i,n) | ||
| + | g[i][j]=g[i][i-1]; | ||
| + | } | ||
| + | f[1][0]=1; | ||
| + | _rep(i,2,n)_for(j,1,i) | ||
| + | f[i][j]=(g[i][j]-g[i][j-1])%mod; | ||
| + | int ans=0; | ||
| + | _for(i,1,n){ | ||
| + | int cnt=0,d=i/2; | ||
| + | if(i&1){ | ||
| + | _for(j,1,n) | ||
| + | cnt=(cnt+1LL*f[j][d]*f[n-j][d]%mod*C(n-1,j-1))%mod; | ||
| + | } | ||
| + | else{ | ||
| + | cnt=f[n][d]; | ||
| + | _for(j,1,n) | ||
| + | cnt=(cnt-1LL*f[j][d-1]*g[n-j][d-1]%mod*C(n,j))%mod; | ||
| + | } | ||
| + | ans=(ans+1LL*cnt*i)%mod; | ||
| + | } | ||
| + | if(ans<0)ans+=mod; | ||
| enter(ans); | enter(ans); | ||
| return 0; | return 0; | ||
| 行 348: | 行 558: | ||
| return 0; | return 0; | ||
| } | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== I. War of Inazuma (Hard Version) ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 要求给 $n$ 位二进制数染上黑白两色，使得黑白两色的二进制数个数不相等。同时每个二进制数向其他只有一位与自身不同的二进制数连边。 | ||
| + | |||
| + | 要求与每个二进制数相邻的同色二进制数不超过 $m=\lceil\sqrt n\rceil$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 将二进制数写成一个 $\lceil\frac nm\rceil\times m$ 的矩阵，最后一行不足的位置补 $1$，然后将二进制数分为四类： | ||
| + | |||
| + | $A.$ 有奇数个 $1$，至少存在一行全为 $1$ | ||
| + | |||
| + | $B.$ 有偶数个 $1$，不存在一行全为 $1$ | ||
| + | |||
| + | $C.$ 有奇数个 $1$，不存在一行全为 $1$ | ||
| + | |||
| + | $D.$ 有偶数个 $1$，至少存在一行全为 $1$ | ||
| + | |||
| + | $A,B$ 染白色，$C,D$ 染黑色。下面证明方案合法： | ||
| + | |||
| + | 只考虑白色的合法性，黑色的合法性是对称的。 | ||
| + | |||
| + | 首先 $A$，$B$ 内部不连边，因为内部 $1$ 奇偶性相同所有至少有两个位置不同。 | ||
| + | |||
| + | 只有仅一行全 $1$ 的 $A$ 才能和 $B$ 连边，否则至少有两个位置不同。 | ||
| + | |||
| + | 对于 $A$ 仅一行全 $1$ 的数 $u$，为了和 $B$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后 $v$ 在 $u$ 的全 $1$ 行只有一个位置是 $0$。 | ||
| + | |||
| + | 由于一行只有 $m$ 个数，于是这样的 $v$ 最多只有 $m$ 个。 | ||
| + | |||
| + | 对与 $B$ 中的每个数 $u$，为了和 $A$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后仅某一行是全 $1$ 行。 | ||
| + | |||
| + | 由于只有 $\lceil\frac nm\rceil$ 行，因此这样的 $v$ 最多只有 $\lceil\frac nm\rceil\le m$ 个。 | ||
| + | |||
| + | 最后有 $A+C=B+D=2^{n-1},B+C=(2^m-1)^{\lceil\frac nm\rceil}$，于是 $A+B,C+D$ 都是奇数。 | ||
| + | |||
| + | 由于 $4\mid A+B+C+D$，于是 $A+B\neq C+D$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | bool check(int n,int m,int v){ | ||
| + | bool flag_cnt=false; | ||
| + | bool flag_one=false; | ||
| + | for(int i=0;i<n;i+=m){ | ||
| + | bool flag_line=true; | ||
| + | int r=min(n,i+m); | ||
| + | _for(j,i,r){ | ||
| + | int c=v&1; | ||
| + | flag_line&=c; | ||
| + | flag_cnt^=c; | ||
| + | v>>=1; | ||
| + | } | ||
| + | flag_one|=flag_line; | ||
| + | } | ||
| + | return flag_cnt^flag_one; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=ceil(sqrt(n)); | ||
| + | _for(i,0,1<<n) | ||
| + | putchar('0'+check(n,m,i)); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| 行 1120: | 行 1399: | ||
| for(int i=0; i<m; i++) PO.work(po.p[i],i+1); | for(int i=0; i<m; i++) PO.work(po.p[i],i+1); | ||
| JXM::solve(); | JXM::solve(); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== K. Walking ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个 $n\times m$ 的网格和初始点 $(a,b)$，求从初始点出发移动 $t$ 步且始终不出界的情况下的所有走法。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 显然横轴坐标是独立的，可以分开考虑。 | ||
| + | |||
| + | 设 $f(s,n,a)$ 表示从一维坐标轴从 $a$ 点出发走 $s$ 步且始终处于 $[1,n]$ 范围内的情况下的所有走法。于是答案为 | ||
| + | |||
| + | $$ | ||
| + | \sum_{i=0}^t {t\choose i}f(i,n,a)f(t-i,m,b) | ||
| + | $$ | ||
| + | |||
| + | 接下来考虑如何计算 $f(s,n,a)(s\in [0,t])$，$f(s,m,b)$ 的计算方式类同。 | ||
| + | |||
| + | 方案一：设 $\text{dp}(i,j)$ 表示走 $i$ 步最后位于 $j$ 点且始终为出界的方案数，不难得到一个 $O(nt)$ 的暴力解法。 | ||
| + | |||
| + | 方案二：不难发现，有 | ||
| + | |||
| + | $$ | ||
| + | \begin{equation}\begin{split} | ||
| + | f(s,n,a)&=\sum_{i=1}^n \text{dp}(s,i) \\ | ||
| + | &=\text{dp}(s-1,1)+\sum_{i=2}^{n-1} (\text{dp}(s-1,i-1)+\text{dp}(s-1,i+1))+\text{dp}(s-1,n)\\ | ||
| + | & =2f(s-1,n,a)-\text{dp}(s-1,1)-\text{dp}(s-1,n) | ||
| + | \end{split}\end{equation} | ||
| + | $$ | ||
| + | |||
| + | 于是问题转化为计算 $\text{dp}(s,1),\text{dp}(s,n)$。 | ||
| + | |||
| + | 对每个移动方案，定义非法序列，每当点进入 $(-\infty,0)$ 时非法序列末尾加上 $L$，每当点进入 $(n,+\infty)$ 时非法序列末尾加上 $R$。 | ||
| + | |||
| + | 对于 $\text{dp}(s,1)$，我们需要获得所有非法序列为空串的移动方案。设 $h(a,b,s)$ 表示从 $a$ 移动 $s$ 步到达 $b$ 的方案数。 | ||
| + | |||
| + | 显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。 | ||
| + | |||
| + | 然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''.*L+.*'' 和 ''.*R+.*'' (非法序列均用正则表达式表示)的移动方案。 | ||
| + | |||
| + | 设 $l(x)=-x,r(x)=2(n+1)-x$。 | ||
| + | |||
| + | 根据简单组合数学知识，不难发现 ''.*L+.*'' 代表的方案为 $h(a,l(1),s)$，''.*R+.*'' 代表的方案为 $h(a,r(1),s)$。 | ||
| + | |||
| + | 接下来我们需要补上减去非法序列为 ''.*L+R+.*'' 和 ''.*R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。 | ||
| + | |||
| + | 依此类推，有 | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(s,1)=h(a,1,s)-h(a,l(1),s)-h(a,r(1),s)+h(a,r(l(1)),s)+h(a,l(r(1)),s)-h(a,l(r(l(1))),s)-h(a,r(l(r(1))),s)+\cdots | ||
| + | $$ | ||
| + | |||
| + | 由于 $r(l(x))=2(n+1)+x$，且当 $\text{abs}(a-x)\gt s$ 时一定有 $h(a,x,s)=0$，所以上述容斥最多迭代 $O(\frac sn)$ 次。 | ||
| + | |||
| + | 于是方案二的总时间复杂度为 $O\left(\sum_{i=1}^t \frac in\right)\sim O\left(\frac {t^2}n\right)$。 | ||
| + | |||
| + | 考虑根号分治，当 $n\lt \sqrt t$ 时采用方案一，否则采用方案二。总时间复杂度 $O(t\sqrt t)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e5+5,MAXM=800,mod=998244353; | ||
| + | int quick_pow(int n,int k){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*n%mod; | ||
| + | n=1LL*n*n%mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int frac[MAXN],invf[MAXN]; | ||
| + | int C(int n,int m){ | ||
| + | return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod; | ||
| + | } | ||
| + | void init(){ | ||
| + | frac[0]=1; | ||
| + | _for(i,1,MAXN)frac[i]=1LL*frac[i-1]*i%mod; | ||
| + | invf[MAXN-1]=quick_pow(frac[MAXN-1],mod-2); | ||
| + | for(int i=MAXN-1;i;i--) | ||
| + | invf[i-1]=1LL*invf[i]*i%mod; | ||
| + | } | ||
| + | int ans1[MAXN],ans2[MAXN]; | ||
| + | int dp[2][MAXM]; | ||
| + | void solve1(int s,int n,int a,int *ans){ | ||
| + | int pos=0; | ||
| + | mem(dp[pos],0); | ||
| + | dp[pos][a]=1; | ||
| + | ans[0]=1; | ||
| + | _rep(i,1,s){ | ||
| + | pos=!pos; | ||
| + | mem(dp[pos],0); | ||
| + | _rep(j,1,n){ | ||
| + | dp[pos][j]=(dp[!pos][j-1]+dp[!pos][j+1])%mod; | ||
| + | ans[i]=(ans[i]+dp[pos][j])%mod; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int cal(int s,int n,int a,int pos){ | ||
| + | int pos1=pos,pos2=pos,ans=0,d=abs(pos-a); | ||
| + | if(d<=s&&(s-d)%2==0) | ||
| + | ans=C(s,(s+d)/2); | ||
| + | for(int j=1;;j++){ | ||
| + | if(j&1){ | ||
| + | pos1=-pos1; | ||
| + | pos2=2*(n+1)-pos2; | ||
| + | } | ||
| + | else{ | ||
| + | pos1=2*(n+1)-pos1; | ||
| + | pos2=-pos2; | ||
| + | } | ||
| + | int d1=abs(pos1-a),d2=abs(pos2-a),det=0; | ||
| + | if(d1>s&&d2>s)break; | ||
| + | if(d1<=s&&(s-d1)%2==0) | ||
| + | det=(det+C(s,(s+d1)/2)); | ||
| + | if(d2<=s&&(s-d2)%2==0) | ||
| + | det=(det+C(s,(s+d2)/2))%mod; | ||
| + | if(j&1) | ||
| + | ans=(ans+mod-det)%mod; | ||
| + | else | ||
| + | ans=(ans+det)%mod; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | void solve2(int s,int n,int a,int *ans){ | ||
| + | ans[0]=1; | ||
| + | _rep(i,1,s) | ||
| + | ans[i]=(2LL*ans[i-1]+mod-cal(i-1,n,a,1)+mod-cal(i-1,n,a,n))%mod; | ||
| + | } | ||
| + | void solve(int s,int n,int a,int *ans){ | ||
| + | if(1LL*n*n<s) | ||
| + | solve1(s,n,a,ans); | ||
| + | else | ||
| + | solve2(s,n,a,ans); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | init(); | ||
| + | int t=read_int(),n=read_int(),m=read_int(),a=read_int(),b=read_int(); | ||
| + | solve(t,n,a,ans1); | ||
| + | solve(t,m,b,ans2); | ||
| + | int ans=0; | ||
| + | _rep(i,0,t) | ||
| + | ans=(ans+1LL*C(t,i)*ans1[i]%mod*ans2[t-i])%mod; | ||
| + | enter(ans); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest16.1629277522.txt.gz · 最后更改: 2021/08/18 17:05 由 lgwza
