【考试总结】2022-03-11
卷王
考虑递推得到所有 \([0,2^{16})\) 的所有答案，将序列差分之后设答案为 \(t\) 在第 \(i\) 秒的操作形式就是将差分序列里面两个相隔 \(i\) 的位置反转
那么将 \(t\) 秒的所有操作反转过来进行 \(\rm DP\) 即可，复杂度 \(\Theta(n^22^n)\)
Code Display
const int N=20;
char s[N];
int n,ans[1<<16],a[N];
bool dp[17][1<<16];
signed main(){
freopen("roll.in","r",stdin); freopen("roll.out","w",stdout);
dp[0][0]=1;
int S=1<<16; --S;
for(int t=0;t<16;++t){
for(int i=0;i<=S;++i) if(dp[t][i]){
dp[t+1][i]=1;
for(int j=1;j<=16;++j){
int nS=i^(1<<(j-1));
if(j+t+1<=16) nS^=1<<(t+j);
dp[t+1][nS]=1;
}
}
}
for(int i=0;i<=S;++i){
for(int t=0;t<16;++t) if(dp[t][i]){ans[i]=t; break;}
}
int T=read(); while(T--){
scanf("%s",s+1); n=strlen(s+1);
reverse(s+1,s+n+1);
if(n<16) rep(i,n+1,16) s[i]='0';
n=16;
reverse(s+1,s+n+1);
rep(i,1,n) a[i]=s[i]-'0';
Down(i,n,1) a[i]^=a[i-1];
int init=0;
Down(i,n,1) init=init<<1|a[i];
print(ans[init]);
}
return 0;
}
赢王
设前缀和数组为 \(s_i\)
考虑在将 \(b_1\) 操作为 \(0\) 之后 \(b_2\) 在模 \(k\) 意义下值是一样的，那么操作前 \(i\) 个数字之后剩下给 \(b_i\) 的是 \(\sum\limits_{j=1}^i \left(s_j\bmod k\right)\)
所以如果长度为 \(i\) 的序列 \(b_1\dots b_i\) 合法那么操作次数最小就是 \(\sum\limits_{j=i}^i \min(s_j\bmod k,k-s_j\bmod k)\)
对这个东西求和是经典问题，使用 \(\text {Fenwick Tree}\) 来维护 \(\mod k\) 每种余数的前缀和的个数和 \(s_i\) 的和
这里个数定义为能造成贡献的区间个数，对于一个前缀模 \(k\) 的余数 \(x\)，一个位置 \(i\) 带来的 \(\min(k-(s_i-x)\mod k,(s_i-x)\mod k)\) 的贡献数量是 \(i\) 前面 \(s_j\equiv x\mod k\) 的 \(j\) 的数量 乘 \(i\) 后面 \(s_j\equiv x\mod k\) 的 \(j\) 的数量
那么扫过一个 \(x\) 时带来的增量是可以计算的，这样子就可以树状数组维护了
在查询的时候每个 \(s_i\) 其它的 \(s_j\) 造成 \(s_i-s_j\in[-k,-\frac k2],(-\frac k2,0],(0,\frac k2],(\frac k2,k]\) 的对答案的贡献形式是不一样的，需要分开讨论计算，平凡但是很难不言繁琐
Code Display
const int N=1e6+10;
int n,ans,a[N],k,sum[N];
int lsh[N],m=1,ton[N];
struct Fenwick_Tree{
int sum[N],cnt[N];
inline void insert(int pos,int num){
int val=mul(num,lsh[pos]);
for(int x=pos;x<=m;x+=x&(-x)) cnt[x]+=num,ckadd(sum[x],val);
return ;
}
inline int query_cnt(int x){
int res=0;
for(;x;x-=x&(-x)) ckadd(res,cnt[x]);
return res;
}
inline int query_sum(int x){
int res=0;
for(;x;x-=x&(-x)) ckadd(res,sum[x]);
return res;
}
}T;
int nowcnt[N];
inline int solve(int l,int r,int coef,int fl){
int cnt=T.query_cnt(r)-T.query_cnt(l-1);
int sum=T.query_sum(r)-T.query_sum(l-1);
return coef*cnt+sum*fl;
}
signed main(){
freopen("win.in","r",stdin); freopen("win.out","w",stdout);
n=read(); k=read();
rep(i,1,n) a[i]=read(),sum[i]=(sum[i-1]+a[i])%k,lsh[++m]=sum[i];
sort(lsh+1,lsh+m+1); m=unique(lsh+1,lsh+m+1)-lsh-1;
ans=-n*(n+1)/2;
rep(i,0,n) sum[i]=lower_bound(lsh+1,lsh+m+1,sum[i])-lsh,ans+=ton[sum[i]],ton[sum[i]]++;
T.insert(sum[0],--ton[sum[0]]); nowcnt[1]=1;
for(int i=1;i<=n;++i){
ans+=solve(lower_bound(lsh+1,lsh+m+1,lsh[sum[i]]-k/2)-lsh,sum[i],lsh[sum[i]],-1);
ans+=solve(lower_bound(lsh+1,lsh+m+1,lsh[sum[i]]+(k+1)/2)-lsh,m,lsh[sum[i]]+k,-1);
ans+=solve(1,upper_bound(lsh+1,lsh+m+1,lsh[sum[i]]-k/2-1)-lsh-1,k-lsh[sum[i]],1);
ans+=solve(sum[i]+1,upper_bound(lsh+1,lsh+m+1,lsh[sum[i]]+(k+1)/2-1)-lsh-1,-lsh[sum[i]],1);
ton[sum[i]]--; nowcnt[sum[i]]++;
int deltnum=ton[sum[i]]-nowcnt[sum[i]]+1;
T.insert(sum[i],deltnum);
}
ans=(ans%mod+mod)%mod;
print(ans);
return 0;
}
稳王
不难发现最优策略是把牌攒到能一次杀掉 \(\text{boss}\) 再一起打出
问题本质上是计算每种不能杀死 \(\text{boss}\) 的牌型的出现概率之和加 \(1\)，那么分为如下若干种情况讨论即可：
-
全拿到复读牌：\(\sum\limits_{i=1}^{+\infty}\frac{1}{3^i}=\frac 12\)
-
全部为毒药牌，不到 \(n+1\) 张不能获胜：\(\sum\limits_{i=1}^{n} \frac 1{3^i}\)
-
全部为火球牌，不拿到 \(m=\lfloor\frac{n-1}2\rfloor\) 不能获胜：\(\sum\limits_{i=1}^{m}\frac{1}{3^i}\)
-
同时有毒药和火球牌，先出一张毒药，那么可以将答案表示为 \(F(x)=\sum\limits_{i=1}^{+\infty} \left(\frac13(x+x^3)\right)^i,Ans=\sum\limits_{i=1}^n[x^i]F(x)\)
但是这里并不能保证毒药和火球都被拿到了，所以要分别减掉 \(F'(x)=\sum\limits_{i=1}^{+\infty} \left(\frac13x\right)^i\) 和 \(F'(x)=\sum\limits_{i=1}^{+\infty} \left(\frac13x^3\right)^i\) 的前 \(n\) 项系数和
这里需要满足多出来一张毒药牌，所以可以将 \(n\leftarrow n+1\) 再做
-
同时有毒药和复读牌，本质相同，这里的项变成了 \(\sum (x+x^2)^i\)，容斥的方式也和上面完全一样
-
同时有 \(3\) 张牌，本质仍然相同，项变成了 \(\sum (x+x^3+x^4)^i\)，算 \(7\) 次而已
注意单项没必要矩阵快速幂，可以直接等比数列求和
不需要预处理向量也是可以通过的
Code Display
templatestruct Matrix{
int a[N][N]; Matrix(){memset(a,0,sizeof(a));}
Matrix operator *(const Matrix &b)const{
Matrix res;
rep(i,0,N-1) rep(k,0,N-1) rep(j,0,N-1) ckadd(res.a[i][j],mul(a[i][k],b.a[k][j]));
return res;
}
inline void init(){
for(int i=0;i>=1; c=c*c;
} return b;
}
};
const int inv2=(mod+1)/2,inv3=ksm(3,mod-2);
inline int calc(int x){
//sigma i in [1,x] 1/(3^i)
return mul(inv2,del(1,ksm(inv3,x)));
}
signed main(){
freopen("stable.in","r",stdin); freopen("stable.out","w",stdout);
int T=read(); while(T--){
int n=read(),m=(n-1)/2,ans=inv2; //first type
ckadd(ans,calc(m)); //third type
ckdel(ans,del(1,ksm(inv3,m))); //sixth type
ckadd(ans,mul(2,del(1,ksm(mul(2,inv3),m))));
Matrix<3>a; //fourth type
a.a[0][2]=a.a[1][0]=a.a[2][2]=1;
a.a[0][1]=a.a[1][1]=inv3;
a=a.qpow(n);
ckadd(ans,add(mul(4,mul(mul(inv3,inv3),a.a[1][2])),mul(inv3,a.a[0][2])));
ckdel(ans,calc(n/2));
Matrix<4>b; //fifth type
b.a[1][0]=b.a[2][1]=b.a[3][3]=1;
b.a[0][3]=b.a[2][3]=b.a[0][2]=b.a[2][2]=inv3;
ckadd(ans,b.qpow(n).a[2][3]);
Matrix<5>c; //seventh type
c.a[1][0]=c.a[2][1]=c.a[3][2]=c.a[4][4]=1;
c.a[0][3]=c.a[1][3]=c.a[3][3]=inv3;
c.a[0][4]=c.a[1][4]=c.a[3][4]=inv3;
ckadd(ans,c.qpow(n).a[3][4]);
c.a[3][3]=c.a[3][4]=0;
ckdel(ans,c.qpow(n).a[3][4]);
c.a[3][3]=c.a[3][4]=inv3;
c.a[1][3]=c.a[1][4]=0;
ckdel(ans,c.qpow(n).a[3][4]);
c.a[1][3]=c.a[1][4]=inv3;
c.a[0][3]=c.a[0][4]=0;
ckdel(ans,c.qpow(n).a[3][4]);
ckadd(ans,calc(n/4));
print(add(ans,1));
}
return 0;
}