• [推公式]Shinobu loves trip 2022杭电多校第6场 1007


    Problem Description

    As a cold-blooded, hot-blooded, and iron-blooded vampire, Shinobu loves traveling around.

    There are PP countries in total, numbered 0,1,\dots ,P-10,1,…,P−1.(It is guaranteed that PP is a prime number)

    It is known that when Shinobu is in the country numbered ii, the next country she visits must be the country numbered (i\cdot a) \mod P(i⋅a)modP (aa is a constant parameter), and it takes Shinobu 11 day to go from one country to another.

    In order to travel smoothly, Shinobu has customized nn travel plans, and the ii-th travel plan is represented by the starting country s_isi​ and the travel days d_idi​.

    For example, if P = 233,\ a = 2P=233, a=2, a plan's starting country is 11 and travel days is 22, then Shinobu will visit the city { 1,2,4 }1,2,4 according to this plan.

    Playf knows these travel plans and the value of parameter aa, now he wants to ask you qq questions. The ii-th question asks how many travel plans will make shinobu visit the country x_ixi​.

    Input

    The first line of the input contains one integer TT ((1\leq T\leq 51≤T≤5 )) --- the number of test cases. Then TT test cases follow.

    For each testcase, the first line contains four integers P,\ a,\ n,\ q(2\le a< P \le 1000000007, 1\le n \le 1000, 1\le q \le 1000 )P, a, n, q(2≤a

    Each of the next nn lines contains two integers s_i,\ d_i(0\le s_i< P, 1\le d_i \le 200000 )si​, di​(0≤si​

    Each of the next qq lines contains one integer x_i(0\le x_i< P)xi​(0≤xi​

    It is guaranteed that PP is a prime number.

    Output

    For each testcase, print qq lines, the ii-th line contains one integer --- the answer to the ii-th question.

    Sample Input

    3 2 1 1

    1 1

    2

    5 4 3 2

    1 4

    4 3

    2 100000

    4

    2

    Sample Output

    1

    2

    1

    题意: 每组数据给出P,a,n,q,接着给出n条旅游计划,每个旅游计划包含起点si以及持续时间di,然后是q次询问,每次询问给出目标地点xi,对于每次询问输出有多少路线经过目标地点xi,已知每天会从当前地点i移动至地点i*a%P,P是质数。

    分析: 对于每个目标地点都遍历一遍所有计划,然后根据题意写出下面这个方程,s*a^y 同余 xi(Mod P) ,实际上这个计划能否经过xi等价于上式中最小解y是否小于等于d,对公式进行变形,两侧同时乘s逆元,就变成了a^y 同余 s^-1*xi(Mop P),可以维护出来a^y在y∈[1, 200000]范围内所有的值,并存放在一个map中,这样就可以通过该值查找到最小的y了,之后在遍历的时候只需要看一下map[s^-1*xi]是否存在,如果存在再看下值是否小于等于d,满足的话就说明这个计划会经过xi。最后需要注意求s逆元的过程不能放在q*n的二层循环中,虽然只是多一个log,但hduoj跑的比较慢,这样是会TLE的,正确做法应该是把各个s的逆元提前预处理出来。

    具体代码如下:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define int long long
    9. #define pii pair
    10. using namespace std;
    11. //s*a^x == t(Mod P)
    12. //a^x == s^-1*t(Mod P)是否存在x <= d的解
    13. int P, a, n, q;
    14. int A[200005];
    15. pii p[1005];
    16. int inv[1005];
    17. unordered_map<int, int> mp;
    18. int ksm(int base, int power){
    19. int ans = 1;
    20. while(power){
    21. if(power&1) ans = ans*base%P;
    22. base = base*base%P;
    23. power >>= 1;
    24. }
    25. return ans;
    26. }
    27. signed main()
    28. {
    29. A[0] = 1;
    30. int T;
    31. cin >> T;
    32. while(T--){
    33. mp.clear();
    34. scanf("%lld%lld%lld%lld", &P, &a, &n, &q);
    35. for(int i = 1; i <= 200000; i++){
    36. A[i] = (A[i-1]*a)%P;
    37. if(mp.count(A[i])) continue;
    38. mp[A[i]] = i;
    39. }
    40. mp[1] = 0;
    41. for(int i = 1; i <= n; i++){
    42. scanf("%lld%lld", &p[i].first, &p[i].second);
    43. inv[i] = ksm(p[i].first, P-2);
    44. }
    45. for(int i = 1; i <= q; i++){
    46. int ans = 0;
    47. int t;
    48. scanf("%lld", &t);
    49. for(int j = 1; j <= n; j++){
    50. if(p[j].first == 0 && t == 0){
    51. ans++;
    52. continue;
    53. }
    54. if(!mp.count(inv[j]*t%P)) continue;
    55. if(mp[inv[j]*t%P] <= p[j].second) ans++;
    56. }
    57. printf("%lld\n", ans);
    58. }
    59. }
    60. return 0;
    61. }

  • 相关阅读:
    国产高云FPGA开发软件Gowin的下载、安装、Licence共享,按照我的方案保证立马能用,不能用你铲我耳屎
    解决 viteprees 中 vp-doc 内置样式影响组件预
    C#匿名方法介绍
    【PAT(甲级)】1048 Find Coins(测试点2,3,4)
    cdh大数据平台中es安装、logstash安装、nginx安装、RTMP和FTP
    【附源码】计算机毕业设计JAVA大数据文章发布系统
    solr 查询以特殊符号拼接Id成的字段
    很强!4.7k star,推荐一款Python工具,可实现自动化操作!!
    适用于 Linux 的 WPF:Avalonia
    小程序环境切换自定义组件
  • 原文地址:https://blog.csdn.net/m0_55982600/article/details/126172507