2020-2021:teams:legal_string:组队训练比赛记录:contest16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/17 10:39] jxm2001 |
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 | 0 | | + | | J | 2 | 0 | 2 | |
| - | | K | 0 | 0 | 0 | | + | | K | 2 | 1 | 0 | |
| ====== 题解 ===== | ====== 题解 ===== | ||
| - | ===== J. Illuminations ===== | + | ===== 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 ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给一个凸多边形，和凸多边形外侧若干个点，每个点作为一盏灯，向四面八方发出光线，让用最少的点照亮平面除凸包内部外所有区域，如果不存在方案输出 $-1$ 。 | ||
| ==== 题解 ==== | ==== 题解 ==== | ||
| 这题可以分成两个部分，一个是求凸包切线部分，一个是求环区间最小覆盖部分。 | 这题可以分成两个部分，一个是求凸包切线部分，一个是求环区间最小覆盖部分。 | ||
| + | |||
| + | 我们注意到，一个点能照亮的最大区域是这个点对于这个凸包求左右两条切线，然后点亮所有区域的等价条件是所有边都被一个点的两条切线夹起来过，求切线就是一个二分的板子，然后这个问题就转化为环形结构内给若干个线段（可以跨过原点），求最少的线段的数量，覆盖 $1$ 到 $n$ 的所有点。 | ||
| 关于求环区间最小覆盖部分，首先肯定是断环成链，然后枚举 $i=1\sim n$ 区间 $[i,i+n)$ 的最小线段覆盖，但这是 $O\left(n^2\right)$ 的，有以下几种解法。 | 关于求环区间最小覆盖部分，首先肯定是断环成链，然后枚举 $i=1\sim n$ 区间 $[i,i+n)$ 的最小线段覆盖，但这是 $O\left(n^2\right)$ 的，有以下几种解法。 | ||
| 行 461: | 行 1077: | ||
| 关于淘汰被另一条线段完全包含的线段，也可以利用桶排等技巧 $O(n)$ 实现。 | 关于淘汰被另一条线段完全包含的线段，也可以利用桶排等技巧 $O(n)$ 实现。 | ||
| + | |||
| + | 关于为什么选最短的线段的每个位置作为起点可以保证得到最优解，本人无法证明。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 781: | 行 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.1629167956.txt.gz · 最后更改: 2021/08/17 10:39 由 jxm2001
