最唐的一集。
A
已知质数 \(P=10^{18}+31\) 的一个原根为 \(g=42\)，给出 \(A\) 数组满足 \(\displaystyle A_i=\begin{cases}795484359100928850&i=0\\\log_g A_{i-1}\bmod P&i>0\end{cases}\)，多次询问 \(A_x\) 的值。
\(1\le T\le 10\)，\(0\le x\le 10^5\)。
input：
4
0
1
30030
100000
output：
795484359100928850
552539349852014697
791247515610184509
960002411612632915
怎么 \(A_{100000}\) 给出来了？
我们用快速幂倒推即可。
注意 1e18+31 会把后面的 \(31\) 丢掉。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
const ll P=1000000000000000031,g=42;
ll mul(ll x,ll y){
return ((__int128)x)*y%P;
}
ll qpow(ll k,ll b){
ll ret=1;
while(b){
if(b&1)ret=mul(ret,k);
k=mul(k,k),b>>=1;
}
return ret;
}
ll a[N];
int main(){
a[100000]=960002411612632915;
for(int i=99999;~i;i--)a[i]=qpow(g,a[i+1]);
int T=read();
while(T--)printf("%lld\n",a[read()]);
return 0;
}
B
给定长为 \(n\) 的串 \(s\) 和长为 \(m\) 的串 \(t\)，问有多少四元组 \((l,r,i,j)\) 满足：
-
\(1\le l\le i\le j\le r\le n\)。
-
\(s[l:r]\) 为回文串且 \(r-l+1\) 为奇数。
-
\(s[i:j]=t\)。
答案对 \(2^{32}\) 取模。
用 kmp 容易求出所有 \((i,j)\)。
判定回文可以 manacher，但是不会。所以枚举中心点，直接二分哈希。
现在需要判定 \(l\le i\) 且 \(j\le r\)，其中 \((l,r)\) 的级别是 \(O(n^2)\) 的。
唐了。等会在想。
C
构造一张简单连通无向图满足恰好有 \(C\) 个无序点对 \((x,y)\) 满足存在 \(x\) 到 \(y\) 的哈密顿路。多测。
需要满足 \(1\le n\le 20\)，\(1\le m\le \frac{n(n-1)}{2}\)。
\(1\le T,C\le 60\)。
很妙啊！
- \(C=1\)
直接构造 \(1 \Longleftrightarrow 2\)。
- \(C=2\)
这个比较特殊，但是构造一个三角形挂上一个点即可。
- \(C\le 20\)
此时构造一个环。
- \(C=\dfrac{k(k+1)}{2},k\in \mathbb{N}\)
此时构造一个完全图。
- \(C\le 60\)
考虑把一个环挂到完全图的两点上。把团与环的交点算作团的部分。记团的大小为 \(n\)，环的大小为 \(m\)（减去了 \(2\)，且 \(m\ge 2\)）。考虑新图上计入贡献的点对。
-
环内：显然相邻点对都合法，除了在团和环的交点，贡献为 \(m+1\)。
-
团内：显然任意两点都合法，除了在团和环的交点，贡献为 \(\dfrac{n(n-1)}{2}-1\)。
-
环和团：此处我们记交点为 \(a,b\)，环上与 \(a\) 相邻的点为 \(c\)，与 \(b\) 相邻的为 \(d\)。显然 \(c\) 能到达除了 \(b\) 之外的节点，\(d\) 能到达除了 \(a\) 之外的节点，贡献为 \(2n-2\)，还要减去 \(a\rightarrow c\) 和 \(b\rightarrow d\) 的贡献，所以是 \(2n-4\)。
综上应满足 \(C=m+2n+\dfrac{n(n-1)}{2}-4\)。寻找合法的 \(n,m\) 即可。
实测 \(n\) 最大为 \(19\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 25
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,C;
void solve(){
C=read();
if(C==1){
printf("2 1\n1 2\n");
return;
}
if(C==2){
printf("4 4\n");
printf("1 2\n2 3\n3 4\n2 4\n");
return;
}
if(C<=20){
printf("%d %d\n",C,C);
for(int i=1;i<=C;i++)
printf("%d %d\n",i,i%C+1);
return;
}
int sub3=0;
for(int k=1;k<=C;k++)
if(k*(k+1)/2==C){sub3=k;break;}
if(sub3){
sub3++;
printf("%d %d\n",sub3,C);
for(int i=1;i<sub3;i++)
for(int j=i+1;j<=sub3;j++)
printf("%d %d\n",i,j);
return;
}
int cnt=2,cyc;
while(C+4-2*cnt-cnt*(cnt-1)/2>=2)cnt++;
cnt--,cyc=C+4-2*cnt-cnt*(cnt-1)/2;
printf("%d %d\n",cnt+cyc,cnt*(cnt-1)/2+cyc+1);
for(int i=1;i<cnt;i++)
for(int j=i+1;j<=cnt;j++)
printf("%d %d\n",i,j);
printf("%d %d\n",cnt-1,cnt+1);
for(int i=cnt+2;i<=cnt+cyc;i++)printf("%d %d\n",i-1,i);
printf("%d %d\n",cnt,cnt+cyc);
}
int main(){
int T=read();
while(T--)solve();
return 0;
}
D
给定 \(\{a_n\}\)，生成二维数组 \(b\)：
多次询问以 \((l_1,l_2)\) 为左上角，\((r_1,r_2)\) 为右下角的子矩形的最大值。
\(n,q\le 2\times 10^5\)。