Atcoder Regular Contest 058 ~ 062

发表于 更新于

arc058-062

AtCoder Regular Contest 058

E. Iroha and Haiku

考虑 $X+Y+Z$ 很小，所以想办法把一个有序数列状态压缩。

一种想法是求出原序列的后缀和，然后压后缀和的每个元素。显然我们可以通过后缀和推出一个唯一的序列。

包含 $X,Y,Z$ 就等价于该序列后缀和是原序列的子序列。

最后发现可行方案不是很好做，处理不可行然后容斥即可。复杂度 $O(n2^n)$。

查看代码 
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 50
#define M 18
#define mod 1000000007
using namespace std;
int f[N][1<<M];
int main()
{
    int n,x,y,z;
    scanf("%d%d%d%d",&n,&x,&y,&z);
    int m=x+y+z,sm=(1<<m)-1;
    int o=(1<<(z-1))|(1<<(y+z-1))|(1<<(x+y+z-1));
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=10;j++)//a_i=j
            for(int s=0;s<=sm;s++)//the set of suf-sum
            if(f[i-1][s])
            {
                int t=((s<<j)|(1<<(j-1)))&sm;
                if((t&o)==o) continue;
                f[i][t]=(f[i][t]+f[i-1][s])%mod;
            }
    int ans=1;
    for(int i=1;i<=n;i++) ans=10ll*ans%mod;
    for(int s=0;s<=sm;s++) ans=(ans-f[n][s]+mod)%mod;
    printf("%d\n",ans);
    return 0;
}

F. Iroha Loves Strings

做法1：首先存下到每个点为之长度为 $i$ 的最小的字符串，然后暴力转移，就可以得到一个 $O(nk^2+nm)$ 的做法，但是不太行。

考虑优化：可以发现这个做法最大的问题在于存下了所有的长度的字符串。但事实上有一些字符串不可能成为最大值。

首先我们先 $O(nK)$ 大力背包预处理可以快速算出从某个点开始可不可行。这样对于点 $i$，如果一个长度为 $i$ 的字符串严格大于长度为 $j$ 的字符串（即字典序大于且不是前后缀关系）且均有解，那么 $i$ 一定不会成为最值。换句话说，所有可能成为最值的字符串均是一个最长字符串的前缀。

这样我们维护一个单调栈，使用 SA + ST 表预处理即可达到 $O(nk+M)$ 的复杂度。

做法2：考虑我们将题目转化为：给定一个字符串和若干关键点，每次到某一个关键点就可以跳到后面的任何一个。求走恰好 $k$ 步的最小字符串。

那么一个显然的想法就是：如果可以走，就贪心往最小的走。

用 bitset 压可以转移的位置和某字符集合的位置集合，暴力转移。

复杂度 $O(nk+\frac{nm\log C}{\omega})$。

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#define N 2010
#define M 1000001
#define K 10010
using namespace std;
char s[M];int p[N],len[N];
bitset<K>f[N];
bitset<M>g[65],w;
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+p[i]);
		len[i]=strlen(s+p[i]);
		p[i+1]=p[i]+len[i];
	}
	f[n+1].set(0);
	for(int i=n;i;i--) f[i]=f[i+1]|(f[i+1]<<len[i]);
	for(int i=0;i<p[n+1];i++) g[32+s[i]-'a'].set(i);
	for(int i=31;i;i--) g[i]=g[i<<1]|g[i<<1|1];
	w.set(0);
	for(int i=1,u;i<=k;i++,w<<=1)
	{
		for(int j=1;j<n;j++)
		if(w.test(p[j])) w.set(p[j+1]);
		for(int j=1;j<=n;j++)
		if(i+len[j]-1>k || !f[j+1].test(k-i-len[j]+1)) w.set(p[j],0);
		for(u=1;u<32;u=u<<1|!(g[u<<1]&w).any());
		putchar('a'+u-32); w&=g[u];
	}
	return 0;
}

AtCoder Regular Contest 059

E. Children and Candies

水题。首先 $x_i$ 的具体值对答案的影响是独立的。

考虑交换求和/求积顺序后，令 $f_{i,j}$ 表示 $i$ 位置分配了 $j$，之前的所有和。

有 $f_{i,j}=\sum_{j\leq i}\left(f_{i-1,k}\sum_{p=a_i}^{b_i}{p^{j-k}}\right)$。

随便前缀和一下就 $O(n^3)$ 了。

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 410
#define mod 1000000007
using namespace std;
int f[N][N],sm[N][N];//\sum_j{j^i}
int a[N],b[N];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=N-10;i++)
		for(int j=sm[0][i]=1;j<=N-10;j++)
			sm[j][i]=1ll*sm[j-1][i]*i%mod;
	for(int i=0;i<=N-10;i++)
		for(int j=1;j<=N-10;j++)
			sm[i][j]=(sm[i][j]+sm[i][j-1])%mod;
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=j;k++)
			f[i][j]=(f[i][j]+1ll*f[i-1][k]*(sm[j-k][b[i]]-sm[j-k][a[i]-1]+mod))%mod;
	printf("%d",f[n][m]);
	return 0;
}

F. Unhappy Hacking

以为是一道神仙题，结果是道脑筋急转弯题。

注意到按 $0,1$ 其实是本质相同的，也就是说长度相同的任意字符串出现的方案数相同。

所以直接算出长度为 $m$ 的字符串出现方案数即可。

设 $f_{i,j}$ 表示按了 $I$ 下，长度为 $j$ 的方案数。显然有 $f_{i,j}\rightarrow f_{i+1,\max(j-1,0),f_{i+1,j+1}}$。

复杂度 $O(n^2)$。

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 5010
#define mod 1000000007
using namespace std;
int f[N][N];char s[N];
int ksm(int a,int b=mod-2)
{
	int r=1;
	for(;b;b>>=1)
	{
		if(b&1) r=1ll*r*a%mod;
		a=1ll*a*a%mod;
	}
	return r;
}
int main()
{
	int n;
	scanf("%d%s",&n,s+1);
	int m=strlen(s+1);
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=n;j++)
		{
			(f[i][max(j-1,0)]+=f[i-1][j])%=mod;
			f[i][j+1]=(f[i][j+1]+2ll*f[i-1][j])%mod;
		}
	printf("%lld",1ll*f[n][m]*ksm(ksm(2,m))%mod);
	return 0;
}

AtCoder Regular Contest 060

E. Tak and Hotels

$\color{red}{skipped}$

F. Best Representation

第一眼幻视成串串划分，结果发现是神必题。

考虑给定的字符串如果不是全部相等，那么要么原来的串不是一个循环串，要么去掉首字母后不是一个循环串。所以答案至多为 $2$。

判掉 $1$ 和 $n$ 的情况之后，剩下的就变成询问从某个点分开左右是不是循环串。

这个直接枚举循环节然后打标记即可。复杂度 $O(n\log n)$。

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 500010
#define mod 1019260817
using namespace std;
char s[N];
int hs[N],bs[N];const int B=233;
int get(int l,int r){return (hs[r]-1ll*hs[l-1]*bs[r-l+1]%mod+mod)%mod;}
bool ban[N];
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=bs[0]=1;i<=n;i++) hs[i]=(1ll*hs[i-1]*B+(s[i]-'a'+1))%mod,bs[i]=1ll*bs[i-1]*B%mod;
	bool same=true;
	for(int i=2;i<=n;i++)
	if(s[i]!=s[i-1]) same=false;
	if(same){printf("%d\n1",n);return 0;}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;i*j+i<=n;j++)
		if(get(1,i)==get(i*j+1,i*j+i)) ban[i*j+i]=true;
		else break;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;i*j+i<=n;j++)
		if(get(n-i+1,n)==get(n-i*j-i+1,n-i*j)) ban[n-i*j-i]=true;
		else break;
	}
	if(!ban[n]){puts("1\n1");return 0;}
	int c=0;
	for(int i=1;i<n;i++)
	if(!ban[i]) c++;
	printf("2\n%d\n",c);
	return 0;
}

AtCoder Regular Contest 061

E. Snuke’s Subway Trip

考虑把每个可以直接到达的点之间建一个新点，向该颜色联通块中的点连一条无向边。

容易发现新图中的最短路就是答案的两倍。

查看代码 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<algorithm>
#define P pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define N 400010
using namespace std;
int nxt[N<<2],to[N<<2],head[N],cnt;
void add(int u,int v)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;head[u]=cnt;
}
int f[N];
int find(int x){return x==f[x]?f[x]:(f[x]=find(f[x]));}
vector<P >g[1000010];
int tmp[N],tt;
int idn=0,id[N];
queue<int>q;
bool vis[N];int dis[N];
int bfs(int s,int t)
{
	q.push(s);vis[s]=true;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(vis[v]) continue;
			vis[v]=true;dis[v]=dis[u]+1;
			q.push(v);
		}
	}
	return !vis[t]?-1:dis[t]/2;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int mx=0;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[w].push_back(MP(u,v));mx=max(mx,w);
	}
	idn=n;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=mx;i++)
	if(!g[i].empty())
	{
		tt=0;
		for(P u:g[i])
		{
			tmp[++tt]=u.fi;tmp[++tt]=u.se;
			f[find(u.fi)]=find(u.se);
		}
		for(int j=1;j<=tt;j++)
		{
			int u=tmp[j];if(vis[u]) continue;
			vis[u]=true;
			if(!id[find(u)]) id[find(u)]=++idn;
			id[u]=id[find(u)];
		}
		for(int j=1;j<=tt;j++) vis[tmp[j]]=false;
		for(int j=1;j<=tt;j++)
		{
			int u=tmp[j];if(vis[u]) continue;
			vis[u]=true;
			add(u,id[u]),add(id[u],u);
			//printf("add %d %d\n",u,id[u]);
		}
		for(int j=1;j<=tt;j++) vis[tmp[j]]=id[tmp[j]]=0,f[tmp[j]]=tmp[j];
	}
	printf("%d\n",bfs(1,n));
	return 0;
}

F. Card Game for Three

考虑 $A$ 要获胜必须在某一时刻拿出了 $n$ 张 $A$，且 $B,C$ 分别不超过 $m,k$。

那么就有答案等于 $\displaystyle\sum_{i=n}^{s}\binom{i}{n}3^{s-i}\sum_{j=i-n-k}^m\binom{i-n}{j}$。

枚举 $i$，发现后面那个式子可以递推处理。复杂度 $O(n)$。

查看代码 
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
41
42
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
#define mod 1000000007
using namespace std;
int fac[N],inv[N];
int ksm(int a,int b=mod-2)
{
    int r=1;
    for(;b;b>>=1)
    {
        if(b&1) r=1ll*r*a%mod;
        a=1ll*a*a%mod;
    }
    return r;
}
int C(int a,int b){return a<b || a<0 || b<0?0:1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;}
void init(int n=N-10)
{
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=ksm(fac[n]);
    for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int _3[N];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    init();
    int s=n+m+k,ans=0,r=1;
    if(m<k) swap(m,k);
    for(int i=_3[0]=1;i<=s;i++) _3[i]=_3[i-1]*3ll%mod;
    for(int i=0;i<=m+k;i++)
    {
        ans=(ans+1ll*r*C(n+i-1,n-1)%mod*_3[m+k-i]%mod)%mod;
        r=(r*2ll-C(i,k)-C(i,i-m)+2ll*mod)%mod;
    }
    printf("%d\n",ans);
    return 0;
}

AtCoder Regular Contest 062

E. Building Cubes with AtCoDeer

考虑枚举上顶面和下底面，那么剩下的四个面就是确定的。

用一个 $\text{map}$ 记录下每种面旋转同构后的结果，注意每取一个就要删除该元素以免计重。

复杂度 $O(n^2\log n)$。

查看代码 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define ll long long
#define N 410
using namespace std;
struct node{
    int p[4];
    node(int a=0,int b=0,int c=0,int d=0){p[0]=a;p[1]=b;p[2]=c;p[3]=d;}
    void rot(){for(int i=0;i<3;i++) swap(p[i],p[i+1]);}
}a[N];
bool operator <(const node a,const node b)
{
    for(int t=0;t<4;t++)
        if(a.p[t]!=b.p[t]) return a.p[t]<b.p[t];
    return false;
}
node operator <<(node a,int p){for(int i=0;i<p%4;i++) a.rot();return a;}
node operator |(node a,node b){return node(a.p[1],a.p[0],b.p[0],b.p[3]);}
vector<node> all_node(node a){return {a,a<<1,a<<2,a<<3};}
map<node,int>mp;
void ins(node u,int v){for(auto p:all_node(u)) mp[p]+=v;}
node sw[5];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i].p[0],&a[i].p[1],&a[i].p[2],&a[i].p[3]);
    for(int i=1;i<=n;i++) ins(a[i],1);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ins(a[i],-1);node u=a[i];
        for(int j=i+1;j<=n;j++)
        {
            ins(a[j],-1);
            for(auto v:all_node(a[j]))
            {
                for(int k=0;k<4;k++,u=u<<1,v=v<<3) sw[k]=u|v;
                bool can=true;
                for(int k=0;k<4 && can;k++)
                if(!mp.count(sw[k])) can=false;
                if(!can) continue;
                ll res=1;
                for(int k=0;k<4;k++) res*=mp[sw[k]],ins(sw[k],-1);
                for(int k=0;k<4;k++) ins(sw[k],1);
                ans+=res;
            }
            ins(a[j],1);
        }
    }
    printf("%lld",ans);
    return 0;
}

F. Painting Graphs with AtCoDeer

考虑如果给定的是一棵树，那么一定不存在同构情况。

而如果给定的是一个环，这显然就是 $Polya$ 定理。

如果给定的是环加上若干条边，可以证明的是任意两条边都可以互换。

所以缩一个点双，然后判断每个点双：如果只有两个点直接乘 $k$，否则判断是那种情况。

由于 $n$ 只有 $50$，随便怎么搞都行。

查看代码 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 210
#define mod 1000000007
using namespace std;
int nxt[N<<1],to[N<<1],head[N],cnt;
void add(int u,int v)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}
vector<int>bc[N];int bt;
int dfn[N],low[N],idn;
int st[N],tp;
void dfs(int u,int p)
{
	low[u]=dfn[u]=++idn;
	st[++tp]=u;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				++bt;
				while(st[tp]!=v) bc[bt].push_back(st[tp--]);
				bc[bt].push_back(st[tp--]);bc[bt].push_back(u);
			}
		}
		else if(v!=p) low[u]=min(low[u],dfn[v]);
	}
}
int ksm(int a,int b=mod-2)
{
	int r=1;
	for(;b;b>>=1)
	{
		if(b&1) r=1ll*r*a%mod;
		a=1ll*a*a%mod;
	}
	return r;
}
int fac[N],inv[N];
int C(int x,int y){return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
void init(int n=N-10)
{
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n]);
	for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
bool vis[N];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	init();
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) dfs(i,0);
	int ans=1;
	for(int p=1;p<=bt;p++)
	{
		int rd=0,pn=bc[p].size();
		if(pn==2){ans=1ll*ans*k%mod;continue;}
		for(int u:bc[p]) vis[u]=true;
		for(int u:bc[p])
			for(int i=head[u];i;i=nxt[i])
			if(to[i]>u && vis[to[i]]) rd++;
		for(int u:bc[p]) vis[u]=false;
		if(pn==rd)
		{
			int res=0;
			for(int i=1;i<=pn;i++) res=(res+ksm(k,gcd(i,pn)))%mod;
			res=1ll*res*ksm(pn)%mod;
			ans=1ll*ans*res%mod;
		}
		else ans=1ll*ans*C(rd+k-1,k-1)%mod;
	}
	printf("%d\n",ans);
	return 0;
}