D
给定两个长度为 $n(1\leq n\leq 2000)$ 的 $0/1$ 串，对 $A$ 执行任意次一下操作的任意一种：
- 将 $A$ 左移一位，即 $A\leftarrow A_2A_3…A_nA_1$
- 将 $A$ 右移一位，即 $A\leftarrow A_nA_1AA_2…A_{n-1}$
- 选择任意 $i$ 满足 $B_i=1$ ，令 $A_i=1-A_i$
求最少需要多少次操作
首先当 $A$ 有 $1$ ，$B$ 没有 $1$ 那么一定无解。当 $A,B$ 均没有 $1$ 时代价为 $0$
其余情况 $B$ 中一定有 $1$ ，将$A$的环状移动用将 $B$ 左右倍长为 $3$ 倍，$A$ 直接左右移动。
对于 $A$ 中每一个位置 $i$ ，预处理每一个 $i$ 需要向左向右最少移动多少步才能使得 $A_i$ 对应了一个 $B_j$ 使得 $B_j=1$ ，记为 $L_i,R_i$
其次，考虑暴力枚举最终 $A$ 在与原来的相对位置与 $B$ 对应，假设 $A$ 与原来的位置相对向右移动了 $k$ 个，然后对于每一个 $A_i \not = B_{i+k}$ ，我们至少将 $A$ 左移 $L_i$ 位或右移 $R_i$
假设我们最终要向右移动 $k$ 位与 $B$ 对应，考虑枚举先向左走了 $x$ 步，那么对于所有 $L_i\leq x$ 对答案无影响了，只需要统计对 $L_i>x$ 的 $R_i$ 最大值(记为 $RS$ )，即先向左移 $x$ 步再移回来，再向右移到 $RS$ ，最后移到 $k$ 最优
过程中要对每一个 $A_i \not = B_{i+k}$ 的进行一步操作，记为 $m$ 个，用 $2x+RS+|RS-k|+m$ 来更新答案。
将 $A$ 向左移动同理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| const int N=8e3+100;
char s1[N],s2[N];
int n,m,p[N],t[N],L[N],R[N];
int pre[N],suf[N],ls[N],rs[N],ct1,ct2,ans;
inline bool cmp(int x,int y){ return L[x]>L[y] || (L[x]==L[y] && R[x]<R[y]);}
inline void upd(int tar,int hd,int rev,int con){
tar>=hd ? ans=min(ans,rev*2+tar+con) : ans=min(ans,rev*2+(hd*2-tar)+con);
}
int main(){
scanf("%s%s",s1+1,s2+1),n=strlen(s1+1),ans=n*n;
for(rei i=1;i<=n;++i) p[i]=s1[i]-'0',t[i]=t[i+n]=t[i+n+n]=s2[i]-'0';
for(rei i=1;i<=n;++i) ct1+=p[i],ct2+=t[i];
if(!ct2) return puts(ct1 ? "-1" : "0"),0;
for(rei i=1;i<=n+n;++i) if(!t[i]) ls[i]=(ls[i-1]+1);
for(rei i=n+n+n;i>n;--i) if(!t[i]) rs[i]=(rs[i+1]+1);
for(rei k=0;k<=n;++k){
m=0;
memset(pre,0,sizeof pre),memset(suf,0,sizeof suf);
for(rei i=1;i<=n;++i){
if(p[i]^t[i+k]){
++m; if(t[i+k]) continue;
pre[ ls[i+n] ]=max(pre[ ls[i+n] ],rs[i+n]);
suf[ rs[i+n] ]=max(suf[ rs[i+n] ],ls[i+n]);
}
}
for(rei i=n-1;i>=0;--i) suf[i]=max(suf[i],suf[i+1]),pre[i]=max(pre[i],pre[i+1]);
for(rei i=0;i<n;++i) upd(k,pre[i+1],i,m),upd(n-k,suf[i+1],i,m);
}
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|
E
给定长度 $n (1\leq n\leq 10^4)$ 的 $0/1$ 串 $A,B$ ，两个串均有 $k$ 个 $1$ ，令 $a_{1\sim k},b_{1\sim k}$ 分别表示 $AB$ 中所有 $1$ 出现的位置。 将 $a,b$ 等概率随机排列，按 $1\sim k$ 的顺序交换 $A_{a_i},B_{b_i}$ ，设 $P$ 表示操作后 $AB$ 相等的概率，求 $P\times k^2$ 在模 $998244353$ 意义下的值
定义 $A_i=1 \land B_i=0$ 的 $i$ 为富余点，能为其他位置提供 $1$ ；$A_i=B_i=1$ 的 $i$ 为公共点，可以传递 $1$ ；$A_i=0 \land B_i=1$ 的位置为缺失点，富余点需要移动到那里
考虑 $dp$ ：设 $f(i,j)$ 表示在传递链中用了 $i$ 个公共点， $j$ 个富余点时传递链中的方案数，有转移： $\displaystyle {f(i,j)=f(i-1,j)\times ij+f(i,j-1)\times j^2}$
即：将一个公共点加入一条传递链的末尾： $j$ 条链中，新的点可以与已有的 $i-1$ 个点交换链中的位置 + 新建一条链：拿出新的一对缺失-富余点，考虑到可以与原来的点交换位置，系数 $j^2$
最后统计，公共点没有必要用完，设链中用了 $a$ 个公共点，还剩 $b$ 个，方案数 $\binom{a+b}{b}$ ；公共点内部方案 $(b!)^2$ ； $b$ 次操作安排进 $k$ 次操作里，方案数 $\binom{k}{b}$ 。设公共点 $s$ ，富余点 $t$ ，答案为： $\displaystyle{\sum_{t=0}^s \binom{s}{i}\times \binom{s+t}{i}\times (i!)^2\times f_{s-i,t}}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| const int N=1e4+100;
const int mod=998244353;
int n,sur,bal,f[N][N],fac[N],fac_inv[N],ans;
char A[N],B[N];
inline void fix(int &x){ x>=mod ? x-=mod : 0;}
inline int mul(ll a,const int b){ return(a*=b)<mod ? a : a%mod;}
inline int qpow(int a,int b){ int res=1;while(b){ if(b&1) res=(ll) res*a%mod;a=(ll) a*a%mod;b>>=1;} return res;}
inline int get_C(int x,int y){ return x<y ? 0 : (ll) fac[x]*((ll) fac_inv[y]*fac_inv[x-y]%mod)%mod;}
inline void init(){
fac[0]=1;
for(rei i=1;i<=n;++i)fac[i]=mul(i,fac[i-1]);
fac_inv[n]=qpow(fac[n],mod-2);
for(rei i=n-1;~i;--i)fac_inv[i]=mul(i+1,fac_inv[i+1]);
}
int main(){
scanf("%s%s",A+1,B+1),n=strlen(A+1);
init();
for(rei i=1;i<=n;++i){
if(A[i]^'0' && B[i]^'0') ++bal;
else if(A[i] > B[i]) ++sur;
}
f[0][0]=1;
for(rei i=0;i<=bal;++i){
for(rei j=0,cur;j<=sur;++j){
if(!(cur=f[i][j])) continue;
fix(f[i+1][j]+=mul(cur,mul(i+1,j)));
fix(f[i][j+1]+=mul(cur,mul(j+1,j+1)));
}
}
for(rei i=0;i<=bal;++i){
rei fre=bal-i;
rei self=mul(mul(fac[fre],fac[fre]), mul(get_C(bal+sur,fre),get_C(bal,fre)));
fix(ans+=mul(f[i][sur],self));
}
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|
F
$N+M$ 个问题，其中 $N$ 个问题的答案为 $Yes$ ，$M$ 个答案的问题为 $No$ ，且这些问题的排列均匀随机。 依次回答每一个问题，回答完该问题后会得知答案，在最优策略下，最多能期望蒙对多少题
显然有 $N>M$ 时，下一个问题需要贪心猜 $Yes$
而当 $N=M$ 时，两种的期望相同，不妨均猜 $Yes$
考虑如何统计：当 $N=M$ 时猜对一道题，称这个为好运题，其他猜对的称为平凡题
有一个比较显然的性质：不论题目的排列顺序，平凡题的数量始终为 $\max\{N,M\}$
应该由归纳法易得对吧
于是由期望的线性得，只需要统计好运题的数量即可，且只需要对于每个 $i=i,2,…,\min\{N,M\}$，求出有 $\frac{p_i}{2}$ 的概率遇到 $i$ 道对 $i$ 道错的题并将该题蒙对，最后对于每个 $i$ ，将这样的概率相加即得好运题的数量期望。
如果我们把 $(N,M)$ 看成坐标平面上的一个整点，那么整个过程可以看成一条 $HV$ 格路，由顺序均匀随机可知，在所有 $\binom{N+M}{N}$ 条 $HV$ 格路中，每条格路出现的概率均相等。
而我们就是要统计这条 $HV$ 格路经过点 $(i,i)$ 的概率，因而只需统计经过这个点的格路个数。
由二项式系数得：$\displaystyle{p_i=\frac{\binom{2\times i}{i}\times \binom{(N-i)+(M-i)}{N-i}}{\binom{N+M}{N}}}$
最终答案就是 $\frac{1}{2}\sum_{i>1} p_i +\max\{N,M\}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| const int N=1e6+100;
const int mod=998244353,iv2=(mod+1)/2;
int A,B,n,ans;
int fac[N],fac_inv[N];
inline ll qpow(ll a,int n,ll c=1){ for(;n;n>>=1,a=a*a%mod) if(n&1) c=c*a%mod; return c;}
inline ll get_C(int a,int b){ return (ll) fac[a+b]*fac_inv[a]%mod *fac_inv[b]%mod;}
inline ll get_C_inv(int a,int b){ return (ll) fac_inv[a+b]*fac[a]%mod *fac[b]%mod;}
inline void init(int n){
fac[0]=1;
for(rei i=1;i<=n;++i) fac[i]=(ll) fac[i-1]*i%mod;
fac_inv[n]=qpow(fac[n],mod-2);
for(rei i=n;i;--i) fac_inv[i-1]=(ll) fac_inv[i]*i%mod;
}
int main(){
scanf("%d%d",&A,&B),n=std::min(A,B);
init(A+B);
for(rei i=1;i<=n;++i) ans=(ans+get_C(i,i)*get_C(A-i,B-i)%mod)%mod;
ans=(ans*get_C_inv(A,B)%mod*iv2%mod+(A^B^n))%mod;
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|