当前位置：首页 > news >正文

UVa 12384 Span

news 2026/6/13 10:27:31

题目描述

给定一个包含nnn个整数的数组X1≤i≤nX_{1 \leq i \leq n}X1≤i≤n，定义数组XXX的spanSSS为一个长度为nnn的整数数组，其中SiS_iSi表示在XiX_iXi之前（包括XiX_iXi自身）连续满足所有元素都≤Xi\leq X_i≤Xi的最大元素个数。数学表示如下：

Si=∣Ai∣,Ai={j≤i∣∀k(j≤k≤i) (Xk≤Xi)}. S_i = |A_i|, \quad A_i = \{j \leq i \mid \forall k (j \leq k \leq i) \ (X_k \leq X_i)\}.Si=∣Ai∣,Ai={j≤i∣∀k(j≤k≤i)(Xk≤Xi)}.

例如，X=[40,2,10,50,30,15]X = [40,2,10,50,30,15]X=[40,2,10,50,30,15]的span为S=[1,1,2,4,1,1]S = [1,1,2,4,1,1]S=[1,1,2,4,1,1]。

本题的特殊设定是：Xi=Pi mod mX_i = P_i \bmod mXi=Pimodm，其中PiP_iPi是第iii个素数。我们需要计算SSS的所有元素之和模mmm的结果。

输入格式

第一行一个整数TTT，表示测试用例个数。
接下来TTT行，每行两个整数n,mn, mn,m，满足1≤n,m≤1051 \leq n, m \leq 10^51≤n,m≤105。

输出格式

对于每个测试用例，输出一行一个整数：(∑i=1nSi) mod m\left(\sum_{i=1}^n S_i\right) \bmod m(∑i=1nSi)modm。

样例输入

3 7 10 10 16 10 7

（实际格式应为每行两个数，这里只是紧凑写法）

样例输出

0 5 6

题目分析

1. 直接计算的复杂度

若直接按照定义计算SiS_iSi，需要向前扫描直到遇到一个大于XiX_iXi的数，时间复杂度O(n2)O(n^2)O(n2)，当nnn达到10510^5105时不可接受。

2. 素数的获取

我们需要前nnn个素数。第10510^5105个素数大约是1.3×1061.3 \times 10^61.3×106，因此可以预先用埃氏筛（Sieve of Eratosthenes\texttt{Sieve of Eratosthenes}Sieve of Eratosthenes）生成2×1062 \times 10^62×106以内的所有素数，并存储到全局数组中。由于TTT最多可能为10510^5105，必须只预处理一次。

3.`Span`的计算优化

观察SiS_iSi的含义：它等于从iii向左数，直到遇到第一个大于XiX_iXi的元素为止，这中间的元素个数（包括XiX_iXi自己）。这是一个经典的左边第一个更大元素问题，可以用单调栈在O(n)O(n)O(n)时间内解决。

具体方法：

维护一个单调递减栈（栈内元素的值从栈底到栈顶严格递减）。
遍历i=0…n−1i = 0 \dots n-1i=0…n−1：
- 当栈非空且栈顶元素的值≤Xi\leq X_i≤Xi时，弹出栈顶（因为这些元素无法成为比XiX_iXi大的左边界）。
- 如果栈为空，说明左边所有元素都≤Xi\leq X_i≤Xi，则Si=i+1S_i = i + 1Si=i+1。
- 否则，栈顶元素的下标jjj是左边第一个大于XiX_iXi的元素，则Si=i−jS_i = i - jSi=i−j。
- 将iii入栈。

这个过程保证了每个元素最多入栈和出栈一次，因此总复杂度O(n)O(n)O(n)。

4. 模运算的注意点

最终需要输出totalSum mod mtotalSum \bmod mtotalSummodm。注意totalSumtotalSumtotalSum可能很大（最大约n2n^2n2级别），应使用646464位整数（如long long\texttt{long long}long long）累加，避免溢出。

解题思路

整体流程

预处理素数
使用埃氏筛，生成2×1062 \times 10^62×106以内的所有素数，存入全局数组primes\texttt{primes}primes。
对每个测试用例
- 读取n,mn, mn,m。
- 取前nnn个素数对mmm取模，得到数组XXX。
- 使用单调栈计算SiS_iSi并累加求和。
- 输出sum mod msum \bmod msummodm。

为什么素数范围取2×1062 \times 10^62×106

第10510^5105个素数约为129970912997091299709，因此2×1062 \times 10^62×106足够生成前10510^5105个素数，且不会造成过多的时间开销。

时间复杂度

筛法：O(Llog⁡log⁡L)O(L \log \log L)O(LloglogL)，其中L=2×106L = 2 \times 10^6L=2×106。
每个测试用例：O(n)O(n)O(n)。
总复杂度：O(Llog⁡log⁡L+∑n)O(L \log \log L + \sum n)O(LloglogL+∑n)，在10510^5105级别内可接受。

空间复杂度

素数列表：约10510^5105个整数。
每个测试用例临时数组XXX和SSS：O(n)O(n)O(n)。

实现细节

使用vector<bool>\texttt{vector<bool>}vector<bool>进行布尔标记以节省内存。
使用stack<int>\texttt{stack<int>}stack<int>存储下标，维护单调性。
输入输出使用scanf\texttt{scanf}scanf/printf\texttt{printf}printf提高效率。
累加和用long long\texttt{long long}long long类型。

代码实现

// Span// UVa ID: 12384// Verdict: Accepted// Submission Date: 2026-05-25// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 全局素数列表vector<int>primes;// 埃氏筛，生成所有不超过 limit 的素数voidsieve(intlimit){vector<bool>isPrime(limit+1,true);isPrime[0]=isPrime[1]=false;for(inti=2;i<=limit;++i){if(isPrime[i]){primes.push_back(i);if((longlong)i*i<=limit){for(intj=i*i;j<=limit;j+=i)isPrime[j]=false;}}}}intmain(){// 预先生成足够多的素数（第 100000 个素数约 1299709，取 2e6 安全）constintMAX_PRIME_LIMIT=2000000;sieve(MAX_PRIME_LIMIT);intT;scanf("%d",&T);while(T--){intn,m;scanf("%d %d",&n,&m);// 步骤1：生成 X 数组vector<int>X(n);for(inti=0;i<n;++i)X[i]=primes[i]%m;// 步骤2：单调栈计算 spanvector<int>S(n);stack<int>st;// 存下标，维护 X[st] 递减longlongtotalSum=0;for(inti=0;i<n;++i){while(!st.empty()&&X[st.top()]<=X[i])st.pop();if(st.empty())S[i]=i+1;elseS[i]=i-st.top();st.push(i);totalSum+=S[i];}// 输出 sum % mprintf("%lld\n",totalSum%m);}return0;}