SDOI一轮省集部分题目题解
绝顶我为峰
2021-05-03 17:59:00
正在补题中……
# Day1
## T1 数排列
[原题](http://codeforces.com/gym/102978/problem/I)
考虑发掘序列 $x$ 的性质，不难发现这个序列生成方式是现在 $[1,n-m]$ 中选一个最小值 $x_1$，然后在 $[x_1+1,n-m+1]$ 中选一个最小值 $x_2$，依次类推得到一个序列。
我们发现对于 $x_{i-1}$ 和 $x_i$，他们只有 $n-m+1$ 位置上的选取是有差异的，也就是说，在 $[x_{i-1}+1,n-m+i-1]$ 这段区间里的数字是两个位置的**公共选择区域**，那么根据贪心的构造原则，这些数字里面较小的会优先被选走。
那么我们发现如果 $x_{i-1}>x_i$ 那么 $x_i$ 一定不在 $x_{i-1}$ 的选择范围内，也就是第 $n-m+i$ 位。
同时我们喜闻乐见的发现后面的数字都没有选择余地了，不需要管他们。所以我们可以把第一个 $x_{i-1}>x_i$ 以后的位置全部确定下来。
未被确定的 $1\sim i$ 是个单调上升的序列，根据贪心构造容易得到 $x_1$ 之前的数字都大于 $x_1$，$x_1\sim x_2$ 之间的数都大于 $x_2$，……，$x_m$ 之后的数大于 $x_m$。
那么我们对于不在 $x$ 中的数字，直接在 $x$ 上找到可以插入的范围，从小到大找可以省去二分。注意到插入的绝对位置并不影响结果，我们可以直接连乘统计答案。
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int mod=998244353;
int n,m,a[250001],ans,p[250001],flag,cnt;
signed main()
{
//freopen("permutation.in","r",stdin);
//freopen("permutation.out","w",stdout);
scanf("%lld%lld",&n,&m);
flag=m;
for(register int i=1;i<=m;++i)
{
scanf("%lld",&a[i]);
p[a[i]]=i;
if(flag==m&&a[i]<a[i-1])
flag=i-1;
}
ans=1;
int pos=1;
for(register int i=1;i<=n;++i)
if(!p[i])
{
if(i<a[1])
{
puts("0");
return 0;
}
while(pos<flag&&i>a[pos+1])
++pos;
if(pos==flag)
++pos;
ans=(ans*(pos+cnt))%mod;
++cnt;
}
printf("%lld\n",ans);
return 0;
}
```
---
## T2 取石子游戏
[原题](http://codeforces.com/gym/102992/problem/J)
根据 $Nim$ 游戏显然有 $sum=\otimes_{i=l}^r=x$ 时答案为 $0$，否则答案为 $\sum_{i=l}^r[a_i\otimes sum\otimes x<a_i]+[sum<x]$
发现这个条件成立的充要条件是 $a_i$ 在 $sum\otimes x$ 的最高位为 $1$，考虑用线段树维护每一位为 $1$ 的数量。
区间 $\max$ 操作是经典的吉司机线段树，直接套上即可。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int n,q,a[200001],minn[200001<<2][2],cnt[200001<<2],sum[200001<<2],ans[200001<<2][31],tag[200001<<2];
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline int ls(int k)
{
return k<<1;
}
inline int rs(int k)
{
return k<<1|1;
}
inline void push_up(int k)
{
sum[k]=sum[ls(k)]^sum[rs(k)];
if(minn[ls(k)][0]<minn[rs(k)][0])
{
minn[k][0]=minn[ls(k)][0];
cnt[k]=cnt[ls(k)];
if(minn[ls(k)][1]<minn[rs(k)][0])
minn[k][1]=minn[ls(k)][1];
else
minn[k][1]=minn[rs(k)][0];
}
else if(minn[ls(k)][0]>minn[rs(k)][0])
{
minn[k][0]=minn[rs(k)][0];
cnt[k]=cnt[rs(k)];
if(minn[ls(k)][0]<minn[rs(k)][1])
minn[k][1]=minn[ls(k)][0];
else
minn[k][1]=minn[rs(k)][1];
}
else
{
minn[k][0]=minn[ls(k)][0];
cnt[k]=cnt[ls(k)]+cnt[rs(k)];
if(minn[ls(k)][1]<minn[rs(k)][1])
minn[k][1]=minn[ls(k)][1];
else
minn[k][1]=minn[rs(k)][1];
}
for(register int i=0;i<30;++i)
ans[k][i]=ans[ls(k)][i]+ans[rs(k)][i];
}
inline void push_down(int k,int l,int r)
{
if(tag[k])
{
if(tag[k]>minn[ls(k)][0]&&tag[k]<minn[ls(k)][1])
{
for(register int i=0;(1<<i)<=minn[ls(k)][0];++i)
if(minn[ls(k)][0]&(1<<i))
ans[ls(k)][i]-=cnt[ls(k)];
if(cnt[ls(k)]&1)
sum[ls(k)]=sum[ls(k)]^minn[ls(k)][0]^tag[k];
minn[ls(k)][0]=tag[k];
for(register int i=0;(1<<i)<=minn[ls(k)][0];++i)
if(minn[ls(k)][0]&(1<<i))
ans[ls(k)][i]+=cnt[ls(k)];
tag[ls(k)]=tag[k];
}
if(tag[k]>minn[rs(k)][0]&&tag[k]<minn[rs(k)][1])
{
for(register int i=0;(1<<i)<=minn[rs(k)][0];++i)
if(minn[rs(k)][0]&(1<<i))
ans[rs(k)][i]-=cnt[rs(k)];
if(cnt[rs(k)]&1)
sum[rs(k)]=sum[rs(k)]^minn[rs(k)][0]^tag[k];
minn[rs(k)][0]=tag[k];
for(register int i=0;(1<<i)<=minn[rs(k)][0];++i)
if(minn[rs(k)][0]&(1<<i))
ans[rs(k)][i]+=cnt[rs(k)];
tag[rs(k)]=tag[k];
}
tag[k]=0;
}
}
void build(int k,int l,int r)
{
if(l==r)
{
sum[k]=minn[k][0]=a[l];
cnt[k]=1;
minn[k][1]=1<<30;
for(register int i=0;(1<<i)<=a[l];++i)
if(a[l]&(1<<i))
ans[k][i]=1;
return;
}
int mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
push_up(k);
}
void update(int nl,int nr,int l,int r,int k,int p)
{
if(l>=nl&&r<=nr)
{
if(p<=minn[k][0])
return;
if(p>minn[k][0]&&p<minn[k][1])
{
for(register int i=0;(1<<i)<=minn[k][0];++i)
if(minn[k][0]&(1<<i))
ans[k][i]-=cnt[k];
if(cnt[k]&1)
sum[k]=sum[k]^minn[k][0]^p;
minn[k][0]=p;
for(register int i=0;(1<<i)<=minn[k][0];++i)
if(minn[k][0]&(1<<i))
ans[k][i]+=cnt[k];
tag[k]=max(tag[k],p);
return;
}
}
push_down(k,l,r);
int mid=(l+r)>>1;
if(nl<=mid)
update(nl,nr,l,mid,ls(k),p);
if(nr>mid)
update(nl,nr,mid+1,r,rs(k),p);
push_up(k);
}
int query1(int nl,int nr,int l,int r,int k)
{
if(l>=nl&&r<=nr)
return sum[k];
push_down(k,l,r);
int mid=(l+r)>>1,res=0;
if(nl<=mid)
res^=query1(nl,nr,l,mid,ls(k));
if(nr>mid)
res^=query1(nl,nr,mid+1,r,rs(k));
return res;
}
int query2(int nl,int nr,int l,int r,int k,int p)
{
if(l>=nl&&r<=nr)
return ans[k][p];
push_down(k,l,r);
int mid=(l+r)>>1,res=0;
if(nl<=mid)
res+=query2(nl,nr,l,mid,ls(k),p);
if(nr>mid)
res+=query2(nl,nr,mid+1,r,rs(k),p);
return res;
}
int main()
{
n=read(),q=read();
for(register int i=1;i<=n;++i)
a[i]=read();
build(1,1,n);
while(q--)
{
int opt=read(),l=read(),r=read(),x=read();
if(opt==1)
update(l,r,1,n,1,x);
if(opt==2)
{
int s=query1(l,r,1,n,1);
if((s^x)==0)
{
puts("0");
continue;
}
int lg=0;
while((1<<lg)<=(s^x))
++lg;
--lg;
printf("%d\n",query2(l,r,1,n,1,lg)+(bool)(x&(1<<lg)));
}
}
return 0;
}
```
## T3 滑冰
[原题](https://codeforces.com/gym/102059/problem/B)
对于任意一个横向或纵向连续的没有障碍的区间，我们显然可以讲这个区间全都走过再继续移动，这样显然是不劣的。
那么我么考虑把每一个这样的连续区间看做一个点，那么只有在拐角两点才能连边。
发现我们要找到一个条链使得这些链经过所有关键点。对于每个关键点，横向和纵向至少要有一个点被经过，才能满足要求。
这很像 $2-SAT$ 模型，我们可以建图。首先对于关键点所在的区间至少选一个，如果有两个区间互相都不能到达，那么他们不能同时选。如果起点所在的两个区间都不能到达某个区间，那么这个区间不能选。
这样所有区间构成全序关系，这个图存在 $2-SAT$ 则原问题一定有解，反之一定无解。
那么我们建出图跑 $2-SAT$ 就好了。
```cpp
#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;
stack<int> t;
int sx,sy,res,tot,T,n,m,dfn[5001],low[5001],cnt,inq[5001],color[5001],a[51][51],b[51][51];
bool vis[2501][2501];
char mp[51][51];
vector<int> e[5001],v[5001];
inline bool check(int x,int y)
{
return mp[x][y]=='o'||mp[x][y]=='.'||mp[x][y]=='S';
}
void tarjan(int k)
{
dfn[k]=low[k]=++cnt;
t.push(k);
inq[k]=1;
for(register int i=0;i<(int)(e[k].size());++i)
if(!dfn[e[k][i]])
{
tarjan(e[k][i]);
low[k]=min(low[k],low[e[k][i]]);
}
else
if(inq[e[k][i]])
low[k]=min(low[k],dfn[e[k][i]]);
if(low[k]==dfn[k])
{
color[k]=++res;
while(!t.empty()&&t.top()!=k)
{
inq[t.top()]=0;
color[t.top()]=res;
t.pop();
}
if(!t.empty())
t.pop();
}
inq[k]=0;
}
void dfs(int k,int s)
{
vis[s][k]=1;
for(register int i=0;i<(int)(v[k].size());++i)
if(!vis[s][v[k][i]])
dfs(v[k][i],s);
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof a);
memset(b,0,sizeof b);
memset(mp,0,sizeof mp);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(inq,0,sizeof inq);
memset(color,0,sizeof color);
memset(vis,0,sizeof vis);
scanf("%d%d",&n,&m);
for(register int i=0;i<=5000;++i)
{
e[i].clear();
v[i].clear();
}
while(!t.empty())
t.pop();
sx=sy=tot=cnt=res=0;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
{
mp[i][j]=getchar();
while(mp[i][j]!='#'&&mp[i][j]!='.'&&mp[i][j]!='S'&&mp[i][j]!='o')
mp[i][j]=getchar();
}
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
if(check(i,j))
{
a[i][j]=check(i,j-1)? a[i][j-1]:++tot;
b[i][j]=check(i-1,j)? b[i-1][j]:++tot;
if(mp[i][j]=='o')
{
e[(a[i][j]<<1)-1].push_back(b[i][j]<<1);
e[(b[i][j]<<1)-1].push_back(a[i][j]<<1);
}
if(mp[i][j]=='S')
{
sx=a[i][j];
sy=b[i][j];
}
if(!check(i,j-1)||!check(i,j+1))
v[a[i][j]].push_back(b[i][j]);
if(!check(i-1,j)||!check(i+1,j))
v[b[i][j]].push_back(a[i][j]);
}
for(register int i=1;i<=tot;++i)
{
dfs(i,i);
for(register int j=1;j<i;++j)
if(!vis[i][j]&&!vis[j][i])
{
e[i<<1].push_back((j<<1)-1);
e[j<<1].push_back((i<<1)-1);
}
}
for(register int i=1;i<=tot;++i)
if(!vis[sx][i]&&!vis[sy][i])
e[i<<1].push_back((i<<1)-1);
for(register int i=1;i<=(tot<<1);++i)
if(!dfn[i])
tarjan(i);
bool flag=1;
for(register int i=1;i<=tot;++i)
if(color[i<<1]==color[(i<<1)-1])
{
flag=0;
puts("No");
break;
}
if(flag)
puts("Yes");
}
return 0;
}
```
# Day2
## T1 我已经完全理解了 DFS 序线段树
~~终于在考场上切了一题~~
[到这里评测](https://www.luogu.com.cn/problem/T177352 )
我们对一个点进行一次操作，意味着我们把这个子树里的叶子同其他叶子区分开来，显然操作**恰好**有叶子数量个。
考虑维护要在哪些点上操作，从下向上维护信息，叶子结点预先选中，然后对于非叶子节点，我们可以在当前点进行一次操作，代替一次**在该节点子树中，且两点路径上没有其他要操作的点**的点上的一次操作。显然我们要换掉花费最大的，于是要用到可并堆.
然而现场问小粉兔，兔说不能用 pb_ds 偷鸡，所以写了个左偏树。
然后我们把儿子的堆上传给父亲并合并，然后拿堆顶和当前点花费比较，如果当前点花费更小就换掉，同时其他的节点不能再被替换，直接清空堆并打上标记，最后遍历根节点的堆打标记，求出需要操作哪些点
然后构造方案，dfs一遍整棵树，维护一个变量每到一个标记点就 +1，变量的值即为子树内叶子目标权值的最小值，然后我们用这个值减去在当前点到根的路径上已经加上的数值即可。
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct edge
{
int nxt,to;
}e[200001<<1];
int n,tot,cnt,res,v[200001],h[200001],ans,s[200001],root[200001];
bool used[200001];
struct tree
{
int lc,rc,dis,val,fa,node;
}t[200001<<1];
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline void add(int x,int y)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
}
int merge(int x,int y)
{
if(!x)
return y;
if(!y)
return x;
if(t[x].val<t[y].val||(t[x].val==t[y].val&&x>y))
swap(x,y);
t[x].rc=merge(t[x].rc,y);
t[t[x].rc].fa=x;
if(t[t[x].lc].dis<t[t[x].rc].dis)
swap(t[x].lc,t[x].rc);
t[x].dis=t[x].rc? t[t[x].rc].dis+1:0;
return x;
}
inline int insert(int x,int node,int val)
{
t[++cnt].val=val;
t[cnt].node=node;
return merge(cnt,x);
}
inline int del(int x)
{
int l=t[x].lc,r=t[x].rc;
t[x].dis=t[x].lc=t[x].rc=t[x].val=t[x].node=0;
return merge(l,r);
}
/*void check(int k)
{
cerr<<t[k].node<<" ";
if(t[k].lc)
check(t[k].lc);
if(t[k].rc)
check(t[k].rc);
}*/
void dfs_tree(int k)
{
used[t[k].node]=1;
if(t[k].lc)
dfs_tree(t[k].lc);
if(t[k].rc)
dfs_tree(t[k].rc);
}
void dfs1(int k,int f)
{
bool flag=1;
for(register int i=h[k];i;i=e[i].nxt)
{
if(e[i].to==f)
continue;
flag=0;
dfs1(e[i].to,k);
s[k]+=s[e[i].to];
if(!root[k])
root[k]=root[e[i].to];
else
root[k]=merge(root[k],root[e[i].to]);
}
if(flag)
{
s[k]=1;
root[k]=++cnt;
t[root[k]].val=v[k];
t[root[k]].node=k;
}
else
if(t[root[k]].val>v[k])
{
root[k]=del(root[k]);
if(root[k])
dfs_tree(root[k]);
root[k]=++cnt;
t[root[k]].node=k;
t[root[k]].val=v[k];
}
//cerr<<k<<":";
//check(root[k]);
//cerr<<endl;
}
void dfs2(int k,int f,int val)
{
if(used[k])
{
++res;
printf("%d %d\n",k,res-val);
val=res;
}
for(register int i=h[k];i;i=e[i].nxt)
{
if(e[i].to==f)
continue;
dfs2(e[i].to,k,val);
}
}
int main()
{
//freopen("segtree.in","r",stdin);
//freopen("segtree.out","w",stdout);
n=read();
for(register int i=1;i<=n;++i)
v[i]=read();
for(register int i=1;i<n;++i)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs_tree(root[1]);
printf("%d\n",s[1]);
dfs2(1,0,0);
return 0;
}
```
## T2 我已经完全理解了字符串哈希
字符串完全随机，根据 $hash$ 的特性，$hash$ 也大约在 $[0,m)$ 中均匀随机。
所以对于一个比较长的字符串，答案有很大可能在 $998244352$ 附近，因此我们可以直接从大到小查找，用哈希表维护一下当前的哈希值是否存在即可。
闲话：数据非常水，30分暴力可以过65分，还有个老哥输出 998244352-t%3 得到了75 分（草）
```cpp
/*字符串见祖宗/cy*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
#define int long long
const int base=2333333,mod=998244353,hashmod=9999991;
int t,n,ha[10000001],pos[10000001],sum[2000001];
string s;
inline void insert(int k,int val)
{
int p=k%hashmod;
while(ha[p]!=-1&&ha[p]!=k)
p=((p<<1)+114514)%hashmod;
if(ha[p]==k)
pos[p]=val;
else
{
ha[p]=k;
pos[p]=val;
}
}
inline int find(int k)
{
int p=k%hashmod;
while(ha[p]!=-1&&ha[p]!=k)
p=((p<<1)+114514)%hashmod;
return ha[p]==-1? 0:pos[p];
}
inline int pw(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
signed main()
{
freopen("strhash.in","r",stdin);
freopen("strhash.out","w",stdout);
scanf("%lld",&t);
long long inv=pw(base,mod-2);
while(t--)
{
memset(ha,-1,sizeof ha);
memset(pos,0,sizeof pos);
cin>>s;
n=s.length();
s=" "+s;
for(register int i=1;i<=n;++i)
s[i]=s[i]-'a'+1;
if(n<=4000)
{
int ans=0;
for(register int i=1;i<=n;++i)
{
int tmp=0;
for(register int j=i;j<=n;++j)
{
tmp=(tmp*base+s[j])%mod;
ans=max(ans,tmp);
}
}
printf("%lld\n",ans);
}
else
{
for(register int i=1;i<=n;++i)
{
sum[i]=(sum[i-1]*base%mod+s[i])%mod;
int tmp=sum[i-1]*pw(inv,i-1)%mod;
if(!find(tmp))
insert(tmp,i);
else
insert(tmp,min(find(tmp),i));
}
bool flag=0;
for(register int ans=998244352;;--ans)
{
//cerr<<ans<<endl;
for(register int i=1;i<=n;++i)
{
int tmp=find((sum[i]-ans+mod)%mod*pw(inv,i)%mod);
if(tmp&&tmp<=i)
{
printf("%lld\n",ans);
flag=1;
break;
}
}
if(flag)
break;
}
}
}
return 0;
}
```
## T3 我已经完全理解了多源 BFS
手玩可以发现答案是一个关于时间的分段函数，我们发现只有在两个点的“势力范围”相遇的时候答案的函数会改变，即在这些时候分段。那么我们可以预处理出这些点，分段计算贡献。
每个段内是一个二次函数，我们可以选三个点插值出二次函数，点值可以扫描线求得。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int mod=998244353;
int ans,sum[201][201],n,m,x[61],y[61],nodex[201],nodey[201],cx,cy,k[100001],cnt;
inline int dis(int a,int b)
{
return (max(abs(x[a]-x[b]),abs(y[a]-y[b]))+1)>>1;
}
int calc(int t)
{
memset(nodex,0,sizeof nodex);
memset(nodey,0,sizeof nodey);
memset(sum,0,sizeof sum);
cx=cy=0;
for(register int i=1;i<=n;++i)
{
nodex[++cx]=x[i]-t+1;
nodex[++cx]=x[i]+t;
nodey[++cy]=y[i]-t+1;
nodey[++cy]=y[i]+t;
}
sort(nodex+1,nodex+cx+1);
cx=unique(nodex+1,nodex+cx+1)-nodex-1;
sort(nodey+1,nodey+cy+1);
cy=unique(nodey+1,nodey+cy+1)-nodey-1;
for(register int i=1;i<=n;++i)
{
int lx=lower_bound(nodex+1,nodex+cx+1,x[i]-t+1)-nodex;
int rx=lower_bound(nodex+1,nodex+cx+1,x[i]+t)-nodex;
int ly=lower_bound(nodey+1,nodey+cy+1,y[i]-t+1)-nodey;
int ry=lower_bound(nodey+1,nodey+cy+1,y[i]+t)-nodey;
++sum[lx][ly];
--sum[lx][ry];
--sum[rx][ly];
++sum[rx][ry];
}
int res=0;
for(register int i=1;i<=cx;++i)
for(register int j=1;j<=cy;++j)
{
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
if(sum[i][j])
res=(res+(nodex[i+1]-nodex[i])*(nodey[j+1]-nodey[j])%mod)%mod;
}
return res;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(register int i=1;i<=n;++i)
scanf("%lld%lld",&x[i],&y[i]);
for(register int i=1;i<n;++i)
for(register int j=i+1;j<=n;++j)
if(dis(i,j)<=m)
k[++cnt]=dis(i,j);
k[++cnt]=m;
sort(k+1,k+cnt+1);
cnt=unique(k+1,k+cnt+1)-k-1;
for(register int i=1;i<=cnt;++i)
{
int len=k[i]-k[i-1],s0=calc(k[i]);
if(i==cnt)
ans=(ans+s0*(m+1)%mod)%mod;
if(len<=3)
{
ans=(ans-s0+mod)%mod;
for(register int line=k[i-1]+1;line<k[i];++line)
ans=(ans-calc(line)+mod)%mod;
}
else
{
int s1=calc(k[i]-1),s2=calc(k[i]-2);
int a=((s2-2*s1+s0+mod)%mod*((mod+1)>>1)%mod+mod)%mod;
int b=(((s1<<2)-s2-3*s0+(mod<<2))%mod*((mod+1)>>1)%mod+mod)%mod;
int c=s0;
int res=(6*len%mod*c%mod+3*len%mod*(len-1)%mod*b%mod+len*(len-1)%mod*(2*len-1)%mod*a%mod)%mod*((mod+1)/6)%mod;
ans=(ans-res+mod)%mod;
}
}
printf("%lld\n",ans);
return 0;
}
```
# Day3
## T1 陌生的城市
[到这里评测](https://www.luogu.com.cn/problem/T177432)
由于只有 $a,b,c$ 三种字母，所以出现最多的字母数量不少于 $\lceil\frac n 3\rceil$
设循环节长度为 $m$ 的串重复 $k$ 次，则价值为 $k^2m$，那么只含循环节长度是 1 的贡献就有 $(k\lceil\frac n 3\rceil)^2$
若有一个子序列可以更新答案，则要满足 $k^2m>(k\lceil\frac m 3\rceil)^2$
解得 $m=1,2,3,5,6$
串的数量很少，直接上子序列自动机统计答案。
~~在这以前我一直用 vector 写子序列自动机多一个 log 我真的蠢~~
```cpp
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long t,n,ans,nxt[100001][3],sum[5],tg[5];
const int len[]={0,1,2,3,5,6};
char c[100001],qwq[6];
long long calc(int k,char s[])
{
int pos=0;
for(register long long tmp=0;;++tmp)
for(register int i=0;i<k;++i)
{
pos=nxt[pos][(int)s[i]];
if(pos==n+1)
return tmp*tmp*k;
}
return 0;
}
void dfs(int k,int l,char s[])
{
if(l==k)
{
if(k==2&&s[0]==s[1])
return;
if(k==3&&s[0]==s[1]&&s[1]==s[2])
return;
if(k==5&&s[0]==s[1]&&s[1]==s[2]&&s[2]==s[3]&&s[3]==s[4])
return;
if(k==6&&((s[0]==s[3]&&s[1]==s[4]&&s[2]==s[5]&&s[3]==s[6])||(s[0]==s[2]&&s[2]==s[4]&&s[1]==s[3]&&s[3]==s[5])))
return;
//cout<<s<<endl;
tg[0]=tg[1]=tg[2]=0;
for(register int i=0;i<k;++i)
++tg[(int)s[i]];
long long qaq=1e9;
for(register int i=0;i<3;++i)
if(tg[i])
qaq=min(qaq,sum[i]/tg[i]);
if(qaq*qaq*l<=ans)
return;
ans=max(ans,calc(k,s));
return;
}
for(register int i=0;i<3;++i)
{
s[l]=i;
dfs(k,l+1,s);
s[l]=0;
}
}
int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
scanf("%lld",&t);
while(t--)
{
ans=0;
scanf("%lld",&n);
scanf("%s",c+1);
nxt[n][0]=nxt[n][1]=nxt[n][2]=n+1;
sum[0]=sum[1]=sum[2]=0;
for(register int i=n;i>=1;--i)
{
nxt[i-1][0]=nxt[i][0];
nxt[i-1][1]=nxt[i][1];
nxt[i-1][2]=nxt[i][2];
nxt[i-1][c[i]-'a']=i;
++sum[c[i]-'a'];
}
ans=max(sum[0],max(sum[1],sum[2]))*max(sum[0],max(sum[1],sum[2]));
/*for(register int i=0;i<3;++i)
{
for(register int j=0;j<(int)(v[i].size());++j)
printf("%lld ",v[i][j]);
puts("");
}*/
for(register int i=1;i<=5;++i)
dfs(len[i],0,qwq);
printf("%lld\n",ans);
}
return 0;
}
```
## T2 大原题
在 YBTOJ 上的原题，不过没有账号看不了。
最大流。
~~说不清为什么是反正就是用心感受他是个网络流题目就好了~~
考虑建图，由于交换有时间顺序，所以把一个点拆成 $m$ 个，第 $m$ 个操作在第 $m$ 层连边。
我们发现每个点只要有一个球到达 1 即可，因此我们可以视为每个点有一个球，容量为 $a_i$（交换后每个点球数量不变）。
初始时源点向第一层的点连容量为 1 的边，每一层向下一层连容量为 $a_i$ 的边（同一时刻最多有 $a_i$ 个球在第 $i$ 个点）。
最后一层的 1 号点向汇点连边，容量无穷大。
这样构造点数 $O(nm)$，显然拿不到什么分。
注意到很多店是没有用的，如果没有交换操作这一层的点只起到连接作用。那么我们大可以删掉这些点，直接连向下一个有交换操作的点。这样优化后点数变为 $O(n+m)$，可以通过此题……吗？
然而会被卡常，因为 dfs 时大量无用的时间被消耗在了无法到达汇点的点上。
我们希望不要走这些点，可以在 bfs 时改为从汇点开始搜，搜到源点直接返回，这样可以最小化无用点的数量。
实测这一常数优化非常优秀，原来耗时 $1.2s$ 的数据现在只需要 $0.1s$。
```cpp
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct edge
{
int nxt,to,weight;
}e[100001<<1];
int T,s,t,cnt,n,m,tot=1,lst[10001],a[10001],h[10001],dep[10001],cur[10001],ans;
bool vis[10001];
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline void add(int x,int y,int w)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
e[tot].weight=w;
}
inline bool bfs()
{
for(register int i=0;i<=t;++i)
{
vis[i]=0;
cur[i]=h[i];
dep[i]=0x3f3f3f3f;
}
queue<int> q;
//q.push(s);
q.push(t);
//dep[s]=0;
dep[t]=0;
while(!q.empty())
{
int k=q.front();
q.pop();
vis[k]=0;
for(register int i=h[k];i;i=e[i].nxt)
if(e[i^1].weight&&dep[e[i].to]>dep[k]+1)
//if(e[i].weight&&dep[e[i].to]>dep[k]+1)
{
dep[e[i].to]=dep[k]+1;
if(e[i].to==s)
//if(e[i].to==t)
return 1;
if(!vis[e[i].to])
{
vis[e[i].to]=1;
q.push(e[i].to);
}
}
}
return dep[0]^dep[s];
//return dep[0]^dep[t];
}
int dfs(int k,int f)
{
if(k==t)
{
ans+=f;
return f;
}
int r=0,used=0;
for(register int i=cur[k];i;i=e[i].nxt)
{
cur[k]=i;
if(e[i].weight&&dep[e[i].to]==dep[k]-1)
//if(e[i].weight&&dep[e[i].to]==dep[k]+1)
if((r=dfs(e[i].to,min(e[i].weight,f-used))))
{
e[i].weight-=r;
e[i^1].weight+=r;
used+=r;
if(f==used)
break;
}
}
return used;
}
inline void dinic()
{
while(bfs())
dfs(s,1<<30);
}
int main()
{
freopen("qaq.in","r",stdin);
freopen("qaq.out","w",stdout);
T=read();
while(T--)
{
//cerr<<T<<endl;
ans=0;
tot=1;
memset(e,0,sizeof e);
memset(h,0,sizeof h);
memset(lst,0,sizeof lst);
n=read(),m=read();
cnt=s=1;
for(register int i=1;i<=n;++i)
{
a[i]=read();
lst[i]=++cnt;
add(s,lst[i],1);
add(lst[i],s,0);
}
for(register int i=1;i<=m;++i)
{
int x=read(),y=read();
++cnt;
add(lst[x],cnt,a[x]);
add(cnt,lst[x],0);
lst[x]=cnt;
++cnt;
add(lst[y],cnt,a[y]);
add(cnt,lst[y],0);
lst[y]=cnt;
add(lst[x],lst[y],1);
add(lst[y],lst[x],0);
add(lst[y],lst[x],1);
add(lst[x],lst[y],0);
}
t=++cnt;
add(lst[1],t,1<<30);
add(t,lst[1],0);
dinic();
printf("%d\n",ans);
}
return 0;
}
```
## T3 美丽的世界
把两个人看成二分图的两部分，那么每个装备可以看成一条边，连接两个装备栏，正向权值 $a$，反向权值 $b$。装备给哪边就从哪边出边。显然每个点只能有一条出边或没有出边。那么对于每一个弱联通块都有两种可能：
- 树，那么可以钦定一个树根，每条边指向根。
- 基环树，环内任意方向绕一圈，树边指向环。
然后有了一组乘积，显然我们可以维护一个下凸壳优化一下。
但是棘手的是我们要合并若干个下凸壳，得到一个总体的下凸壳。有一个奇妙的科技叫做[闵可夫斯基和](https://baike.baidu.com/item/%E9%97%B5%E5%8F%AF%E5%A4%AB%E6%96%AF%E5%9F%BA%E5%92%8C/8997888?fr=aladdin)，维护这个东西就可以得到整体下凸壳。
然后我们在总体的下凸壳上跑一遍更新答案就好了。
~~叉积要开 long long！我没开查了好久！~~
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct cp
{
int x,y;
};
cp make_cp(int x,int y)
{
cp res;
res.x=x;
res.y=y;
return res;
}
cp operator +(cp a,cp b)
{
return make_cp(a.x+b.x,a.y+b.y);
}
cp operator -(cp a,cp b)
{
return make_cp(a.x-b.x,a.y-b.y);
}
inline long long cross(cp a,cp b)
{
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
inline bool cmp1(cp a,cp b)
{
return a.x^b.x? a.x<b.x:a.y<b.y;
}
inline bool cmp2(cp a,cp b)
{
return cross(a,b)>0;
}
struct edge
{
int nxt,to,weight;
}e[2000001<<1];
int n,m,tot,h[1000001],d[1000001],cnt,qwq,sum[2],v[1000001];
bool inq[2000001<<1];
int vis[1000001];
queue<int> q;
long long ans;
cp cur[1000001],tmp[1000001],pre;
vector<cp> dq;
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
void dfs1(int k)
{
cur[cnt++]=make_cp(sum[0],sum[1]);
for(register int i=h[k];i;i=e[i].nxt)
if(inq[i>>1])
{
inq[i>>1]=0;
sum[k&1]+=e[i].weight;
sum[e[i].to&1]-=e[i^1].weight;
dfs1(e[i].to);
inq[i>>1]=1;
sum[k&1]-=e[i].weight;
sum[e[i].to&1]+=e[i^1].weight;
}
}
void dfs2(int k)
{
bool flag=1;
for(register int i=h[k];i;i=e[i].nxt)
if(!inq[i>>1])
{
flag=0;
inq[i>>1]=1;
sum[k&1]+=e[i].weight;
dfs2(e[i].to);
inq[i>>1]=0;
sum[k&1]-=e[i].weight;
}
if(flag)
cur[cnt++]=make_cp(sum[0],sum[1]);
}
int main()
{
n=read(),m=read();
tot=2;
for(register int i=1;i<=m;++i)
{
int x=read(),y=read(),a=read(),b=read();
x=(x<<1)-2;
y=(y<<1)-1;
++d[x];
++d[y];
e[tot].to=y;
e[tot].weight=a;
e[tot].nxt=h[x];
h[x]=tot++;
e[tot].to=x;
e[tot].weight=b;
e[tot].nxt=h[y];
h[y]=tot++;
}
for(register int node=0;node<(n<<1);++node)
if(!vis[node])
{
int p=0,res=0;
while(!q.empty())
q.pop();
q.push(node);
vis[node]=1;
while(!q.empty())
{
int k=q.front();
q.pop();
v[p++]=k;
res+=d[k];
for(register int i=h[k];i;i=e[i].nxt)
if(!vis[e[i].to])
{
vis[e[i].to]=1;
q.push(e[i].to);
}
}
res>>=1;
while(!q.empty())
q.pop();
for(register int i=0;i<p;++i)
if(d[v[i]]==1)
q.push(v[i]);
sum[0]=sum[1]=0;
while(!q.empty())
{
int k=q.front();
q.pop();
vis[k]=2;
for(register int i=h[k];i;i=e[i].nxt)
if(!inq[i>>1])
{
inq[i>>1]=1;
sum[k&1]+=e[i].weight;
if(--d[e[i].to]==1)
q.push(e[i].to);
}
}
cnt=0;
if(res<p)
{
int u=0;
for(register int i=0;i<p;++i)
{
u=v[i];
if(!d[u])
break;
}
dfs1(u);
}
else
{
int u=0;
for(register int i=0;i<p;++i)
{
u=v[i];
if(vis[u]==1)
break;
}
dfs2(u);
}
sort(cur,cur+cnt,cmp1);
dq.clear();
for(register int i=0;i<cnt;++i)
{
while(dq.size()>1&&cross(dq[dq.size()-1]-dq[dq.size()-2],cur[i]-dq[dq.size()-1])<=0)
dq.pop_back();
dq.push_back(cur[i]);
}
pre=pre+dq[0];
for(register int i=1;i<(int)(dq.size());++i)
tmp[qwq++]=dq[i]-dq[i-1];
}
sort(tmp,tmp+qwq,cmp2);
ans=1ll*pre.x*pre.y;
for(register int i=0;i<qwq;++i)
{
pre=pre+tmp[i];
ans=min(ans,1ll*pre.x*pre.y);
}
printf("%lld\n",ans);
return 0;
}
```
# Day4
## T1 度数
模拟赛开始 40min，已经开始写网络流板子了，这时人群当中突然跳出来一个兔队！
“出锅了，数据范围忘了写，$0\leq x_i,y_i \leq 1$。”
然后一眼就会做法了……
我们就是要构造一个图满足每个点是否有出边和入边，注意到如果这个无向图里存在一个环，那么我们非常显然的把他们首尾顺次相连，就可以满足任何要求。
那么我们跑一遍 tarjan 把环找出来缩了，然后整个图就成了一个树，树上直接从下到上维护每条边的方向即可。
另外这题是个细节巨大多的题目，考场上调了 3h /px
~~FST 成了 88 分，哈哈。~~
好吧实际上是数据锅了，重测这题过了。
~~兔居然造了自环数据，小锅兔石锤了~~
```cpp
//#pragma GCC optimize(2)//不要忘记删了O2
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
struct edge
{
int nxt,to,id;
}e[500001<<2],E[500001<<2];
int x[500001],y[500001],TOT=1,H[500001],s[500001],col[500001],n,m,cnt,a[500001],b[500001],sum[2],tot=1,h[500001],d[500001],dfn[500001],low[500001];
int used[500001];
bool vis[500001],inq[500001];
stack<int> t;
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline void add(int x,int y,int id)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
e[tot].id=id;
}
inline void ADD(int x,int y,int id)
{
E[++TOT].nxt=H[x];
H[x]=TOT;
E[TOT].to=y;
E[TOT].id=id;
}
void tarjan(int k,int num)
{
dfn[k]=++cnt;
low[k]=cnt;
vis[k]=1;
//cerr<<t.size()<<endl;
t.push(k);
for(register int i=h[k];i;i=e[i].nxt)
{
if(e[i].id==num)
continue;
if(!dfn[e[i].to])
{
tarjan(e[i].to,e[i].id);
low[k]=min(low[k],low[e[i].to]);
}
else
if(vis[e[i].to])
low[k]=min(low[k],dfn[e[i].to]);
}
if(dfn[k]==low[k])
{
vis[k]=0;
col[k]=k;
s[k]=1;
while(!t.empty()&&t.top()!=k)
{
col[t.top()]=k;
++s[k];
vis[t.top()]=0;
t.pop();
}
if(!t.empty())
t.pop();
if(s[k]>1)
a[k]=b[k]=0;
}
}
bool dfs1(int k,int f,int num)
{
register bool flag1=0,flag2=0;
register int free[2]={0,0};
for(register int i=H[k];i;i=E[i].nxt)
{
if(E[i].id==num)
continue;
if(!dfs1(E[i].to,k,E[i].id))
return 0;
if(used[E[i].id]==1)
{
if(col[x[E[i].id]]==k)
flag2=1;
else
flag1=1;
}
if(used[E[i].id]==0)
{
if(col[x[E[i].id]]==k)
flag1=1;
else
flag2=1;
}
if(used[E[i].id]==-1)
{
if(!free[0])
free[0]=E[i].id;
else
if(!free[1])
free[1]=E[i].id;
}
}
if(flag1&&flag2)
return 1;
if(!flag1&&a[k])
{
if(free[0])
{
if(col[x[free[0]]]==k)
used[free[0]]=0;
else
used[free[0]]=1;
free[0]=0;
}
else
if(free[1])
{
if(col[x[free[1]]]==k)
used[free[1]]=0;
else
used[free[1]]=1;
free[1]=0;
}
else
if(num&&used[num]==-1)
{
if(col[x[num]]==k)
used[num]=0;
else
used[num]=1;
}
else
return 0;
}
if(!flag2&&b[k])
{
if(free[0])
{
if(col[x[free[0]]]==k)
used[free[0]]=1;
else
used[free[0]]=0;
free[0]=0;
}
else
if(free[1])
{
if(col[x[free[1]]]==k)
used[free[1]]=1;
else
used[free[1]]=0;
free[1]=0;
}
if(num&&used[num]==-1)
{
if(col[x[num]]==k)
used[num]=1;
else
used[num]=0;
}
else
return 0;
}
return 1;
}
void dfs2(int k,int f,int num)
{
if(vis[k])
return;
vis[k]=1;
for(register int i=h[k];i;i=e[i].nxt)
{
if(used[e[i].id]!=-1)
continue;
if(col[e[i].to]^col[k])
continue;
if(e[i].id==num)
continue;
if(x[e[i].id]==k)
used[e[i].id]=0;
else
used[e[i].id]=1;
dfs2(e[i].to,k,e[i].id);
}
}
int main()
{
freopen("degree.in","r",stdin);
freopen("degree.out","w",stdout);
n=read(),m=read();
for(register int i=1;i<=n;++i)
{
a[i]=read();
sum[0]+=a[i];
}
for(register int i=1;i<=n;++i)
{
b[i]=read();
sum[1]+=b[i];
}
if(sum[0]>m||sum[1]>m)
{
puts("-1");
return 0;
}
for(register int i=1;i<=m;++i)
{
x[i]=read(),y[i]=read();
add(x[i],y[i],i);
add(y[i],x[i],i);
++d[x[i]],++d[y[i]];
}
for(register int i=1;i<=n;++i)
if(d[i]<a[i]+b[i])
{
puts("-1");
return 0;
}
for(register int i=1;i<=m;++i)
used[i]=-1;
tarjan(1,0);
for(register int i=1;i<=m;++i)
{
if(col[x[i]]==col[y[i]])
continue;
ADD(col[x[i]],col[y[i]],i);
ADD(col[y[i]],col[x[i]],i);
}
if(!dfs1(col[1],0,0))
{
puts("-1");
return 0;
}
for(register int i=1;i<=n;++i)
vis[i]=0;
for(register int i=1;i<=n;++i)
if(!inq[col[i]])
{
inq[col[i]]=1;
dfs2(col[i],0,0);
}
for(register int i=1;i<=m;++i)
if(used[i]==1)
{
putchar('1');
putchar(' ');
}
else
{
putchar('0');
putchar(' ');
}
puts("");
return 0;
}
//Sebastian Vettel you are the triple champion of the world! You are the man, you are the man.
```
## T2 数位
[原题](https://codeforces.com/contest/778/problem/E)
数位 dp，设 $dp_{i,j}$ 表示当前考虑到第 $i$ 位，进位集合为 $j$ 的最大值，那么会有非常 naive 的转移。
但是状态太多了，我们需要优化，我们发现很多状态是不可能到达的，如果对所有 $b$ 的后 $i$ 位后缀排序，那么进位的数字集合一定是一个后缀，每位状态就减少到了 $O(n)$ 个。排序直接基数排序可以搞了，然后更新答案。
还有一个问题是可能有前导零，要把他们的贡献搞掉。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define int long long
int n,m,len[1001],pos[11],sum[11],dp[1001][1001],c[11],ord[1001][1001],ans;
char b[1001][1001],a[1001];
int vis[1001];
vector<int> t[11];
inline bool check(int x,int y)
{
if(x==len[0]&&!y)
return 0;
return (a[x]==y+'0'||a[x]=='?');
}
inline bool judge(int id,int x,int y)
{
return !(x>len[id]&&!y);
}
signed main()
{
//freopen("digits.in","r",stdin);
//freopen("digits.out","w",stdout);
memset(dp,-0x3f,sizeof dp);
scanf("%s",a+1);
m=len[0]=strlen(a+1);
reverse(a+1,a+m+1);
scanf("%lld",&n);
for(register int i=1;i<=n;++i)
{
scanf("%s",b[i]+1);
len[i]=strlen(b[i]+1);
reverse(b[i]+1,b[i]+len[i]+1);
m=max(m,len[i]);
len[i]=max(len[i],len[0]);
}
for(register int i=0;i<10;++i)
scanf("%lld",&c[i]);
int tmp=strlen(a+1);
for(register int i=tmp+1;i<=m;++i)
a[i]='0';
for(register int i=1;i<=n;++i)
{
tmp=strlen(b[i]+1);
for(register int j=tmp+1;j<=m;++j)
b[i][j]='0';
}
dp[0][n+1]=0;
for(register int i=1;i<=n;++i)
ord[0][i]=i;
for(register int i=1;i<=m;++i)
b[0][i]=15+'0';
for(register int i=1;i<=m;++i)
{
for(register int j=0;j<10;++j)
t[j].clear();
for(register int j=1;j<=n;++j)
t[b[ord[i-1][j]][i]-'0'].push_back(ord[i-1][j]);
int cnt=0;
for(register int j=0;j<10;++j)
for(register int k=0;k<(int)(t[j].size());++k)
ord[i][++cnt]=t[j][k];
for(register int j=0;j<10;++j)
{
sum[j]=0;
pos[j]=n+1;
for(register int k=n;k>=1;--k)
if(judge(ord[i][k],i,j))
sum[j]+=c[(b[ord[i][k]][i]-'0'+j)%10];
while(pos[j]>0&&b[ord[i][pos[j]]][i]-'0'+j>=10)
--pos[j];
++pos[j];
if(check(i,j))
dp[i][pos[j]]=max(dp[i][pos[j]],dp[i-1][n+1]+sum[j]);
}
for(register int j=1;j<=n;++j)
vis[j]=0;
vis[0]=114514;
for(register int j=n;j>=1;--j)
{
vis[ord[i-1][j]]=1;
for(register int k=0;k<10;++k)
{
if(judge(ord[i-1][j],i,k))
sum[k]-=c[(b[ord[i-1][j]][i]-'0'+k)%10];
sum[k]+=c[(b[ord[i-1][j]][i]-'0'+k+1)%10];
while(pos[k]>0&&b[ord[i][pos[k]]][i]-'0'+k+vis[ord[i][pos[k]]]>=10)
--pos[k];
++pos[k];
if(check(i,k))
dp[i][pos[k]]=max(dp[i][pos[k]],dp[i-1][j]+sum[k]);
}
}
}
ans=dp[m][n+1];
for(register int i=n;i>=1;--i)
ans=max(ans,dp[m][i]+(n-i+1)*c[1]);
printf("%lld\n",ans);
return 0;
}
//I'm faster than Felipe!
```
## T3 跳跃
[原题](https://codeforces.com/gym/102431/problem/G)
这个博弈论模型的胜负状态和点的位置，跳的长度都有关，不能直接 $Nim$ 游戏或者 $SG$ 函数。
考虑最后一步，当有人走到树的直径的一端时他就输了，因为下一个人可以调到另一个端点，而直径端点间距离最长。那么两人的最优策略就是避免自己走到直径端点。
我们可以递归考虑这个问题，去掉直径两个端点之后，问题没有改变，先走到现在直径的端点的人必败。那么这样一直递归下去，最后会出来一个类似链的结构，其中一个端点是起点。
显然对于起点在端点的链后手必败，除了退化成点的特殊情况。
那么在两边均匀的去掉点后只剩下起点，说明**起点是直径的中点**
接下来就成了一个计数题，记 $f_{i,j}$ 是以 $i$ 为根的子树最大深度不超过 $j$ 的方案数，记 $i$ 的儿子为 $son_i$，转移的时候 $f_{i,j}=\prod_{node\in son_i}f_{node,j-1}$。然后这个东西是树上背包，$O(n^2)$ 的。
然后对于 1 的子树，我们发现一个构造是合法的当且仅当有两个子树是最深的而且深度相同，直接合并即可。
这个做法还不够优秀，tyy 说可以用长链剖分优化，~~但是我不会~~现在总算明白了一点。
长链信息直接继承，考虑怎样合并短链。根据 $f$ 的定义，可以知道 $f$ 的长度很可能是无穷大的，这样我们就没法搞了，得想个办法把无限的部分处理掉。为此我们需要维护一个 lazy tag，和数组 $f'$，满足 $f'_{i,j}\prod_{k=1}^j tag_{i,k}=f_{i,j}$，这样可以发现 $tag$ 在超出树高的部分全部为 1，直接忽略即可。合并的时候把短链标记往后推一格，在短链长度的位置直接乘真实的 $f$ 值即可。
然后再用 $f$ 合并推出答案。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
struct edge
{
int nxt,to;
}e[200001<<1];
const int mod=998244353;
int ans=1,val[200005<<3],n,tot,tmp[200005],h[200005],*id,*f[200001],*g[200005],*tag[200005],len[200005],son[200005],dp[200005][2],tag_dp[200005][2];
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline void add(int x,int y)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
}
inline void push_down(int k,int dep)
{
if(tag[k][dep]^1)
{
f[k][dep]=f[k][dep]*tag[k][dep]%mod;
tag[k][dep+1]=tag[k][dep+1]*tag[k][dep]%mod;
tag[k][dep]=1;
}
}
inline void update(int k)
{
dp[k][0]=dp[k][0]*tag_dp[k][0]%mod;
tag_dp[k+1][0]=tag_dp[k+1][0]*tag_dp[k][0]%mod;
tag_dp[k][0]=1;
dp[k][1]=dp[k][1]*tag_dp[k][1]%mod;
tag_dp[k+1][1]=tag_dp[k+1][1]*tag_dp[k][1]%mod;
tag_dp[k][1]=1;
}
void dfs1(int k,int f)
{
for(register int i=h[k];i;i=e[i].nxt)
{
if(e[i].to==f)
continue;
dfs1(e[i].to,k);
if(len[e[i].to]>len[son[k]])
son[k]=e[i].to;
}
len[k]=len[son[k]]+1;
}
void dfs2(int k,int fa)
{
f[k][0]=1;
tag[k][0]=1;
if(!son[k])
return;
f[son[k]]=f[k]+1;
tag[son[k]]=tag[k]+1;
dfs2(son[k],k);
for(register int i=h[k];i;i=e[i].nxt)
{
if(e[i].to==fa||e[i].to==son[k])
continue;
f[e[i].to]=id;
id+=len[e[i].to]+1;
tag[e[i].to]=id;
id+=len[e[i].to]+1;
dfs2(e[i].to,k);
tmp[0]=f[k][0];
for(register int j=0;j<len[e[i].to];++j)
{
push_down(e[i].to,j);
push_down(k,j);
if(j)
{
tmp[j]=(tmp[j-1]+f[k][j])%mod;
f[e[i].to][j]=(f[e[i].to][j]+f[e[i].to][j-1])%mod;
}
}
for(register int j=0;j<len[e[i].to];++j)
{
push_down(k,j+1);
if(j)
f[k][j+1]=(f[k][j+1]*(f[e[i].to][j]+1)%mod+tmp[j]*(f[e[i].to][j]-f[e[i].to][j-1]+mod)%mod)%mod;
else
f[k][j+1]=(f[k][j+1]*(f[e[i].to][j]+1)%mod+tmp[j]*f[e[i].to][j]%mod)%mod;
}
tag[k][len[e[i].to]+1]=tag[k][len[e[i].to]+1]*(f[e[i].to][len[e[i].to]-1]+1)%mod;
}
}
signed main()
{
n=read();
for(register int i=1;i<n;++i)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
for(register int i=0;i<=n+1;++i)
tag_dp[i][0]=tag_dp[i][1]=1;
dfs1(1,1);
dp[0][1]=1;
for(register int i=h[1];i;i=e[i].nxt)
{
f[e[i].to]=id=val;
id+=len[e[i].to]+1;
tag[e[i].to]=id;
id+=len[e[i].to]+1;
dfs2(e[i].to,1);
for(register int j=0;j<len[e[i].to];++j)
{
push_down(e[i].to,j);
if(j)
f[e[i].to][j]=(f[e[i].to][j]+f[e[i].to][j-1])%mod;
}
tmp[0]=dp[0][0]+dp[0][1];
for(register int j=1;j<=len[e[i].to];++j)
{
update(j);
tmp[j]=(tmp[j-1]+dp[j][0]+dp[j][1])%mod;
}
for(register int j=0;j<len[e[i].to];++j)
{
if(j)
dp[j+1][1]=(dp[j+1][1]+dp[j+1][1]*f[e[i].to][j]%mod+dp[j+1][0]*(f[e[i].to][j]-f[e[i].to][j-1]+mod)%mod)%mod;
else
dp[j+1][1]=(dp[j+1][1]+dp[j+1][1]*f[e[i].to][j]%mod+dp[j+1][0]*f[e[i].to][j]%mod)%mod;
if(j)
dp[j+1][0]=(dp[j+1][0]*(f[e[i].to][j-1]+1)%mod+tmp[j]*(f[e[i].to][j]-f[e[i].to][j-1]+mod)%mod)%mod;
else
dp[j+1][0]=(dp[j+1][0]+tmp[j]*f[e[i].to][j]%mod)%mod;
}
tag_dp[len[e[i].to]+1][0]=tag_dp[len[e[i].to]+1][0]*(f[e[i].to][len[e[i].to]-1]+1)%mod;
tag_dp[len[e[i].to]+1][1]=tag_dp[len[e[i].to]+1][1]*(f[e[i].to][len[e[i].to]-1]+1)%mod;
}
for(register int i=1;i<=len[1];++i)
{
update(i);
ans=(ans+dp[i][1])%mod;
}
printf("%lld\n",ans);
return 0;
}
```
# Day5
## T1 即得
太好了，又切了一题。
太坏了，后面 T2 智障的 60 分没拿到。
此题 $2\leq n\leq 21$，显然状压。
记 $dp_s$ 为只经过节点集合 $s$ 的最小生成树，$mp$ 是邻接矩阵，那么有显然的转移 $dp[s|2^{j-1}]=\min(dp[s|2^{j-1}],dp[s]+mp[i][j]);$，其中 $i\in s,j\notin s$。单次转移 $O(n^2)$，总复杂度 $O(n^22^n)$，可以拿到 20 分的好成绩/px
然后各种乱搞优化这个 dp，我的做法是预处理，记 $e_i$ 为与点 $i$ 相连的权值不是 $2^{31}-1$ 的边集，$mincost[i][s]$ 表示点 $i$ 在所选点集与 $e_i$ 的交为 $s$ 时和点集直接相连的边的最小权值，这个东西可以邻接表排序然后查表搞了，复杂度赛时没仔细算，反正能过。然后 dp 的时候可以直接 $dp[s|2^{i-1}]=\min(dp[s|2^{i-1}],dp[s]+mincost[i][s\&e[i]])$。这样转移是 $O(n)$ 的，总复杂度（大约？） $O(n2^n)$，可以通过。
还有一些奇怪的优化也可以加上，比如对于每个 $s$ 用 $lowbit$ 和 $\log_2$ 可以 $O(1)$ 求出每个 $s$ 的最低位最高位，然后能有点常数优化，不过好像没啥大用我就给删掉了。
```cpp
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n,m,q,mp[22][22];
long long dp[(1<<21)+1];
int mincost[22][(1<<21)+1];
int e[22];
vector<pair<int,int> > v[22];
/*struct edge
{
int x,y;
long long weight;
bool operator <(const edge &other) const
{
return weight<other.weight;
}
}e[((21*21)>>1)+1];*/
inline long long read()
{
register long long x=0;
register char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
void print(register long long x)
{
if(x>=10)
print(x/10);
putchar(x%10+'0');
}
inline long long minn(register long long x,register long long y)
{
return x<y? x:y;
}
/*int anc(register int k)
{
if(!bin[k])
return k;
return bin[k]=anc(bin[k]);
}
inline void link(register int x,register int y)
{
x=anc(x);
y=anc(y);
if(x!=y)
bin[y]=x;
}
inline void kruskal()
{
register int cnt=0;
for(register int i=1;i<=m;++i)
if(anc(e[i].x)^anc(e[i].y))
{
ans+=e[i].weight;
++cnt;
link(e[i].x,e[i].y);
}
ans+=2147483647ll*(n-1-cnt);
}*/
int main()//how to let this f**king code run into O(n2^n)???????????
{
freopen("acquire.in","r",stdin);
freopen("acquire.out","w",stdout);
n=read(),m=read();
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)
mp[i][j]=2147483647ll;
for(register int i=1;i<=n;++i)
mincost[i][0]=2147483647ll;
for(register int i=1;i<=m;++i)
{
register int x=read(),y=read();
mp[x][y]=mp[y][x]=read();
v[x].push_back(make_pair(mp[x][y],y));
v[y].push_back(make_pair(mp[x][y],x));
e[x]|=1<<(y-1);
e[y]|=1<<(x-1);
}
for(register int i=1;i<=n;++i)
{
sort(v[i].begin(),v[i].end());
for(register int s=1;s<=e[i];++s)
if((s&e[i])==s)
for(register int j=0;j<(int)v[i].size();++j)
if((s>>(v[i][j].second-1))&1)
{
mincost[i][s]=v[i][j].first;
break;
}
}
//sort(e+1,e+m+1);
//kruskal();
for(register int i=1;i<(1<<n);++i)
{
dp[i]=2147483647ll*21;
//mn[i]=log2(i&(-i))+1;
//mx[i]=floor(log2(i))+1;
}
for(register int i=1;i<=n;++i)
dp[1<<(i-1)]=0;
for(register int s=1;s<(1<<n);++s)
{
/*for(register int i=mn[s];i<=mx[s];++i)
if((s>>(i-1))&1)
for(register int j=1;j<=n;++j)
if(((s>>(j-1))&1)==0)
dp[s|(1<<(j-1))]=minn(dp[s|(1<<(j-1))],dp[s]+mp[i][j]);*/
for(register int i=1;i<=n;++i)
if(((s>>(i-1))&1)==0)
{
register int tmp=s&e[i];
dp[s|(1<<(i-1))]=minn(dp[s|(1<<(i-1))],dp[s]+mincost[i][tmp]);
}
}
for(register int s=(1<<n)-1;s;--s)
for(register int i=1;i<=n;++i)
if((s>>(i-1))&1)
dp[s^(1<<(i-1))]=minn(dp[s^(1<<(i-1))],dp[s]);
q=read();
while(q--)
{
register int k=read(),s=0;
while(k--)
{
register int x=read();
s|=1<<(x-1);
}
print(dp[s]);
putchar('\n');
}
return 0;
}
```
## T2 易见
[原题](https://loj.ac/p/6074)，本题加强到 1e6，但是我不会做。
原题做法考虑 dp，有显然的 $O(n^2)$ 转移，形象理解就是子序列自动机上面的路径计数。
然后这个转移是个矩阵形式，我们可以维护前缀和后缀和搞了他，在模拟赛可以拿 80 分。
~~但是我写了 20 分暴力，哈哈~~
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
int n,m;
char s[1000001];
const int mod=1000000007;
struct matrix
{
int n,m,a[11][11];
void init(int x,int y)
{
n=x;
m=y;
memset(a,0,sizeof a);
}
}sum[200001],inv[200001];
matrix operator *(const matrix &x,matrix &y)
{
matrix res;
res.init(x.n,x.m);
for(register int i=1;i<=x.n;++i)
for(register int k=1;k<=x.n;++k)
if(y.a[i][k])
for(register int j=1;j<=x.m;++j)
if(x.a[k][j])
res.a[i][j]=(res.a[i][j]+y.a[i][k]*1ll*x.a[k][j]%mod)%mod;
return res;
}
int main()
{
//freopen("easy.in","r",stdin);
//freopen("easy.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
scanf("%d",&m);
for(register int i=0;i<=n;++i)
{
sum[i].n=sum[i].m=inv[i].n=inv[i].m=10;
for(register int j=1;j<=10&&i;++j)
{
sum[i].a[s[i]-'a'+1][j]=1;
inv[i].a[s[i]-'a'+1][j]=1000000006;
}
for(register int j=1;j<=10;++j)
sum[i].a[j][j]=inv[i].a[j][j]=1;
}
for(register int i=1;i<=n;++i)
{
sum[i]=sum[i-1]*sum[i];
inv[i]=inv[i]*inv[i-1];
}
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
matrix tmp,ans;
int cnt=0;
tmp.init(10,10);
ans.init(10,1);
tmp=inv[x-1]*sum[y];
ans.a[10][1]=1;
ans=ans*tmp;
for(register int i=1;i<=9;++i)
cnt=(cnt+ans.a[i][1])%mod;
printf("%d\n",cnt);
}
return 0;
}
```
# Day6
目前最低排名，被结论题和自己 T2 的锅送到了 rk40/cy
## T1 清风
[原题](https://www.luogu.com.cn/problem/CF838D)
在链上加一个点与 $1,n$ 相连，链变成一个环，那么一个构造不合法当且仅当新加上的点被选中。
显然总方案为 $2^m(n+1)^m$，由于我们可以把这个环转转转，所以每个点本质上是相同的，则每个点都有 $\frac{n-m+1}{n+1}$ 的概率不被选中，所以最终答案为 $2^m(n+1)^{m-1}(n-m+1)$。
~~结论题爪巴爪巴爪巴~~
## T2 半夜
[原题](http://oj.qingyu.us/problem/305)
给两个长度相同的环，求环上的 LCS 长度。
此处借鉴 wzm 神仙的做法。
有显然的 $O(n^3)$ dp，然后打个 dp 数组的表可以发现每次循环会在 dp 数组的一段后缀上减一，所以这个东西可以用树状数组快速维护一下和，就能过了。
```cpp
/*下次能不能出个可做的T2*/
#include<iostream>
#include<cstdio>
using namespace std;
int sum[4021][2021],dp[2001][2001],n,ans;
string s1,s2;
inline int lowbit(int x)
{
return x&-x;
}
inline void update(int i,int x,int val)
{
for(;x<=n+1;x+=lowbit(x))
sum[i][x]+=val;
}
inline int query(int i,int x)
{
int res=0;
for(;x;x-=lowbit(x))
res+=sum[i][x];
return res;
}
int main()
{
//freopen("midnight.in","r",stdin);
//freopen("midnight.out","w",stdout);
scanf("%d",&n);
cin>>s1>>s2;
s1=" "+s1+s1;
s2=" "+s2;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(s1[i]==s2[j])
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
update(i,j,dp[i][j]);
update(i,j+1,-dp[i][j]);
}
ans=dp[n][n];
for(register int i=1;i<=n;++i)
{
int pos=1;
for(register int j=1;j<=n+1;++j)
sum[i][j]=0;
for(register int j=1;j<n;++j)
{
while(pos<=n)
{
int tmp=max(query(i+j-1,pos),query(i+j,pos-1));
if(s1[i+j]==s2[pos])
tmp=max(tmp,query(i+j-1,pos-1)+1);
if(tmp^query(i+j,pos))
break;
++pos;
}
update(i+j,pos,-1);
update(i+j,n+1,1);
}
for(register int j=1;j<=n;++j)
{
int tmp=max(query(i+n,j-1),query(i+n-1,j));
if(s1[i+n]==s2[j])
tmp=max(tmp,query(i+n-1,j-1)+1);
update(i+n,j,tmp);
update(i+n,j+1,-tmp);
}
ans=max(ans,query(i+n,n));
}
printf("%d\n",ans);
return 0;
}
```
## T3 鸣蝉
[原题](https://loj.ac/p/6499)
终于有我可以理解的 T3 了。
空间限制很小还强制在线，树套树 CDQ 全部死掉，考虑 bitset 优化。
然后发现这个 bitset 还是过不了，可以用四毛子分块，然后 bitset 优化 ST 表，这样可以卡过去。
注意手写 bitset 卡常。
代码又是贺的。
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,p,last,dt[100001],block[100001],a[100001],lg[100001],node[100001],tot,cnt,blocks;
struct bitset
{
unsigned int a[(100000>>5)+1];
bitset operator |(bitset b) const
{
bitset c;
for(register int i=0;i<=cnt;++i)
c.a[i]=a[i]|b.a[i];
return c;
}
void reset()
{
for(register int i=0;i<=cnt;++i)
a[i]=0;
}
void set(int x)
{
a[x>>5]|=1u<<(x&31);
}
int count()
{
int res=0;
for(register int i=0;i<=cnt;++i)
res+=dt[a[i]>>16]+dt[a[i]&((1<<16)-1)];
return res;
}
}f[73][9],ans;
inline void init()
{
for(register int i=1;i<=65535;++i)
for(register int x=i;x;x&=(x-1))
++dt[i];
for(register int i=2;i<=100000;++i)
lg[i]=lg[i>>1]+1;
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
init();
blocks=sqrt(1.2*n*log2(n+1));
tot=n/blocks+1;
for(register int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
node[i]=a[i];
block[i]=i/blocks+1;
}
sort(node+1,node+n+1);
cnt=unique(node+1,node+n+1)-node-1;
for(register int i=1;i<=n;++i)
{
a[i]=lower_bound(node+1,node+cnt+1,a[i])-node;
f[block[i]][0].set(a[i]);
}
cnt>>=5;
for(register int j=1;j<=lg[tot];++j)
for(register int i=1;i+(1<<j)-1<=tot;++i)
f[i][j]=f[i][j-1]|f[i+(1<<(j-1))][j-1];
for(register int i=1;i<=m;++i)
{
ans.reset();
int k;
scanf("%d",&k);
while(k--)
{
int l,r;
scanf("%d%d",&l,&r);
if(p&&i!=1)
{
l=(l^last)%n+1;
r=(r^last)%n+1;
if(l>r)
l^=r^=l^=r;
}
if(block[l]==block[r])
for(register int i=l;i<=r;++i)
ans.set(a[i]);
else
{
for(register int i=l;;++i)
{
if(block[i]^block[l])
break;
ans.set(a[i]);
}
for(register int i=r;;--r)
{
if(block[i]^block[r])
break;
ans.set(a[i]);
}
if(block[r]-block[l]>1)
ans=ans|f[block[l]+1][lg[block[r]-block[l]-1]]|f[block[r]-(1<<lg[block[r]-block[l]-1])][lg[block[r]-block[l]-1]];
}
}
printf("%d\n",last=ans.count());
}
return 0;
}
```
# Day7
哈哈，阴间场。
## T1 体积
[原题](http://codeforces.com/gym/100269/attachments)，L 题。
不会做。
## T2
这个题目是临时换的，并没有名字。
[原题](http://codeforces.com/problemset/problem/582/D)
正在做。
## T3 编码
这是真正的 T1，可惜我没看出来。
[原题](http://codeforces.com/gym/101239/attachments)，L 题。
参考荷马史诗的做法，用哈夫曼树（合并果子）统计答案，但是字符串数量高达 $4^n$，过不去。
但是我们发现为一位每个字符概率相同，那么很多串的概率是一样的，本质不同的概率最多只有 $\dbinom{23}{3}=1771$ 个。那么我们可以把概率相同的串压在一起，然后每次先优先合并自己，然后有剩余再和别的概率合并。
这个东西大约是 $1\log$ 的，感性理解这个东西每合并一次就会减少一半，那么经过 $\log $ 次一堆会变成 $1$。
```cpp
//有样例，别忘了骗分
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
double ans,p[4];
struct node
{
double w;
int h,sum;
node(double W,int H,int SUM)
{
w=W,h=H,sum=SUM;
}
};
bool operator <(node a,node b)
{
return a.w!=b.w? a.w>b.w:a.h^b.h? a.h>b.h:a.sum<b.sum;
}
priority_queue<node,vector<node>,less<node> > q;
int n,cnt,maxh,c[21][21],res;
void dfs(int k,int maxn,double val,int sum)
{
if(maxn>=n)
{
//++cnt;
q.push(node(val,1,sum));
//res+=sum;
//printf("%d %.20lf\n",sum,val);
return;
}
if(k>=4)
return;
for(register int i=maxn;i<=n;++i)
{
double tmp=1.0000;
for(register int j=maxn+1;j<=i;++j)
tmp*=p[k];
dfs(k+1,i,val*tmp,sum*c[n-maxn][i-maxn]);
}
}
signed main()
{
//freopen("code.in","r",stdin);
//freopen("code.out","w",stdout);
scanf("%lld",&n);
c[0][0]=c[1][0]=1;
for(register int i=1;i<=n;++i)
{
for(register int j=0;j<=i;++j)
{
if(j)
c[i][j]=c[i-1][j-1]+c[i-1][j];
else
c[i][j]=1;
//printf("%d ",c[i][j]);
}
//puts("");
}
//printf("%d\n",c[3][1]*c[2][1]*c[1][1]);
for(register int i=0;i<4;++i)
scanf("%lf",&p[i]);
dfs(0,0,1.0000,1);
//printf("%d\n",res);
while(q.size()>1)
{
node now=q.top();
q.pop();
if(now.sum>1)
{
q.push(node(2*now.w,now.h+1,now.sum>>1));
ans+=(now.sum-(now.sum&1))*now.w;
now.sum&=1;
}
if(now.sum)
{
node tmp=q.top();
q.pop();
q.push(node(now.w+tmp.w,max(now.h,tmp.h)+1,1));
ans+=now.w+tmp.w;
if(--tmp.sum)
q.push(tmp);
}
}
printf("%.10lf\n",ans);
return 0;
}
```
# Day8
哈哈，最后五分钟测了个样例，然后电脑成了砖头。
重启之后代码没了。
于是快乐爆零。
## T1 循环数组
[原题](http://codeforces.com/problemset/problem/722/F)
每个数字显然独立，没有出现在某个串中显然不能更新答案，于是题目变成了给定若干个连续的同余方程，求最长有解的段。
似乎赛时大部分神仙都是直接 exCRT+Sparse Table 头铁一波就过了？~~反正我暴力 exCRT~~
然而这一题只要知道有没有解，而不关心解是什么，上面的做法似乎有点大材小用。
我们发现任意两个方程需要满足 $ax+b=cy+d$，其中那么我们可以直接双指针判断当前区间有没有解，固定右指针，然后看解是否合法来移动左指针。
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,len[100001],a[100001][41],ans[100001],maxn,l;
struct node
{
int id,a,b;
}t[100001];
vector<node> v[100001];
int gcd(int x,int y)
{
return x%y? gcd(y,x%y):y;
}
inline bool excrt(int x,int y,int a,int b)
{
return x==a? y==b:(y-b)%gcd(x,a)==0;
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;++i)
{
int k;
scanf("%d",&k);
maxn=max(maxn,k);
for(register int j=1;j<=k;++j)
{
int x;
scanf("%d",&x);
node nw;
nw.id=i;
nw.a=k;
nw.b=j-1;
v[x].push_back(nw);
}
}
for(register int i=1;i<=m;++i)
{
l=0;
for(register int j=1;j<=maxn;++j)
t[j].a=t[j].b=0;
for(register int j=0;j<(int)v[i].size();++j)
{
if(i&&v[i][j].id!=v[i][j-1].id+1)
while(l<j)
--t[v[i][l++].a].a;
for(register int k=1;k<=maxn;++k)
if(t[k].a&&!excrt(k,t[k].b,v[i][j].a,v[i][j].b))
while(t[k].a)
--t[v[i][l++].a].a;
++t[v[i][j].a].a;
t[v[i][j].a].b=v[i][j].b;
ans[i]=max(ans[i],j-l+1);
}
}
for(register int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
```
## T2 淡出字符串
[原题](https://codeforces.com/problemset/problem/1063/F)
正解 $O(n \log n)$，然而不会。
显然有自然根号，然后可以暴力枚举最长字符串的长度，维护 每个字串的 hash 值判断是否可以转移。
但是 $n\leq 5\times 10^5$ 过不去，可以用 bitset卡常，然后就过了。
代码贺的，然后自己写了一遍。
~~顺便吐槽一下这题模数用 1145141 会 WA，李田所还是不行啊。~~
```cpp
#include<iostream>
#include<cstdio>
#include<bitset>
#include<string>
#include<cmath>
using namespace std;
const int mod=7000007,base=37;
string s;
int n,maxn,res,h[500001];
bitset<mod+1> qwq;
bitset<500001> f[1001];
int main()
{
cin>>n>>s;
s=" "+s;
for(register int i=1;i<=n;++i)
h[i]=s[i]-='a'-1;
maxn=sqrt(n<<1)+1;
res=1;
f[1].set();
for(register int i=2;i<=maxn;++i)
{
res+=i;
for(register int j=n-res+1;j>=1;--j)
{
if(f[i-1][j+i])
qwq[h[j+i]]=1;
if(qwq[h[j]]||qwq[h[j+1]])
f[i][j]=1;
}
if(f[i].none())
{
printf("%d\n",i-1);
return 0;
}
qwq.reset();
for(register int j=1;j<=n-res+1;++j)
h[j]=(h[j]*base%mod+s[j+i-1])%mod;
}
printf("%d\n",maxn);
return 0;
}
```
# Day9
## T2 掉落
考场上写了个树套树，没调出来/px
[原题](http://codeforces.com/problemset/problem/780/G)
这道题几乎没有什么思维难度，是一个二维数点的板子，每个板子可以接住正上方一个 $s_i\times(r_i-l_i+1)$ 的矩形内的球，可以用树套树维护。
但是内层再开一个线段树会炸空间（256MB），~~并且不好写，不好调~~，我们考虑换个方法。
注意到对于每个位置上所有球，一个板子能接到的一定是一个区间，所以可以用堆直接维护每个位置上球的高度，数量即可。
然后需要维护每个区间的最小高度用来剪枝，防止在无用区间浪费时间。
对于每个板子，我们直接在矩形内查询，统计答案，然后分别在板子两侧加入同样数量的球即可。
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define int long long
const int mod=1000000007;
struct board
{
int h,l,r,s;
bool operator <(const board &other) const
{
return h>other.h;
}
}a[100001];
int maxn,w,n,sum,ans[100001<<2];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q[100001];
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline int ls(int k)
{
return k<<1;
}
inline int rs(int k)
{
return k<<1|1;
}
inline void push_up(int k)
{
ans[k]=min(ans[ls(k)],ans[rs(k)]);
}
void build(int k,int l,int r)
{
if(l==r)
{
q[l].push(make_pair(maxn+1,1));
ans[k]=maxn+1;
return;
}
int mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
push_up(k);
}
void update(int node,int l,int r,int k,int p,int h)
{
if(l==r)
{
q[l].push(make_pair(h,p));
ans[k]=min(ans[k],h);
return;
}
int mid=(l+r)>>1;
if(node<=mid)
update(node,l,mid,ls(k),p,h);
else
update(node,mid+1,r,rs(k),p,h);
push_up(k);
}
int query(int nl,int nr,int l,int r,int k,int h,int s)
{
if(ans[k]>h+s)
return 0;
if(l==r)
{
int res=0;
while(!q[l].empty()&&q[l].top().first<=h+s)
{
res=(res+q[l].top().second)%mod;
q[l].pop();
}
ans[k]=q[l].empty()? 1e10+7:q[l].top().first;
return res;
}
int mid=(l+r)>>1,res=0;
if(nl<=mid)
res=(res+query(nl,nr,l,mid,ls(k),h,s))%mod;
if(nr>mid)
res=(res+query(nl,nr,mid+1,r,rs(k),h,s))%mod;
push_up(k);
return res;
}
signed main()
{
maxn=read(),w=read(),n=read();
for(register int i=1;i<=n;++i)
a[i].h=read(),a[i].l=read(),a[i].r=read(),a[i].s=read();
sum=w;
build(1,1,w);
sort(a+1,a+n+1);
for(register int i=1;i<=n;++i)
{
int tmp=query(a[i].l,a[i].r,1,w,1,a[i].h,a[i].s);
sum=(sum+tmp)%mod;
if(a[i].l==1)
update(a[i].r+1,1,w,1,(tmp<<1)%mod,a[i].h);
else
if(a[i].r==w)
update(a[i].l-1,1,w,1,(tmp<<1)%mod,a[i].h);
else
{
update(a[i].l-1,1,w,1,tmp,a[i].h);
update(a[i].r+1,1,w,1,tmp,a[i].h);
}
}
printf("%lld\n",sum);
return 0;
}
```
# Day10
## T1 排列
[原题](https://codeforces.com/problemset/problem/840/C)
显然，对完全平方数质因数分解得到的一定是若干个质数的偶数次幂的连乘，那么我们可以推出如果两个数相乘得到完全平方数，那么他们的质因数分解后的奇数次幂的质数完全相同。
~~然而其实你并不需要这些，因为 n<=300 你只需要暴力相乘就好了。~~
接下来就变成了这样一个问题，有若干种颜色的小球，每种有数量，求有多少种排列中相邻小球颜色均不相同。
这个东西巨大像容斥，但我不会/cy
但是我以前恰好看过[这篇文章](https://blog.csdn.net/df4516/article/details/102160607)而且还写过代码，所以这个东西我就在考场上秒了。
思路那里讲的挺明白的，这里不再赘述。
```cpp
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define int long long
int n,a[301],ans,sum,cnt,fac[401],inv[401],cur,f[2][401];
map<int,int> mp;
const int mod=1000000007;
inline int pw(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
inline int c(int x,int y)
{
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main()
{
//freopen("permutation.in","r",stdin);
//freopen("permutation.out","w",stdout);
scanf("%lld",&n);
fac[0]=inv[0]=1;
for(register int i=1;i<=400;++i)
{
fac[i]=fac[i-1]*i%mod;
inv[i]=pw(fac[i],mod-2);
}
for(register int i=1;i<=n;++i)
{
int x,val=1;
scanf("%lld",&x);
for(register int j=2;j*j<=x;++j)
{
bool flag=0;
while(x%j==0)
{
flag^=1;
x/=j;
}
if(flag)
val*=j;
}
if(x)
val*=x;
if(!mp[val])
mp[val]=++cnt;
++a[mp[val]];
}
f[cur][0]=1;
for(register int i=1;i<=cnt;++i)
{
cur^=1;
for(register int t=0;t<=a[i]+sum+1;++t)
f[cur][t]=0;
for(register int k=1;k<=a[i]&&k<=sum+1;++k)
for(register int j=0;j<=sum;++j)
for(register int l=0;l<=k&&l<=j;++l)
f[cur][j-l+a[i]-k]=(f[cur][j-l+a[i]-k]+f[cur^1][j]*c(a[i]-1,k-1)%mod*c(j,l)%mod*c(sum+1-j,k-l)%mod)%mod;
sum+=a[i];
}
ans=f[cur][0];
for(register int i=1;i<=cnt;++i)
ans=ans*fac[a[i]]%mod;
printf("%lld\n",ans);
return 0;
}
```
## T2 路线
[原题](https://codeforces.com/gym/100801)，K 题。
没空写代码，先用嘴巴㗅一下。
我们发现每个点的可以转移的范围是一个半圆加直线构成的图形，但是这样不好搞，我们把他拆开，两边分别计算，然后取并集就好了，这个东西只要每个点扫一遍就行，然后可以快乐 $O(1)$ 转移。
~~然而赛时数据非常的水，一大车立方暴力算法（包括我）草过了这题。~~