冲刺CSP联训模拟2
过T2了，赢了
T3 T4 暴力没写满，输了
A 挤压
我是唐诗老哥一个半小时才过 T1
发现要求的是 \(E(s^2)\)，因为有个异或，所以直接考虑拆贡献到每一位
\[E(s^2)=E(\sum s_i \sum s_j)=\sum E(s_i s_j) \]所以直接考虑后面那个咋做，就是 \(i,j\) 位同时是一的时候贡献 \(2^{ij}\) ，发现可以暴力dp做出两位同是一的概率，直接计算期望就完了，是 \(O(n\log^2n)\) 的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
const llt mod=1e9+7;
const llt N=100100;
llt n,a[N],p[N],ans[40],P[40][40],output,inv;
llt qpow(llt a,llt b)
{
llt ret=1,mid=a;
while(b)
{
if(b&1) ret=ret*mid%mod;
mid=mid*mid%mod;
b>>=1;
}
return ret;
}
llt us[N][2][2];
inline llt solve(llt x,llt y)
{
llt A,B;
us[0][0][0]=1;
for(int i=1;i<=n;i++)
{
us[i][0][0]=us[i][0][1]=us[i][1][0]=us[i][1][1]=0;
A=(a[i]>>x)&1,B=(a[i]>>y)&1;
us[i][0^A][1^B]=us[i][0^A][1^B]+us[i-1][0][1]*p[i]%mod+mod,
us[i][0][1]=us[i][0][1]+us[i-1][0][1]*(1-p[i])%mod+mod;
us[i][0^A][0^B]=us[i][0^A][0^B]+us[i-1][0][0]*p[i]%mod+mod,
us[i][0][0]=us[i][0][0]+us[i-1][0][0]*(1-p[i])%mod+mod;
us[i][1^A][0^B]=us[i][1^A][0^B]+us[i-1][1][0]*p[i]%mod+mod,
us[i][1][0]=us[i][1][0]+us[i-1][1][0]*(1-p[i])%mod+mod;
us[i][1^A][1^B]=us[i][1^A][1^B]+us[i-1][1][1]*p[i]%mod+mod,
us[i][1][1]=us[i][1][1]+us[i-1][1][1]*(1-p[i])%mod+mod;
us[i][0][0]%=mod,us[i][0][1]%=mod,us[i][1][0]%=mod,us[i][1][1]%=mod;
}
return us[n][1][1];
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%lld",&n);
for(llt i=1;i<=n;i++) scanf("%lld",&a[i]);inv=qpow(1e9,mod-2);
for(llt i=1;i<=n;i++) scanf("%lld",&p[i]),p[i]=p[i]*inv%mod;
for(llt i=0;i<=31;i++)
{
for(llt j=1;j<=n;j++)
if((a[j]>>i)&1)
ans[i]=((1-ans[i])*p[j]%mod+ans[i]*(1-p[j])%mod+mod+mod)%mod;
output=output+(1ll<<(i*2ll))%mod*ans[i]%mod;output%=mod;
}
for(llt i=0;i<=31;i++)
for(llt j=i+1;j<=31;j++)
output=output+(1ll<<(i+j+1))%mod*solve(i,j)%mod,output%=mod;
printf("%lld\n",output);
return 0;
}
B 工地难题
考虑容斥，直接求最大连续段至少是 \(k\) 的就好了
尝试拿 \(k\) 个 \(1\) 出来，之后还回去，剩下的插板
发现对于一个有 \(x\) 个大于 \(k\) 的连续段的方案恰好计算 \(x\) 遍
所以直接插回去容斥就好了
或者直接转化成 \(n-m+1\) 个自然数相加等于 \(m\)，其中最大的数大于等于 \(k\)，所以直接容斥成所有的减去全小于 \(k\) 的，就是容斥原理板子（这里求最大连续段小于等于 \(k\) 的可以少一步容斥），预处理组合数，发现是调和级数的， \(O(n \log n)\) 做完了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
const llt mod=1e9+7;
const llt N=2000100;
llt n,m,inv[N],tms[N],invt[N],us,ans[N],sum,nd;
llt C(llt a,llt b){if(b>a) return 0;return tms[a]*invt[b]%mod*invt[a-b]%mod;}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%lld%lld",&n,&m);
inv[1]=tms[0]=invt[0]=1;for(int i=2;i<=n;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=n;i++) tms[i]=tms[i-1]*i%mod,invt[i]=invt[i-1]*inv[i]%mod;
for(int k=m;k>=1;k--)
{
nd=0;
for(int i=k;i<=m;i+=k)
{
us=C(m-i+1+n-m-1,n-m);
if((i/k)&1) nd=(nd+C(n-m+1,i/k)*us%mod+mod)%mod;
else nd=(nd-C(n-m+1,i/k)*us%mod+mod)%mod;
}
ans[k]=(nd-sum+mod)%mod,sum=(sum+ans[k])%mod;
}
for(int k=1;k<=m;k++) printf("%lld ",ans[k]);
return 0;
}
C 星空遗迹
好题啊
发现一些结论：
-
我们将相邻两项的胜负关系中胜利看作左括号，失败看作右括号，容易发现如果是合法的括号序列的话答案就是第一个字母，因为括号中间的会被两边吃掉
-
如果不满足关系的话，直接找最靠后的一个落单的右括号，发现这个右括号处就是答案，因为合法的括号匹配完毕后可以当做不存在，之后括号序列长这个样子
））））（（（，发现中间的那个一定是答案
那么就可以直接开栈统计，可以做到 \(O(nq)\)
考虑使用数据结构优化，线段树就可行，将左括号设为 \(1\)，右括号设为 \(-1\)，直接使用线段树维护找那个谷就好了，可以单点修改加线段树二分，也可以维护前缀和，就是后缀修改查区间最小值
复杂度 \(O(q \log n)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
const llt N=2000100;
llt n,q,a,b,w[N],tot,pl;char s[N],c;
int g(char A,char B)
{
if(A=='R'&&B=='P') return -1;
if(A=='P'&&B=='R') return 1;
if(A=='P'&&B=='S') return -1;
if(A=='S'&&B=='P') return 1;
if(A=='R'&&B=='S') return 1;
if(A=='S'&&B=='R') return -1;
return 0;
}
struct SEGMENT_TREE
{
llt node[N<<2],sum[N<<2];
#define mid ((st+ed)>>1)
llt is,L,R,sigma;
void change(llt now,llt st,llt ed,llt x,llt p)
{
if(st==ed) {node[now]=min(0ll,p),sum[now]=p;return;}
if(x<=mid) change(now<<1,st,mid,x,p);
else change((now<<1)|1,mid+1,ed,x,p);
sum[now]=sum[now<<1]+sum[(now<<1)|1];
node[now]=min(node[now<<1],node[(now<<1)|1]+sum[now<<1]);
}
llt find(llt now,llt st,llt ed,llt x,llt y,llt S)
{
if(x<=st&&ed<=y){if(S+node[now]<0) {is=now,L=st,R=ed,sigma=S;return sum[now]-node[now];}return S+sum[now];}
if(x<=mid) S=find(now<<1,st,mid,x,y,S);
if(y>mid) S=find((now<<1)|1,mid+1,ed,x,y,S);
return S;
}
inline llt F(llt x,llt y){if(x+node[y]<0) return sum[y]-node[y];return x+sum[y];}
llt check(llt now,llt st,llt ed,llt S)
{
if(st==ed) return st;
if(node[(now<<1)|1]+F(S,now<<1)<0) return check((now<<1)|1,mid+1,ed,F(S,now<<1));
else return check(now<<1,st,mid,S);
}
char Query(llt a,llt b)
{
is=L=R=sigma=0;
find(1,1,n,a,b,0);
if(is==0) return s[a];
return s[check(is,L,R,sigma)+1];
}
}s_tree;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%lld%lld",&n,&q);
scanf("%s",s+1);
for(int i=1;i<n;i++) w[i]=g(s[i],s[i+1]),s_tree.change(1,1,n,i,w[i]);
for(int i=1;i<=q;i++)
{
scanf("%lld",&a);
if(a==1)
{
scanf("%lld %c",&b,&c);
s[b]=c;
if(b-1>0) w[b-1]=g(s[b-1],s[b]),s_tree.change(1,1,n,b-1,w[b-1]);
if(b<n) w[b]=g(s[b],s[b+1]),s_tree.change(1,1,n,b,w[b]);
}
else
{
scanf("%lld%lld",&a,&b);
printf("%c\n",s_tree.Query(a,b-1));
}
}
return 0;
}
D 纽带
我要会这个高低得让 xrlong 给我磕一个