A
类 Hanoi 问题，三个塔，移动顺序必须为 \(1\rightarrow 2\rightarrow 3\rightarrow 1\).
初始有 \(n\) 的圆盘到柱子 \(1\)，问将它们全部操作到 \(2,3\) 上分别需要的步数 \(a,b\).
答案模 \(998244353\)，多测。分别输出所有 \(a\) 和 \(b\) 的异或和即可（模 \(998244353\) 后异或）。
\(T\le 1.2\times 10^6\)，\(n\le 10^{12}\)，TL=1s.
不会推，直接猜结论。
\(n=1,2,3\) 时的答案为 \((1,2),(5,7),(15,21)\).
一开始以为 \(a\) 到 \(b\) 的差值为 \(\operatorname{fac}(n)\)，然后一推发现完全不可做。
然后知道了 \(n=4\) 的答案是 \((43,59)\)，所以换一种。
容易发现有
直接捏矩阵即可，考虑
构造 \(A=\begin{bmatrix}0&1&0\\2&2&0\\1&2&1\end{bmatrix}\) 即可。
复杂度 \(O(27\cdot T\log n)\).
写几个优化。
-
离线做。
-
对于 \(i\in[0,40]\)，预处理 \(A^{2^i}\)，快速幂时 \(O(k^3)\rightarrow O(k^2)\).
-
循环展开，取模优化。在 GJOJ 上使用指令集。
另外地，考虑优化矩乘的渐进复杂度，这意味着常数是可以去掉的。考虑构造
贴 \(k=3\) 的代码。
点击查看代码
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define N 1200010
#define P 998244353
using namespace std;
ll read(){
ll 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 add(int x,int y){
x+=y;
return x>=P?x-P:x;
}
int md(ll x){
return x>=P?x%P:x;
}
struct Mat{
int a[3][3];
Mat(){
a[0][0]=a[0][1]=a[0][2]=0;
a[1][0]=a[1][1]=a[1][2]=0;
a[2][0]=a[2][1]=a[2][2]=0;
}
Mat operator*(const Mat &b)const{
Mat c;
c.a[0][0]=add(add(md(1ll*a[0][0]*b.a[0][0]),md(1ll*a[0][1]*b.a[1][0])),md(1ll*a[0][2]*b.a[2][0]));
c.a[0][1]=add(add(md(1ll*a[0][0]*b.a[0][1]),md(1ll*a[0][1]*b.a[1][1])),md(1ll*a[0][2]*b.a[2][1]));
c.a[0][2]=add(add(md(1ll*a[0][0]*b.a[0][2]),md(1ll*a[0][1]*b.a[1][2])),md(1ll*a[0][2]*b.a[2][2]));
c.a[1][0]=add(add(md(1ll*a[1][0]*b.a[0][0]),md(1ll*a[1][1]*b.a[1][0])),md(1ll*a[1][2]*b.a[2][0]));
c.a[1][1]=add(add(md(1ll*a[1][0]*b.a[0][1]),md(1ll*a[1][1]*b.a[1][1])),md(1ll*a[1][2]*b.a[2][1]));
c.a[1][2]=add(add(md(1ll*a[1][0]*b.a[0][2]),md(1ll*a[1][1]*b.a[1][2])),md(1ll*a[1][2]*b.a[2][2]));
c.a[2][0]=add(add(md(1ll*a[2][0]*b.a[0][0]),md(1ll*a[2][1]*b.a[1][0])),md(1ll*a[2][2]*b.a[2][0]));
c.a[2][1]=add(add(md(1ll*a[2][0]*b.a[0][1]),md(1ll*a[2][1]*b.a[1][1])),md(1ll*a[2][2]*b.a[2][1]));
c.a[2][2]=add(add(md(1ll*a[2][0]*b.a[0][2]),md(1ll*a[2][1]*b.a[1][2])),md(1ll*a[2][2]*b.a[2][2]));
return c;
}
}init,base,now,bs[50];
int m;ll q[N];
void qpow(ll b){
int cnt=0;
while(b){
if(b&1)now=now*bs[cnt];
cnt++,b>>=1;
}
}
int ansa,ansb;
int main(){
init.a[0][0]=init.a[0][2]=1,init.a[0][1]=2;
base.a[2][0]=base.a[0][1]=base.a[2][2]=1,base.a[1][0]=base.a[1][1]=base.a[2][1]=2;
bs[0]=base;
for(int i=1;i<50;i++)bs[i]=bs[i-1]*bs[i-1];
m=read();
for(int i=1;i<=m;i++)q[i]=read();
sort(q+1,q+1+m),q[0]=1;
now=init;
for(int i=1;i<=m;i++){
qpow(q[i]-q[i-1]);
ansa^=now.a[0][0],ansb^=now.a[0][1];
}
printf("%d %d\n",ansa,ansb);
return 0;
}
B
给出长为 \(n\) 的序列 \(a_0,a_1,\dots,a_{n-1}\).
\(m\) 次询问，每次给出 \(k\)，问将 \(a\) 重排后，\(\sum\limits_{i=0}^{n-1}a_i\cdot a_{(i+k)\bmod n}\) 的最大值。
\(2\le n\le 5000\)，\(1\le m\le n\)，\(0\le k<n\)，\(1\le a_i\le 10^5\).
一眼贪，考虑从大到小添，如果找到左侧或右侧距离为 \(k\) 没有数的最大的 \(x\)，把这个数放在 \(x\) 的左边或右边。
一共有 \(\gcd(n,k)\) 个循环，每次填完一个循环就从新的位置开始填。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 5010
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,a[N];
int pos[N],gcd,now,res[N];
int gl(int x,int k){
return (x-k+n)%n;
}
int gr(int x,int k){
return (x+k)%n;
}
void solve(){
int k=read();
if(!k){
ll ans=0;
for(int i=0;i<n;i++)ans+=1ll*a[i]*a[i];
printf("%lld\n",ans);
return;
}
if(k*2==n){
ll ans=0;
for(int i=0;i<n/2;i++)
ans+=2ll*a[i*2]*a[i*2+1];
printf("%lld\n",ans);
return;
}
memset(pos,-1,sizeof(pos)),memset(res,-1,sizeof(res));
gcd=__gcd(k,n),now=n-1;
for(int i=0,tp;i<gcd;i++){
pos[now]=i,res[i]=now;
tp=gl(pos[now],k),pos[now-1]=tp,res[tp]=now-1;
now-=2;
for(int j=3;j<=n/gcd;j++){
tp=gl(pos[now+2],k);
if(~res[tp])tp=gr(pos[now+2],k);
pos[now]=tp,res[tp]=now--;
}
}
ll ans=0;
for(int i=0;i<n;i++)
ans+=1ll*a[res[i]]*a[res[gr(i,k)]];
printf("%lld\n",ans);
}
int main(){
n=read();
for(int i=0;i<n;i++)a[i]=read();
sort(a,a+n);
int T=read();
while(T--)solve();
return 0;
}
C
已知 \(i\in[1,n]\)，\(a_i\) 是 \([l_i,r_i]\) 间的一个实数。
对于每个 \(i\) 求 \(a_i\) 的期望排名，排名具体指 \(a_j\ge a_i\) 的 \(j\) 的个数，\(j\in[1,n]\).
\(n\le 10^5\)，\(1\le l_i<r_i\le 10^5\).