模拟赛 6（8.7）
T1 纤维续光
给定两个长度为 n 的子序列 a,b，选出一个 a 的子序列，对于选出的长度为 k 的子序列 a'，要求对于任意的 \(1\le j\le k\) 有 \(a'_{j+1}>b_ja'_j\)，求最大的长度 k。\(n\le 10^6\)。
算法一 \(n\le 1000\) 暴力
进行这样一个 DP，记 \(dp[i][j]\) 为前 i 个数，选的最后一个数是 j 的上升子序列的最长长度。
- 不选第 i 个数时 \(dp[i][j]→dp[i+1][j]\)。
- 选第 i 个数时 \(dp[i][j]+1→dp[i+1][i+1]\)，前提是 \(a_{i+1}>b_{dp[i][j]}\times a_j\)。
答案是 \(\max\{dp[n]\}\)，时空复杂度 \(O(n^2)\)。（50分）
算法二 另一种 DP，\(b_i>1\) 的部分分
记 \(dp[i][j]\) 表示前 i 个数，选出长度为 j 的上升子序列，最后一个数的最小值。
- 不选第 i 个数时 \(dp[i][j]=dp[i-1][j]\)。
- 选第 i 个数时 \(dp[i][j]=a[i]\)，前提是 \(a_{i}>b_{j-1}\times dp[i-1][j-1]\)。
我们发现当 \(b_i>1\) 时，每次都至少增长 2 倍，所以答案最高是 \(O(\log a_i)\) 的，总时间复杂度 \(O(n\log a_i)\)。（65分）
算法三 最长上升子序列，\(b_i=1\)
显然就是最长上升子序列问题，维护最终序列，每次用二分找出第一个大于插入数的位置并替换，是当前最大的就插入，最终答案为最后序列的长度，时间复杂度 \(O(n\log n)\)。（80分）
算法四 优化
注意到对于每个 \(dp[i]\)，它的值都是随 j 单调递增的，因为构造的序列越长，最优时结尾的数一定越大。
考虑 \(dp[i-1]\) 何时需要转移到 \(dp[i]\)，发现有很大一部分的转移是没有意义的：
- 当 \(dp[i-1][j]<a_i\) 时，此时如果满足条件则 \(dp[i][j]=\min(dp[i-1][j],a[i])=dp[i-1][j]\)，dp 值一定不会变化，没有意义；
- 记第一个 \(dp[i-1][j]\ge a_i\) 的位置 j 为 k，那么对于所有的 \(j>k+1\)，那么注意到条件转化后：\(a_i>dp_[i-1][j-1]\times b_{j-1}>dp[i-1][k]\times b_{j-1}\ge dp[i-1][k]\ge a_i\) 一定不成立，所以一定不能转移。
那么只有 \(dp[i-1][k]\) 需要转移，所以第一维可以不用开，扫一遍 a，对于每一个 \(a_i\) 记录 dp 数组第一个大于等于它的位置 k，然后判断位置 k 是否可以转移并转移即可，每次需要二分，时间复杂度 \(O(n\log n)\)。(100分）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n;
int a[N],b[N];
int dp[N];
signed main(){freopen("filament.in","r",stdin);freopen("filament.out","w",stdout);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++)dp[i]=1e18;dp[0]=0;int len=0;for(int i=1;i<=n;i++){int k=lower_bound(dp+1,dp+len+1,a[i])-dp;if(k==len+1){if(len==0||a[i]>dp[len]*b[len])dp[++len]=a[i];continue;}if(k==1||a[i]>b[k-1]*dp[k-1])dp[k]=min(dp[k],a[i]);}cout<<len<<"\n";return 0;
}
T3 双环刻时
定义 \(\phi(x,y)=((x-1)d+y-1)\mod w+1\)
给定 m,d,w,a,b，求有多少对 \(1\le x,y\le\min(m,d)\) 满足 \(\phi(x,y)=a,\phi(y,x)=b\)。
\(m,d,w\le 10^9,a,b\in[1,w]\)，w 是质数。
子任务 1 \(m,d\le 1000\)（30分）
子任务 2 \(w\le 10^5\)（30分）
子任务 3：数据随机生成（20分）
算法一：直接暴力枚举所有 \((x,y)\)，时间复杂度 \(O(\min(m,d)^2)\)。（30分）
算法二：题面中从 1 开始不好看，下文中 a,b 为实际的 \(a-1,b-1\)。
依据题意，一个 \((x,y)\) 合法需要满足
其中 \(x,y\in[0,\min(m,d)-1]\)。
一种暴力的方式就是枚举 x，然后解关于 y 的同余方程并记录解的数量，但是复杂度 \(O(w\log w)\)，可以通过 \(w\le 10^5\) 的特殊性质。
算法三：考虑对这个方程组消元，对 ① 式移项得 \(y\equiv a-dx\)，代入 ② 式得 \(d(a-dx)+x\equiv b\)，即
若 \(d^2-1\ne 0\) 时，可以求出它的逆元 inv，求出 \(x=(da-b)\times inv(d^2-1) \mod w\)，这就可以求出方程的一组特解 \(x_0\)。因为 \(x\equiv x_0\)，我们就可以计算出 x 的个数。
同样，我们可以看出 y 的个数，最终答案就是 \(cnt_x\times cnt_y\)。
这里假设了 \(d^2\equiv 1\pmod w\)，随机数据是可以避免这种情况的。（50分）
算法四
设 \(n=\min(m,d)-1\)。
考虑 \(d^2\equiv 1\pmod w\) 时，有以下两种情况
-
\(d\equiv-1\pmod w\)
代入到最原始的方程组，得
\[y-x\equiv a\pmod w\\ x-y\equiv b\pmod w \]显然 \(a\equiv-b\pmod p\)，如果不成立一定没有解。
如果有解，设 \(u=y-x\)，问题就转化为求 \(u\equiv a\pmod w\) 的 \(0\le x,y\le n\) 的个数，依据这个范围，可得 u 的取值范围 \(-n\le u\le n\)。
考虑函数 \(y=x+u\)，那么函数必须在 \(0\le x,y\le n\) 的正方形中，所以 x 的取整范围为
\[\max(0,-u)\le x\le \min(n,n-u) \]可以画图理解一下。
区间长度为 \(\min(n,n-u)-\max(0,-u)+1=n+1-|u|\)。
因此合法的总个数为
\[\sum_{-n\le u\le n,u\equiv a\pmod w}(n+1-|u|) \]求法稍后介绍。
-
\(d\equiv1\pmod w\)
做法类似，此时代入原方程组得
\[x+y\equiv a\pmod w\\ x+y\equiv b\pmod w \]显然 \(a\equiv b\pmod p\)，如果不成立一定没有解。
设 \(s=x+y\)，我们要求 \(s\equiv a\pmod w\) 的数量。
这次，函数 \(y=s-x\) 必须在 \(0\le x,y\le n\) 的正方形中，所以 x 的取整范围为
\[\max(0,s-n)\le x\le \min(n,s) \]区间长度为 \(\min(s,2n-s)+1\)。
总答案
\[\sum_{0\le s\le 2n,s\equiv a\pmod w}(\min(s,2n-s)+1) \]
现在，我们要快速求