NIO‘s Sword（思维，取模，推公式）

NIO’s Sword

题意
一共有 n 个怪兽，有一把初始能量为 0 的宝剑。
每次可以在某一时刻将宝剑的能量升级：如果原来能量为 $a$，升级之后能量变为 $a\ast 10+x$，x 为 $0-9$ 中任选的一个数。
如果想要击败第 $i(2\le i\le n)$ 只怪兽，需要保证第 $i-1$ 只怪兽已经被击败。
在击败第 i 只怪兽时，宝剑的能量 a 需满足 $A\equiv i(\mathrm{mod}n).$
问，击败所有怪兽最少需要升级多少次？

$1\le n\le 10^6$

思路
如果击败第 i 个怪兽时，宝剑的能量值为 a，并且 a%n = i，而要击败第 i+1 个怪兽是由 a 继续升级的，也就是由 i 继续升级，所以就是看将值 i 升级到 t 满足 t%n = (i+1)%n 最少需要升级多少次。

升级 1 次后的能量为：$a\ast 10+x$，x 属于 $[0,9]$；
升级 2 次后的能量为：$a\ast 10^2+x$，x 属于 $[0,99]$；
…
升级 k 次的能量为：$a\ast 10^k+x$，x 属于 $[0,10^k-1]$；

要使得：$$(a\ast 10^k+x)\mathrm{mod}n=b\mathrm{mod}n$$

• 如果 $a\ast 10^k(\mathrm{mod}n)\le b(\mathrm{mod}n)$ 时，$x=b(\mathrm{mod}n)-a\ast 10^k(\mathrm{mod}n)$；
• 否则，$(a\ast 10^k+x)\mathrm{mod}n$ 就应该变为 $b(\mathrm{mod}n)+n$，要使得 x 尽可能小，那么 $x=n+b(\mathrm{mod}n)-a\ast 10^k(\mathrm{mod}n)$

如果 x 在这次升级所能达到的范围内的话，说明就是这次升级就是满足的。

而 n 最大到 1e6，那么 x 最多 6 次就可以构造出任意小于 n 的值，所以最多升级 6 次，暴力枚举每次升级。

最后注意当 n 为 1 时，任意能量值 a 都同余于 1%1，所以能量值为0也行，不需要升级，注意特判。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

int pd(int a, int b)
{
	int k = 0;
	while(1)
	{
		k ++;
		a = a*10 % n;
		
		int x;
		if(a <= b) x = b - a;
		else x = n + b - a;
		if(x <= pow(10, k)-1) break;
	}
	return k;
}

signed main(){
	Ios;
	cin >> n;
	
	if(n == 1){
		cout << 0; return 0;
	}
	
	int ans = 0;
	for(int i=0;i<n;i++)
	{
		ans += pd(i, (i+1)%n);
	}
	cout << ans;
	
	return 0;
}
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

经验
这样的取模的式子一直不会化，总觉得取模之后原来的数就变的面目全非了，然后就不敢往下化，怕不等。
其实取模在乘法和加法运算时和原式是毫无影响的，该咋化就咋化，不用怕。

感谢队友大半夜教会我！！

---

Jobs (Easy Version)

题意
给定 n 个集合，每个集合有 mi 个三元组 {$x_j,y_j,z_j$}。
一共 q 次询问，每次询问给定一个三元组 {a, b, c}，问一共有多少个集合满足，其中存在一个三元组，其三个元素都不超过 {a, b, c}？

$1\le n\le 10,1\le q\le 2\times 10^6,1\le x_j,y_j,z_j\le 400$

思路
一共 1e6 次询问，每次询问要处理 10 个集合，那么留给每个集合的计算时间就很少了，暴力枚举不行。

一种非常巧妙的思路是，构造二维前缀最小值。
对于三元组{x, y, z}，可以将矩阵 (x, y) 位置上的值 f[x, y] 置为 z。
最后将 f[][] 数组更新成前缀最小值，即 (1,1) 位置到 (x, y) 位置的所有位置中，z 的最小值。
后面对于每次询问 {a, b, c}，肯定要从 (1, 1) 到 (a, b) 位置中找到最小值，即 f[a, b]，判断其和 c 的大小关系。如果最小值不超过 c，则说明存在某个位置 (x, y)，其值 z = f[x, y] 不超过 c，即找到满足三元组。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 998244353;
int T, n, m;
int a[N];
int f[11][410][410];

int solve(int x, int y, int z)
{
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
		if(f[i][x][y] <= z) cnt++;
	}
	return cnt;
}

int qmi(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

signed main(){
	Ios;
	cin >> n >> m;
	
	for(int i=0;i<=n;i++)
		for(int j=0;j<=400;j++)
			for(int k=0;k<=400;k++)
				f[i][j][k] = 1e9;
	
	for(int i=1;i<=n;i++)
	{
		int k; cin >> k;
		while(k--)
		{
			int x, y, z; cin >> x >> y >> z;
			f[i][x][y] = min(f[i][x][y], z);
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=400;j++){
			for(int k=1;k<=400;k++)
			{
				f[i][j][k] = min(f[i][j][k], f[i][j-1][k]);
				f[i][j][k] = min(f[i][j][k], f[i][j][k-1]);
			}
		}
	}
	
	int seed;
	cin >> seed;

	std::mt19937 rng(seed);
	std::uniform_int_distribution<> u(1,400);
	
	int lastans=0, ans = 0;
	for (int i=1;i<=m;i++)
	{
	    int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
	    int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
	    int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
	    lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
	    ans = (ans + lastans * qmi(seed, m-i) % mod) % mod;
	}
	cout << ans;
	
	return 0;
}
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

还有一种比较巧妙的思路：
类似于单调栈，如果对于当前三元组 {x, y, z}，发现集合中存在一个三元组{a, b, c}满足，其三个元素都比当前三元组的三个元素小，那么当每次询问的时候，只需要判断最小值是否满足，那么当前三元组 {x, y, z} 就没有存在的意义，完全可以删掉。

所以可以先按照三元素大小将集合中三元组从小到大排序，维护一个vector表示最后剩下的三元组，遍历所有三元组，如果对于当前三元组发现vector中存在一个三元组比当前优，那么当前的就不要了，否则就加到vector里。

这样删过之后，对于三个位置，要么有比它大的，要么有比它小的，最多只有 8 个三元组了，然后每次询问遍历每个集合的 8 个三元组即可。

这样的话完全不用考虑每个元素的大小。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 998244353;
int T, n, m;
struct node{
	int x, y, z;
};
vector<node> a[12], v[12];

bool cmp(node a, node b){
	if(a.x != b.x) return a.x < b.x;
	else if(a.y != b.y) return a.y < b.y;
	return a.z < b.z;
}

int solve(int x, int y, int z)
{
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
		for(node t : v[i])
		{
			if(t.x <= x && t.y <= y && t.z <= z){
				cnt ++;
				break;
			}
		}
	}
	return cnt;
}

int qmi(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

signed main(){
	Ios;
	cin >> n >> m;
	
	for(int i=1;i<=n;i++)
	{
		int k; cin >> k;
		while(k--)
		{
			int x, y, z; cin >> x >> y >> z;
			a[i].push_back({x, y, z});
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		sort(a[i].begin(), a[i].end(), cmp);
		for(node t : a[i])
		{
			int flag = 0;
			for(node left : v[i])
			{
				if(left.x <= t.x && left.y <= t.y && left.z <= t.z) flag = 1;
			}
			if(!flag) v[i].push_back(t);
		}
	}
	
	int seed;
	cin >> seed;

	std::mt19937 rng(seed);
	std::uniform_int_distribution<> u(1,400);
	
	int lastans=0, ans = 0;
	for (int i=1;i<=m;i++)
	{
	    int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
	    int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
	    int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
	    lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
	    ans = (ans + lastans * qmi(seed, m-i) % mod) % mod;
	}
	cout << ans;
	
	return 0;
}
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

感谢友队提供思路，很强！

---

Particle Arts

题意
一共 n 个粒子，每个粒子有权值 a_i。
如果两个值为 a 和 b 的粒子相碰的话，这两个粒子将会消失，同时产生两个新粒子，权值分别为 a&b 和 a|b。
这 n 个粒子两两随意碰撞，很长时间之后，所有点权值的方差收敛到一个稳定值。
求最终的方差。

$2\le n\le 10^5,0\le a_i<2^{15}$

思路
观察两个粒子碰撞后，两个数的二进制变化：

1 0 1 0 0 1  
0 0 1 0 1 0
———————————— 两粒子相撞后
0 0 1 0 0 0
1 0 1 0 1 1
1
2
3
4
5

会发现，如果二进制中有一位两数中只有一个 1，那么肯定会聚集到第二个数中。
那么如果两个聚集过的两数相碰，将不会有任何变化。

重新构造这 n 个数，使得任意两个数碰撞不会发生变化，那么所有权值的方差就是稳定的。也就是，将每一位上，所有的 1 都拿出来，重新分配，尽量分给前面的数。
这样，任意拿出两个数，后面数的某一位有1，前面数也一定有。前面数有后面数不一定有，两数碰撞后不会有任何变化。

求方差，可以直接套方差公式，但是注意范围会爆 longlong，需要用到 __int128，其输出需要自写函数：

void print(__int128 x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x/10);
	putchar(x%10 + '0');
}
1
2
3
4
5
6

也可以用这个公式：
$设一个数组的方差为D(x),平均数为E(x)。$

$\text{ 则 }D(x)=E\left(x^2\right)-E^2(x)$

long long 范围内运算即可。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], cnt[30];

void print(__int128 x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x/10);
	putchar(x%10 + '0');
}

__int128 gcd(__int128 a, __int128 b)
{
	if(!b) return a;
	return gcd(b, a%b);
}

signed main(){
	Ios;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int x; cin >> x;
		for(int j=0;j<16;j++)
		{
			if(x & 1) cnt[j]++;
			x >>= 1;
		}
	}
	
	int sum = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<16;j++)
		{
			if(cnt[j]) a[i] |= 1<<j, cnt[j]--;
		}
		sum += a[i];
	}
	
	int x = sum, y = n, g = __gcd(sum, n);
	x /= g, y /= g;
	
	__int128 up = 0, down;
	for(int i=1;i<=n;i++)
	{
		up += (__int128)(a[i]*y - x) * (a[i]*y - x);
	}
	
	if(up == 0){
		cout << "0/1";
		return 0;
	}
	
	down = n*y*y;
	
	__int128 gg = gcd(up, down);
	print(up/gg);
	printf("/");
	print(down/gg);
	
	return 0;
}
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

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], cnt[30];

signed main(){
	Ios;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int x; cin >> x;
		for(int j=0;j<16;j++)
		{
			if(x & 1) cnt[j]++;
			x >>= 1;
		}
	}
	
	int sum1 = 0, sum2 = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<16;j++)
		{
			if(cnt[j]) a[i] |= 1<<j, cnt[j]--;
		}
		sum1 += a[i]*a[i];
		sum2 += a[i];
	}
	
	int up = n*sum1 - sum2*sum2, down = n*n;
	if(up == 0){
		cout << "0/1";
		return 0;
	}
	int g = __gcd(up, down);
	cout << up/g << "/" << down/g;
	
	return 0;
}
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