https://atcoder.jp/contests/agc047/tasks

A - Integer Product

 

题意：给定一个实数数列，0<Ai<1040 < A_i < 10^4，且 AiA_i 小数点后最多有 9 位，问有几对数相乘得到整数。

由于 AiA_i 位数有限，因此化为分数后分母上必定是 2p⋅5q2^p\cdot 5^q，所以如果要相乘得到整数，只需要考虑每个数的 22 和 55 的幂次即可。

由于可能有负幂次，所以要先乘以 10910^9 确保分母都去掉。乘的过程中又会有误差问题，如果用 (longlong)(longlong) 强制转换会有误差，需要用 llround(x⋅1e9)llround(x\cdot 1e9).

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
#include <bits/stdc++.h>
#define debug(x) cout << ##x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
ll a[N];
ll cnt[100][100], ans;
int two[N], five[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		double x;
		scanf("%lf", &x);
		a[i] = llround(x * 1e9);
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			two[i]++;
		}
		while (a[i] % 5 == 0) {
			a[i] /= 5;
			five[i]++;
		}
		cnt[two[i]][five[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 18 - two[i]; j <= 44; j++) {
			for (int k = 18 - five[i]; k <= 19; k++) {
				ans += cnt[j][k];
			}
		}
		if (two[i] >= 9 && five[i] >= 9)ans--;
	}
	printf("%lld\n", ans / 2);
	return 0;
}

 

B - First Second

 

题意：对于一个字符串，每次操作可以删除前两个字符中任意一个。给定 n 个字符串，问有几对字符串可以通过操作其中一个任意次得到另一个字符串。保证每个串不同。

Trie

S 串能通过操作变为 T 串，等价于 S 串第二个字符起的后缀是 T 串的后缀，且 S 的第一个字符在 T 串该后缀前出现过。

把字符串都反过来，插入 Trie 中，短串是长串后缀变成长串从根开始的路径等于短串。再记录长串中剩下的字符，暴力找即可。

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
#include <bits/stdc++.h>
#define debug(x) cout << ##x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
string s;
ll ans;
int ch[N][30];
int cnt[30], sum[N], tot;
void ins(const string& s) {
	int rt = 0;
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; s[i]; i++)cnt[s[i] - 'a']++;
	for (int i = 0; s[i]; i++) {
		for (int j = 0; j < 26; j++) {
			if (ch[rt][j] && cnt[j])ans += sum[ch[rt][j]];
		}
		if (!ch[rt][s[i] - 'a'])ch[rt][s[i] - 'a'] = ++tot;
		cnt[s[i] - 'a']--;
		rt = ch[rt][s[i] - 'a'];
	}
	sum[rt]++;
}
vector<string>vc;
bool cmp(const string& a, const string& b){
	return a.length() < b.length();
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		reverse(s.begin(), s.end());
		vc.push_back(s);
	}
	sort(vc.begin(), vc.end(), cmp);
	for (int i = 0; i < n; i++) {
		ins(vc[i]);
	}
	cout << ans << endl;
	return 0;
}

 

C - Product Modulo

 

题意：给定数列 AA，求 ∑i=1n−1∑j=i+1n(Ai⋅Ajmod  200003)\sum_{i=1}^{n-1}\sum_{j=i+1}^n(A_i\cdot A_j\mod 200003)。

原根+FFT

通过原根把乘法变成加法的技巧。

由原根的性质可知 gg 为 mm 的原根，等价于 {g0,g1,⋯ ,gφ(m)−1}\{g^0,g^1,\cdots,g^{\varphi(m)-1}\} 为 mm 的一个简化剩余系，即 {g0,g1,⋯ ,gφ(m)−1}\{g^0,g^1,\cdots,g^{\varphi(m)-1}\} 对 mm 的余数取遍 [0,m−1][0,m-1] 中与 mm 互质的数且不重复。

由于 200003200003 是质数，22 是 200003200003 的一个原根，所以 {20,21,⋯ ,2200002}\{2^0,2^1,\cdots,2^{200002}\} 取遍 [0,200002][0,200002] 且不重复。

AiA_i 对应与其同余的 2p2^p，则 Ai⋅Aj=2p+qA_i\cdot A_j=2^{p+q}，p,q∈[0,200002]p,q\in[0,200002]，则 p+q∈[0,400004]p+q\in[0,400004]。

遍历 2k,k∈[0,400004]2^k,k\in[0,400004]，产生的贡献为 (2k%200003)⋅∑p+q=kcntp⋅cntq(2^k\% 200003)\cdot\sum_{p+q=k}cnt_p\cdot cnt_q，其中 cntpcnt_p 为与 2p2^p 同余的 AiA_i 的个数。FFT 求 cntcnt 数组自己和自己的卷积。

还要注意自己和自己不能产生贡献，以及每对数产生了两次贡献。

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
95
96
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 200003;
const double PI = acos(-1.0);
struct Complex {
	double x, y;
	Complex(double _x = 0.0, double _y = 0.0) {
		x = _x;
		y = _y;
	}
	Complex operator-(const Complex &b) const {
		return Complex(x - b.x, y - b.y);
	}
	Complex operator+(const Complex &b) const {
		return Complex(x + b.x, y + b.y);
	}
	Complex operator*(const Complex &b) const {
		return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
	}
};
void change(Complex y[], int len) {
	int i, j, k;
	for (i = 1, j = len / 2; i < len - 1; i++) {
		if (i < j) swap(y[i], y[j]);
		k = len / 2;
		while (j >= k) {
			j = j - k;
			k = k / 2;
		}
		if (j < k) j += k;
	}
}
void fft(Complex y[], int len, int on) {	//0-len-1
	change(y, len);
	for (int h = 2; h <= len; h <<= 1) {
		Complex wn(cos(2 * PI / h), sin(on * 2 * PI / h));
		for (int j = 0; j < len; j += h) {
			Complex w(1, 0);
			for (int k = j; k < j + h / 2; k++) {
				Complex u = y[k];
				Complex t = w * y[k + h / 2];
				y[k] = u + t;
				y[k + h / 2] = u - t;
				w = w * wn;
			}
		}
	}
	if (on == -1) {
		for (int i = 0; i < len; i++) {
			y[i].x /= len;
		}
	}
}
int m, n;
int mp[N], mo[N];
int f[N], a[N];
Complex b[N << 2], c[N << 2];
int main() {
	scanf("%d", &m);
	int mx = 2 * mod, len = 1;
	while (len <= mx)len <<= 1;
	int p = 1;
	for (int i = 0; i < len; i++) {
		if (i < mod - 1)mp[p] = i;
		mo[i] = p;
		p = p * 2 % mod;
	}
	for (int i = 1; i <= m; i++) {
		int x;
		scanf("%d", &x);
		if (x)a[++n] = x;
	}
	for (int i = 1; i <= n; i++) {
		f[mp[a[i]]]++;
	}
	for (int i = 0; i < mod - 1; i++) {
		b[i] = { f[i] * 1.0,0.0 };
	}
	fft(b, len, 1);
	for (int i = 0; i < len; i++)c[i] = b[i] * b[i];
	fft(c, len, -1);
	ll ans = 0;
	for (int i = 0; i < len; i++) {
		ans += 1ll * mo[i] * (ll)(c[i].x + 0.5);
	}
	for (int i = 1; i <= n; i++) {
		ans -= 1ll * a[i] * a[i] % mod;
	}
	printf("%lld\n", ans / 2);
	return 0;
}