2020-2021:teams:legal_string:组队训练比赛记录:contest16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/17 11:39] 王智彪 |
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/28 08:50] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ||
| - | | A | 0 | 0 | 0 | | + | | A | 2 | 2 | 0 | |
| | B | 0 | 0 | 0 | | | B | 0 | 0 | 0 | | ||
| - | | C | 0 | 0 | 0 | | + | | C | 2 | 2 | 0 | |
| - | | D | 0 | 0 | 0 | | + | | D | 2 | 1 | 0 | |
| | E | 0 | 0 | 0 | | | E | 0 | 0 | 0 | | ||
| - | | G | 0 | 0 | 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 | |
| ====== 题解 ===== | ====== 题解 ===== | ||
| + | |||
| + | ===== A. Browser Games ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 个字符串，对 $i=1\sim n$，找出一个最小的前缀集合，满足： | ||
| + | |||
| + | 对前 $i$ 个字符串都至少有一个前缀位于该集合且对于后面的 $n-i$ 个字符串都不存在前缀属于这个集合。 | ||
| + | |||
| + | 数据保证不存在一个字符串是另一个字符串前缀的情况，且内存限制为 $32\text{ megabytes}$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 首先不考虑内存限制，可以对所有串建立字典树，并用叶子结点代表每个字符串。 | ||
| + | |||
| + | 然后问题转化为从树上选择最少的结点集合，使得前 $i$ 个字符串至少有一个祖先结点被选中，且后 $n-i$ 个字符串不存在祖先结点被选中。 | ||
| + | |||
| + | 不难发现，如果一个结点的子树中叶子结点都属于前 $i$ 个字符串，则以该结点为根的子树答案为 $1$。否则该结点答案等于所有儿子结点答案之和。 | ||
| + | |||
| + | 建立字典树后依次处理 $i=1\sim n$ 的询问，动态更新每个结点的子树中的后 $n-i$ 个字符串个数以及以该结点为根的子树答案。 | ||
| + | |||
| + | 每次询问的答案记为字典树根节点的答案，注意特判 $i=n$ 的询问，因为前缀不能是空串。 | ||
| + | |||
| + | 然后考虑内存限制，注意到只有一个儿子结点的结点都是可以压缩的，于是树上的关键结点个数可以卡到 $O(n)$。 | ||
| + | |||
| + | 最坏的情况是完全二叉树，这时节点个数是 $2n-1$，于是开两倍空间即可。 | ||
| + | |||
| + | 关于建树，可以递归构建，如果当前结点的字符串个数为 $1$ 则直接返回。 | ||
| + | |||
| + | 否则找到最小的当前结点的所有字符串的非公共前缀长度，然后划分字符串，继续递归，同时记录非公共前缀的位置用于后续更新操作比较。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,MAXS=MAXN<<1,MAXL=105; | ||
| + | char s[MAXN][MAXL],suf[MAXS]; | ||
| + | int head[MAXS],nxt[MAXS],dep[MAXS],s1[MAXS],s2[MAXS],node_cnt; | ||
| + | vector<int> c[MAXS]; | ||
| + | void build(int k,int d){ | ||
| + | s1[k]=c[k].size(); | ||
| + | if(s1[k]==1){ | ||
| + | c[k].clear(); | ||
| + | return; | ||
| + | } | ||
| + | while(true){ | ||
| + | int p1=c[k][0]; | ||
| + | bool flag=true; | ||
| + | for(int p2:c[k]){ | ||
| + | if(s[p2][d]!=s[p1][d]){ | ||
| + | flag=false; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | if(flag) | ||
| + | d++; | ||
| + | else | ||
| + | break; | ||
| + | } | ||
| + | dep[k]=d; | ||
| + | for(int t:c[k]){ | ||
| + | int i=head[k]; | ||
| + | for(;i;i=nxt[i]){ | ||
| + | if(suf[i]==s[t][d]) | ||
| + | break; | ||
| + | } | ||
| + | if(!i){ | ||
| + | i=++node_cnt; | ||
| + | nxt[i]=head[k]; | ||
| + | suf[i]=s[t][d]; | ||
| + | head[k]=i; | ||
| + | } | ||
| + | c[i].push_back(t); | ||
| + | } | ||
| + | c[k].clear(); | ||
| + | for(int i=head[k];i;i=nxt[i]) | ||
| + | build(i,d+1); | ||
| + | } | ||
| + | void update(int k,char *t){ | ||
| + | s1[k]--; | ||
| + | if(s1[k]==0){ | ||
| + | s2[k]=1; | ||
| + | return; | ||
| + | } | ||
| + | for(int i=head[k];i;i=nxt[i]){ | ||
| + | if(suf[i]==t[dep[k]]){ | ||
| + | s2[k]-=s2[i]; | ||
| + | update(i,t); | ||
| + | s2[k]+=s2[i]; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | if(n==1){ | ||
| + | puts("1"); | ||
| + | return 0; | ||
| + | } | ||
| + | _rep(i,1,n){ | ||
| + | scanf("%s",s[i]); | ||
| + | c[0].push_back(i); | ||
| + | } | ||
| + | build(0,0); | ||
| + | _for(i,1,n){ | ||
| + | update(0,s[i]); | ||
| + | enter(s2[0]); | ||
| + | } | ||
| + | int ans=0; | ||
| + | for(int i=head[0];i;i=nxt[i]) | ||
| + | ans++; | ||
| + | enter(dep[0]==0?ans:1); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== C. Dance Party ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $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 ==== | ||
| + | |||
| + | 考虑求树的直径的过程，可以先删去所有叶子结点，得到一棵新树，称为一次操作。然后再不断对新树进行操作，知道最后剩下一个或两个结点。 | ||
| + | |||
| + | 此时如果只剩下一个结点，则树的直径为操作次数 $\times 2$。如果剩下两个结点，则树的直径为操作次数 $\times 2+1$。 | ||
| + | |||
| + | 考虑通过逆算法反向构建树。设 $f(i,j)$ 表示有 $j$ 个叶子结点的 $i$ 标号树个数，假设上一步操作删除了 $k(k\ge j)$ 个叶子。 | ||
| + | |||
| + | 于是问题等价于给这 $k$ 个叶子找一个父结点，使得原来的 $j$ 个叶子结点至少有一个儿子。 | ||
| + | |||
| + | 同时对于这 $i+k$ 个结点，标号是任意的，对所有 $i+k$ 标号树而言，删去 $k$ 叶子结点得到的树的标号方式实际上有 ${i+k\choose i}f(i,j)$ 种。 | ||
| + | |||
| + | 设 $g(i,j,k)$ 表示长度为 $k$ 且每个位置有 $i$ 种可选取值且特定的 $j$ 个值至少出现一次的序列个数，于是有 | ||
| + | |||
| + | $$ | ||
| + | f(i+k,k)\gets g(i,j,k)f(i,j){i+k\choose i} | ||
| + | $$ | ||
| + | |||
| + | 接下来考虑求 $g(i,j,k)$，可以考虑序列前 $k-1$ 位，如果此时 $j$ 个特定值都出现了至少一次，则第 $k$ 位可以任取，于是有 | ||
| + | |||
| + | $$ | ||
| + | g(i,j,k)\gets i\times g(i,j,k-1) | ||
| + | $$ | ||
| + | |||
| + | 如果前 $k-1$ 位只有 $j-1$ 个特殊值出现了至少一次，则显然前 $k-1$ 位的取值只有 $i-1$ 种，同时要从 $j$ 个特殊值中确定一个放在第 $k$ 位，有 | ||
| + | |||
| + | $$ | ||
| + | g(i,j,k)\gets j\times g(i-1,j-1,k-1) | ||
| + | $$ | ||
| + | |||
| + | 最后设 $h(i,j)$ 表示有 $j$ 个叶子的 $i$ 标号树的直径之和。同样假设上一步操作删除了 $k(k\ge j)$ 个叶子。 | ||
| + | |||
| + | 考虑原有的树的直径和操作带来的直径 $+2$ 的新贡献，于是有 | ||
| + | |||
| + | $$ | ||
| + | h(i+k,k)\gets g(i,j,k){i+k\choose i}(h(i,j)+2f(i,j)) | ||
| + | $$ | ||
| + | |||
| + | 另外所有 $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 查看代码> | ||
| + | <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]; | ||
| + | int C(int n,int m){ | ||
| + | return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod; | ||
| + | } | ||
| + | int f[MAXN][MAXN],g[MAXN][MAXN][MAXN],h[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; | ||
| + | g[0][0][0]=1; | ||
| + | _rep(i,1,n){ | ||
| + | g[i][0][0]=1; | ||
| + | _rep(k,1,n) | ||
| + | g[i][0][k]=1LL*g[i][0][k-1]*i%mod; | ||
| + | _rep(j,1,i)_rep(k,j,n) | ||
| + | g[i][j][k]=(1LL*g[i][j][k-1]*i+1LL*g[i-1][j-1][k-1]*j)%mod; | ||
| + | } | ||
| + | f[1][1]=f[2][2]=1; | ||
| + | _rep(i,1,n)_rep(j,1,i)_rep(k,max(j,2),n-i) | ||
| + | f[i+k][k]=(f[i+k][k]+1LL*f[i][j]*g[i][j][k]%mod*C(i+k,i))%mod; | ||
| + | h[2][2]=1; | ||
| + | _rep(i,3,n)_rep(j,1,i) | ||
| + | h[i][j]=2LL*f[i][j]%mod; | ||
| + | _rep(i,1,n)_rep(j,1,i)_rep(k,max(j,2),n-i) | ||
| + | h[i+k][k]=(h[i+k][k]+1LL*h[i][j]*g[i][j][k]%mod*C(i+k,i))%mod; | ||
| + | int ans=0; | ||
| + | _rep(i,1,n) | ||
| + | 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); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== G. Game of Death ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 一个游戏，有 $n$ 名玩家。每个玩家等概率选择一名除自己以为的人进行射击，射击的命中率为 $p$。 | ||
| + | |||
| + | 对每个 $k=1\sim n$ ，询问最后存活 $k$ 人的概率。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 设 $f(k)$ 表示固定 $k$ 个人的集合，这 $k$ 个人全部死亡的概率。$g(k)$ 表示固定 $k$ 个人的集合，死亡的人是这个集合的子集的概率。 | ||
| + | |||
| + | 首先考虑计算 $g(k)$，事实上可以把所有人分成两种人，一种是在这个 $k$ 人集合中的人，记为 $A$ 类人。另一种记为 $B$ 类人。 | ||
| + | |||
| + | 于是只需要保证不杀死 $B$ 类人即可。于是对 $A$ 类人，这个概率为 $1-\frac {p(n-k)}{n-1}$。而对于 $B$ 类人，这个概率为 $1-\frac {p(n-1-k)}{n-1}$。 | ||
| + | |||
| + | 于是有 | ||
| + | |||
| + | $$ | ||
| + | g(k)=\left(1-\frac {p(n-k)}{n-1}\right)^k\left(1-\frac {p(n-1-k)}{n-1}\right)^{n-k} | ||
| + | $$ | ||
| + | |||
| + | 同时有 $g(k)=\sum_{i=0}^k {k\choose i}f(i)$，根据二项式反演，得 | ||
| + | $$ | ||
| + | f(k)=\sum_{i=0}^k (-1)^{k-i}{k\choose i}g(i)=k!\sum_{i=0}^k\frac{(-1)^{k-i}}{(k-i)!}\frac{g(i)}{i!} | ||
| + | $$ | ||
| + | 卷积计算即可，最终 $k$ 人死亡的答案为 ${n\choose k}f(k)$。时间复杂度 $O(n\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e5+5,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; | ||
| + | } | ||
| + | namespace Poly{ | ||
| + | const int G=3,Mod=998244353; | ||
| + | int rev[MAXN<<2],Wn[30][2]; | ||
| + | void init(){ | ||
| + | int m=Mod-1,lg2=0; | ||
| + | while(m%2==0)m>>=1,lg2++; | ||
| + | Wn[lg2][1]=quick_pow(G,m); | ||
| + | Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2); | ||
| + | while(lg2){ | ||
| + | m<<=1,lg2--; | ||
| + | Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod; | ||
| + | Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod; | ||
| + | } | ||
| + | } | ||
| + | int build(int k){ | ||
| + | int n,pos=0; | ||
| + | while((1<<pos)<=k)pos++; | ||
| + | n=1<<pos; | ||
| + | _for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1)); | ||
| + | return n; | ||
| + | } | ||
| + | void NTT(int *f,int n,bool type){ | ||
| + | _for(i,0,n)if(i<rev[i]) | ||
| + | swap(f[i],f[rev[i]]); | ||
| + | int t1,t2; | ||
| + | for(int i=1,lg2=0;i<n;i<<=1,lg2++){ | ||
| + | int w=Wn[lg2+1][type]; | ||
| + | for(int j=0;j<n;j+=(i<<1)){ | ||
| + | int cur=1; | ||
| + | _for(k,j,j+i){ | ||
| + | t1=f[k],t2=1LL*cur*f[k+i]%Mod; | ||
| + | f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod; | ||
| + | cur=1LL*cur*w%Mod; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(!type){ | ||
| + | int div=quick_pow(n,Mod-2); | ||
| + | _for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod; | ||
| + | } | ||
| + | } | ||
| + | void mul(int *f,int _n,int *g,int _m){ | ||
| + | int n=build(_n+_m-2); | ||
| + | _for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0; | ||
| + | NTT(f,n,1);NTT(g,n,1); | ||
| + | _for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod; | ||
| + | NTT(f,n,0); | ||
| + | } | ||
| + | } | ||
| + | int frac[MAXN],invf[MAXN]; | ||
| + | int C(int n,int m){ | ||
| + | return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod; | ||
| + | } | ||
| + | int f[MAXN<<2],g[MAXN<<2]; | ||
| + | int main() | ||
| + | { | ||
| + | Poly::init(); | ||
| + | int n=read_int(),a=read_int(),b=read_int(); | ||
| + | int p=1LL*a*quick_pow(b,mod-2)%mod; | ||
| + | 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 div=quick_pow(n-1,mod-2); | ||
| + | _rep(i,0,n){ | ||
| + | LL t1=1-1LL*p*(n-i)%mod*div; | ||
| + | LL t2=1-1LL*p*(n-1-i)%mod*div; | ||
| + | g[i]=1LL*quick_pow(t1%mod,i)*quick_pow(t2%mod,n-i)%mod; | ||
| + | g[i]=1LL*g[i]*invf[i]%mod; | ||
| + | f[i]=(i&1)?-invf[i]:invf[i]; | ||
| + | } | ||
| + | Poly::mul(f,n+1,g,n+1); | ||
| + | _rep(i,0,n) | ||
| + | f[i]=1LL*f[i]*frac[i]%mod*C(n,i)%mod; | ||
| + | _rep(i,0,n) | ||
| + | enter(f[n-i]); | ||
| + | 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> | ||
| + | </hidden> | ||
| ===== J. Illuminations ===== | ===== J. Illuminations ===== | ||
| 行 785: | 行 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.1629171562.txt.gz · 最后更改: 2021/08/17 11:39 由 王智彪
