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<bits/stdc++.h>
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;
}

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

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

---

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<bits/stdc++.h>
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;
}

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

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

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

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

#include<bits/stdc++.h>
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;
}

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