D - Anticube

说实话质因数分解的题都挺有意思的

首先对于每个数，显然里面存在的质数三次方的因子都是无贡献的，那么将其的每个质因数化简，即对于质因子 $p^k$，将其变为 $p^{k ~ mod ~ 3}$

那么两个数若乘积为完全立方数，则必须满足它们的每一个相同质因子都是“互补的”（即次数相加为 $0$ 或 $3$），同时显然一定不存在大于一个 $> \sqrt[3]n$ 的质因数 $p$，那么解法就很显然了

就是筛出 $[2, \sqrt[3]n]$ 的质数，然后对每一个数进行化简，然后将化简后的数的计数器加一，最后在所有两两“互补”的数中取 $max$ 求和即可

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <cstdio>
#include <cstring>
#include <tr1/unordered_map>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 2200 + 10;

int N;
LL a[MAXN], newa[MAXN]= {0};

int prime[MAXM]= {0}, pcnt = 0;
bool visit[MAXM]= {false};
const int MAX = 2200;
void sieve () {
	for (int i = 2; i <= MAX; i ++) {
		if (visit[i]) continue;
		prime[++ pcnt] = i;
		for (int j = i << 1; j <= MAX; j += i)
			visit[j] = true;
	}
}

tr1::unordered_map<LL, int> mapp, ccnt;
int ind = 0;
inline LL power (LL x, int p) {
	LL cnt = 1;
	for (int j = 1; j <= p; j ++)
		cnt *= x;
	return cnt;
}
pair<LL, LL> save[MAXN];
int solve () {
	int ans = 0;
	save[++ ind] = make_pair (1, 0);
	mapp[0] = mapp[1] = 1;
	for (int i = 1; i <= N; i ++) {
		LL p = a[i];
		LL cnt = 1, ano = 1;
		for (int j = 1; j <= pcnt; j ++)
			if (! (p % prime[j])) {
				int times = 0;
				while (! (p % prime[j]))
					p /= prime[j], times ++;
				times %= 3;
				if (times > 0)
					ano *= power (prime[j], 3 - times);
				cnt *= power (prime[j], times);
			}
		if (a[i] != 1 && cnt == 1 && p == 1) {
			ccnt[0] ++;
			continue;
		}
		ccnt[cnt * p] ++, newa[i] = cnt * p;
		if (mapp[cnt * p]) continue;
		if (p > 1) {
			LL sqr = sqrt (p);
			if (sqr * sqr == p) {
				save[++ ind] = make_pair (cnt * p, ano * sqr);
				mapp[cnt * p] = mapp[ano * sqr] = ind;
			}
		}
		else {
			save[++ ind] = make_pair (cnt, ano);
			mapp[cnt] = mapp[ano] = ind;
		}
	}
	ccnt[0] = min (ccnt[0], 1), ccnt[1] = min (ccnt[1], 1);
	for (int i = 1; i <= ind; i ++)
		ans += max (ccnt[save[i].first], ccnt[save[i].second]);
	for (int i = 1; i <= N; i ++)
		if (! mapp[newa[i]])
			ans ++;
	return ans;
}

template<typename T>
T getnum () {
	T num = T ();
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum<int> ();
	for (int i = 1; i <= N; i ++)
		a[i] = getnum<LL> ();
	sieve ();
	int ans = solve ();
	cout << ans << endl;

	return 0;
}

/*
8
1
2
3
4
5
6
7
8
*/

/*
6
2
4
8
16
32
64
*/

/*
10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999
*/

/*
10
1
10
100
2368593037
38192375
218391929
572421321
2
16
32
*/

E - Sequential operations on Sequence

先考虑所有只存在增加长度的操作

那么可以从后往前枚举，考虑后面的操作对前面的贡献

那么对于每一个位置 $p$，它相当于是第一个小于它的位置 $q$ 算 $p / q$ 次，然后再算一次 $p ~ mod ~ q$，故递归即可

然后对于减少长度的操作，显然该操作之前所有长度大于等于当前长度的操作都是无用的，故只需初始化时取递增的操作即可转化为只存在增加长度的操作的集合

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;

int N, M;
LL que[MAXM]= {0};
int tail = 0;

LL suffix[MAXM]= {0};
int value[MAXM]= {0};
int findpos (int limit, LL delta) {
	if (delta < que[1]) return delta;
	int posi = upper_bound (que + 1, que + limit, delta) - que - 1;
	LL add = delta / que[posi], rest = delta % que[posi];
	suffix[posi] += suffix[limit] * add;
	return findpos (limit, rest);
}
LL subsum[MAXN]= {0};
void solve () {
	value[1] = que[1], suffix[tail] = 1;
	for (int i = tail; i >= 2; i --) {
		int val = findpos (i, que[i]);
		value[i] = val;
	}
	for (int i = tail; i >= 1; i --)
		subsum[value[i]] += suffix[i];
	for (int i = N - 1; i >= 1; i --)
		subsum[i] += subsum[i + 1];
}

template<typename T>
T getnum () {
	T num = T ();
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}
inline void write (LL x) {
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}
inline void println (LL x) {
	write (x), puts ("");
}

int main () {
	N = getnum<int> (), M = getnum<int> ();
	que[++ tail] = N;
	for (int i = 1; i <= M; i ++) {
		LL posi = getnum<LL> ();
		while (tail >= 1 && que[tail] >= posi) tail --;
		que[++ tail] = posi;
	}
	solve ();
	for (int i = 1; i <= N; i ++)
		println (subsum[i]);

	return 0;
}

/*
5 3
6
4
11
*/

/*
10 10
9
13
18
8
10
10
9
19
22
27
*/

/*
10 10
15
22
12
18
16
2
18
18
10
18
*/

/*
10 10
6
26
2
12
12
2
8
10
6
20
*/

/*
10 10
10
24
2
18
18
18
16
18
6
4
*/

F - Fraction of Fractal

于是我又看错了一次题目。。

对于左右、上下复制后都连通的情况，显然答案为 $1$

对于左右、上下复制后都不连通的情况，设其黑点个数为 $p$，则答案显然为 $p^{k - 1}$

那么现在假设左右复制后连通，上下复制后不连通，令其最终状态黑点个数 $x_n$，左右连通的点组（即 $##$）个数为 $y_n$，那么思考一下，答案即为 $x_n - y_n$，考虑转移，那么 $y_i$ 会只会在最左端和最右端连通时增加，故令 $z_i$ 表示 $i$ 状态时最左和最右连通的个数，则转移即为
$$
\begin{aligned}
x_i &= x_{i - 1}^2 \\
y_i &= x_{i - 1} \times y_{i - 1} + z_{i - 1} \times y_{i - 1} \\
z_i &= z_{i - 1}^2
\end{aligned}
$$
然后发现这样子满足矩阵乘法，即可构造矩阵
$$
\begin{bmatrix}
x_1 & y_1 \\
0 & z_1
\end{bmatrix}
$$

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
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 1000 + 10;

LL power (LL x, LL p) {
	LL cnt = 1;
	while (p) {
		if (p & 1)
			cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

struct Matrix {
	LL a[3][3];

	Matrix () {
		memset (a, 0, sizeof (a));
	}
} ;
Matrix operator * (const Matrix& A, const Matrix& B) {
	Matrix ret = Matrix ();
	for (int i = 1; i <= 2; i ++)
		for (int j = 1; j <= 2; j ++)
			for (int k = 1; k <= 2; k ++)
				ret.a[i][j] = (ret.a[i][j] + A.a[i][k] * B.a[k][j] % MOD) % MOD;
	return ret;
}
LL matpower (Matrix x, LL k) {
	Matrix ret = Matrix ();
	ret.a[1][1] = ret.a[2][2] = 1;
	while (k) {
		if (k & 1)
			ret = ret * x;
		x = x * x;
		k >>= 1;
	}
	return (ret.a[1][1] - ret.a[1][2] + MOD) % MOD;
}

int N, M;
LL k;
char map[MAXN][MAXN];

int main () {
	scanf ("%d%d%lld", & N, & M, & k);
	int tol = 0, toup = 0;
	int lr = 0, ud = 0;
	int cnt = 0;
	for (int i = 1; i <= N; i ++) {
		scanf ("%s", map[i] + 1);
		for (int j = 1; j <= M; j ++)
			if (map[i][j] == '#') {
				cnt ++;
				tol += map[i][j - 1] == '#';
				toup += map[i - 1][j] == '#';
			}
		if (map[i][1] == '#' && map[i][M] == '#') lr ++;
	}
	for (int j = 1; j <= M; j ++)
		if (map[1][j] == '#' && map[N][j] == '#') ud ++;
	if (! lr && ! ud) {
		cout << power (1ll * cnt, k - 1) << endl;
		return 0;
	}
	if (lr && ud) {
		puts ("1");
		return 0;
	}
	if (! lr) swap (lr, ud), swap (tol, toup);
	Matrix x = Matrix ();
	x.a[1][1] = cnt, x.a[1][2] = tol, x.a[2][2] = lr;
	LL ans = matpower (x, k - 1);
	cout << ans << endl;

	return 0;
}

/*
3 3 3
.#.
###
#.#
*/

/*
11 15 1000000000000000000
.....#.........
....###........
....####.......
...######......
...#######.....
..##.###.##....
..##########...
.###.....####..
.####...######.
###############
#.##..##..##..#
*/