杭电多校-Shinobu loves trip-(预处理+同余定理)

Shinobu loves trip

题意：
就是有p个城市，编号0~p-1。然后有n个旅行计划，每个旅行计划有个初始点，和旅行的天数。然后小A旅行的的点顺序是，每次乘以a，当然同时对p取模。然后有m次查询，每次问你有几个旅行计划可以到达城市x。

思考：
1.观察到查询次数和旅行计划很少，应该是查询的时候，枚举每个旅行计划看看是否可以。对于一个计划可以走到的点就是s×a^k %p。所以这这个式子 = x就行。所以就是s×a^k %p = x%p。根据同余定理，可以把s移到右边。得到a^k %p= x*s^-1 %p。右边除以的时候乘以逆元就行。右边算出来后，看看是否有a^k %p = 这个值的。如果有看看k最小是多少，然后这个k是否小于旅行计划的时间。
2.a^k 预处理出来，每个旅行计划的起点也要预处理，因为每次求n个数的逆元的话复杂度也很高。还要注意特判的就是如果某个计划的起点是0的话，看看x是不是0。如果不特判的话，这样的情况就不会计入答案了。还有值得注意的就是用map查询某个数是否存在的时候最好用count函数，不用!mp[t]，mp可以是0的话，这样就不算出现了。
3.当时也写出来了s×a^k %p = x%p，这个式子，但是一想每次都跑一遍的话复杂度太高了。然后去想每次乘完以后%p，这样会不会回到之前出现过的点，这样就会产生环？不用算那么多之类的。其实根本不用想那么多，就是一直乘a，看看能到达的城市是多少就行了。然后乘法和取模也是互不影响的，该多少还是多少。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
PII va[N];
int pre[N];
int cnt[N];
int p,a;

unordered_map<int,int > mp;

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%p;
		a = a*a%p;
		b >>= 1;
	}
	return sum;
}

void init()
{
	mp.clear();
	pre[0] = 1;mp[1] = 0;
	for(int i=1;i<=2e5+5;i++)
	{
		pre[i] = pre[i-1]*a%p;
		if(!mp.count(pre[i])) mp[pre[i]] = i;
		else mp[pre[i]] = min(mp[pre[i]],i);
	}
	for(int i=1;i<=n;i++) cnt[i] = ksm(va[i].fi,p-2)%p;
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>p>>a>>n>>m;
		for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
		init();
		while(m--)
		{
			int x;
			cin>>x;
			int sum = 0;
			for(int i=1;i<=n;i++)
			{
				if(va[i].fi==0)
				{
					if(x==0) sum++;
					continue;
				}
				int ned = x*cnt[i]%p;
				if(mp.count(ned)&&mp[ned]<=va[i].se) sum++;
			}
			cout<<sum<<"\n";
		}
	}
	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

总结：
多多思考，不要想的太复杂，用简洁的眼光去看待。