AGC047部分题解_[agc047b] first second

A

问有多少个数对 $(i,j)$ 满足 $i<j$ 且 $a_i\times a_j$ 是个整数。

将所有数乘上 $10^9$ 之后，就转化成了 $a_i\times a_j$ 是 $10^{18}$ 的倍数。

$x$ 是 $10^{18}$ 的倍数，需要满足 $x$ 质因数分解之后 $2$ 和 $5$ 的数量不少于 $18$ 个，那么将所有 $a_i$ 分解一下得到 $2$ 和 $5$ 的质因子个数，然后就变成了一个二维偏序问题，但是这题数据范围很小，直接暴力搞即可。

代码如下：

#include <cmath>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
#define ll long long
#define it map<par,int>::iterator
 
int n;
struct par{
	int x,y;par(int xx,int yy):x(xx),y(yy){}
	bool operator <(const par &B)const{return x==B.x?y<B.y:x<B.x;}
};
map<par,int>mp;
ll ans=0;
 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		long double x;cin>>x;
		x*=1e9;ll y=(ll)(x+1e-2);int c=0,d=0;
		while(y%2==0)y/=2,c++;
		while(y%5==0)y/=5,d++;
		mp[par(c,d)]++;
	}
	for(it i=mp.begin();i!=mp.end();i++){
		for(it j=mp.begin();j!=mp.end();j++){
			if(i->first.x+j->first.x>=18&&i->first.y+j->first.y>=18){
				if(i==j)ans+=1ll*i->second*(i->second-1);
				else ans+=1ll*i->second*j->second;
			}
		}
	}
	cout<<ans/2ll;
}
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

B

对于一个字符串，一次操作可以删除它的第一或第二个字符，现在给你 $n$ 个字符串，问有多少对字符串 $(s_i,s_j)$ 满足 其中一个可以通过进行若干次操作得到另一个。

容易发现，如果 $a$ 通过若干次操作能得到 $b$，那么 $b$ 去掉第一个字符后，一定是 $a$ 的后缀，$a$ 去掉这个后缀之后，剩下的部分肯定包含 $b$ 的第一个字符。

然后我就愉快的码了一个哈希，为了保证正确性用了map，然后就T飞了。

优秀点的做法是造一棵字典树，将每个字符串倒着插进去，在每个节点上存一个大小为 $26$ 的数组，$t[i]$ 表示有多少个字符串去掉这个后缀后，剩下的部分包含第 $i$ 个字符。

最后将每个字符串丢进去跑一遍就得到答案了，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 200010
#define ll long long
 
int n,len[maxn],t[maxn];
string s[maxn];
struct node{
	int t[26];
	node *son[26];
	node(){for(int i=0;i<26;i++)t[i]=0,son[i]=NULL;}
}*root=new node();
void insert(string &S,int &l){
	for(int i=0;i<l;i++)t[S[i]-'a']++;
	node *now=root;
	for(int i=l-1;i>=0;i--){
		for(int j=0;j<26;j++)if(t[j])now->t[j]++;
		if(!now->son[S[i]-'a'])now->son[S[i]-'a']=new node();
		now=now->son[S[i]-'a'];t[S[i]-'a']--;
	}
}
ll ans=0;
 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];len[i]=s[i].length();
		insert(s[i],len[i]);
	}
	for(int i=1;i<=n;i++){
		node *now=root;
		for(int j=len[i]-1;j>=1;j--)now=now->son[s[i][j]-'a'];
		ans+=now->t[s[i][0]-'a']-1;
	}
	cout<<ans;
}
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

C

给出一个序列 $a$，求 ${\sum }_{i=1}^n{\sum }_{j=i+1}^n(a_i\times a_j\mathrm{m}\mathrm{o}\mathrm{d}200003)$。

由于模数不大，容易想到 求出答案中 $0$ ~ $200002$ 每个数的出现次数 这样的做法。

有一个小技巧，先找到 $200003$ 的一个原根（比如 $2$），然后将每个数转化成 $2^k$ 的形式，令 $F[i]$ 表示序列中 $2^i$ 的出现次数，然后将 $F$ 和自己做个卷积再去去重什么的就得到答案了。

代码如下;

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 4000010
#define mod 200003
#define ll long long
#define eps 1e-2
 
int n,m,a[maxn],c[maxn],d[maxn];
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
struct comp{
	double x,y;comp(double xx=0,double yy=0):x(xx),y(yy){}
	comp operator +(const comp &B){return comp(x+B.x,y+B.y);}
	comp operator -(const comp &B){return comp(x-B.x,y-B.y);}
	comp operator *(const comp &B){return comp(x*B.x-y*B.y,x*B.y+y*B.x);}
}F[maxn],G[maxn];
int limit,r[maxn];
const double Pi=acos(-1);
void dft(comp *f,int type)
{
	for(int i=1;i<limit;i++)
	if(i<r[i])swap(f[i],f[r[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		comp wn(cos(Pi/mid),type*sin(Pi/mid));
		for(int j=0;j<limit;j+=(mid<<1)){
			comp w(1,0);
			for(int i=0;i<mid;i++,w=w*wn){
				comp x=f[j+i],y=f[j+i+mid]*w;
				f[j+i]=x+y;f[j+i+mid]=x-y;
			}
		}
	}
	if(type==-1)for(int i=0;i<limit;i++)f[i].x/=limit;
}
 
 
int main()
{
	scanf("%d",&n);int len=mod-1;
	for(int i=0;i<len;i++)d[i]=ksm(2,i),c[d[i]]=i;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i])F[c[a[i]]].x+=1;
	}
	int lg=0;limit=1;while(limit<=2*len)limit<<=1,lg++;
	for(int i=1;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));
	dft(F,1);for(int i=0;i<limit;i++)F[i]=F[i]*F[i];dft(F,-1);
	
	for(int i=1;i<=n;i++)if(a[i])F[c[a[i]]+c[a[i]]].x-=1;//自己乘自己不算，因为要满足i<j
	ll ans=0;
	for(int i=0;i<limit;i++)ans+=(ll)(F[i].x/2+1e-1)*d[i%len];//这里出现次数要除以2，还是因为i<j
	printf("%lld",ans);
}
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

D

有两棵完全一样的高度为 $H$ 的完全二叉树，现在将他们的叶子节点之间连边（这些边称为特殊边），$p_i$ 表示第一棵树的第 $i$ 个叶子结点与第二课树的第 $p_i$ 个叶子结点之间连了边。保证 $p_i$ 是 $1$ ~ $2^{H-1}$ 的一个排列。
现在定义一个合法的简单环满足：经过恰好两条不同的特殊边。一个简单环的贡献是上面所有点的编号乘积，现在要求所有合法简单环的贡献之和。

设经过的两条特殊边为 $(a,b),(c,d)$，其中 $a,c$ 在第一棵树内，$c,d$ 在第二棵树内。

考虑枚举 $a,c$ 的 $lca$，设为 $A$，先遍历 $A$ 的左子树，并通过左子树走到第二棵树上，对于走到的点 $B$，让 $sum[B]$ 加上一路上所有点的乘积，走完之后，$sum[B]$ 就表示点 $A$ 经过 $(a,b)$ 到达点 $B$ 的所有路径贡献之和。

然后遍历 $A$ 的右子树，也通过右子树走到第二棵树上，对于走到的节点 $C$，统计所有 $b,d$ 的 $lca$ 为 $C$ 的父亲的路径的贡献之和，即 $sum[D]\times \lfloor \frac{C}{2}\rfloor \times prod$，其中 $D$ 是 $C$ 的兄弟节点，$prod$ 是从 $A$ 一路走来所有点的乘积。

由于第一棵树中每个叶子只会被遍历 $H$ 次，每次遍历又要在第二棵树中走 $H$ 的距离，所有总的时间复杂度大概是 $O(H^2{2}^{H-1})$。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn (1<<18)+1
#define mod 1000000007

int H,n,p[maxn];
int vis[maxn],id=0,sum[maxn];
int ans=0;
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void go2(int x,int prod,bool left){
	if(x==1)return;
	prod=1ll*prod*x%mod;
	if(left){
		if(vis[x]<id)vis[x]=id,sum[x]=0;
		add(sum[x],prod);
	}
	else{
		if(vis[x^1]<id)vis[x^1]=id,sum[x^1]=0;
		add(ans,1ll*(x/2)*prod%mod*sum[x^1]%mod);
	}
	go2(x/2,prod,left);
}
void go(int x,int prod,bool left){
	prod=1ll*prod*x%mod;
	if(x>=n){go2(n+p[x-n+1]-1,prod,left);return;};
	go(x*2,prod,left);
	go(x*2+1,prod,left);
}

int main()
{
	scanf("%d",&H);n=1<<(H-1);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1;i<n;i++){
		id++;
		go(i*2,i,true);
		go(i*2+1,1,false);
	}
	printf("%d",ans);
}
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
'
运行
运行