题解：P16019 [ICPC 2021 NAC] Permutation CFG
lailai0916
·
·
题解
题意简述
给定 1\sim n 的排列。符号 x 会按排列顺序展开为所有不超过 x 的符号。从 n 开始展开 s 次，询问结果序列某个前缀内符号 k 的出现次数。
解题思路
记 F_t(x) 为从符号 x 出发，展开 t 次得到的序列。规则右侧包含 1\sim x 各一次，因此完整序列的长度与排列顺序无关：
|F_t(x)|=\binom{x+t-1}{t}
当 t\ge1 且 k\le x 时，符号 k 在完整序列中的出现次数为：
c_t(x,k)=\binom{x-k+t-1}{t-1}
两个式子都可由展开规则做一次前缀求和得到。
用可持久化线段树完成块定位。第 $x$ 个版本包含值 $1\sim x$，下标是这些值在排列中的位置。节点对每个 $0\le t\le4$ 维护 $|F_t(y)|$ 之和。按该权值在线段树上二分，即可找到前缀末尾所在的排列位置。
块长度只用于和查询前缀比较。查询中的 $a\le10^9$，所以更大的长度可以统一截断。代码截到 $4\times10^{18}$，并用 `__int128` 完成乘法。
还需统计末尾位置之前的完整块贡献。版本 $x$ 减去版本 $k-1$ 后，恰好保留 $k\le y\le x$ 的值。对固定的 $t$，$c_t(y,k)$ 是关于 $y$ 的至多三次多项式。节点再维护 $y^0,y^1,y^2,y^3$ 之和，便可还原贡献。代码用 `__int128` 保存这些矩，避免中间量溢出。
预处理复杂度为 $O(n\log n)$。每个询问的复杂度为 $O(s\log n)$，空间复杂度为 $O(n\log n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128;
const int N=100005;
const int M=N*19;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct node
{
int l,r;
ll sum[5];
i128 pw[4];
}tr[M];
int n,tot;
int rt[N],a[N],pos[N];
int update(int pre,int l,int r,int x,int val)
{
int u=++tot;
tr[u]=tr[pre];
if(l==r)
{
tr[u].sum[0]=1;
for(int i=1;i<=4;i++)tr[u].sum[i]=min((i128)inf,(i128)tr[u].sum[i-1]*(val+i-1)/i);
tr[u].pw[0]=1;
for(int i=1;i<=3;i++)tr[u].pw[i]=tr[u].pw[i-1]*val;
return u;
}
int mid=(l+r)>>1;
if(x<=mid)tr[u].l=update(tr[pre].l,l,mid,x,val);
else tr[u].r=update(tr[pre].r,mid+1,r,x,val);
for(int i=0;i<=4;i++)tr[u].sum[i]=min(inf,tr[tr[u].l].sum[i]+tr[tr[u].r].sum[i]);
for(int i=0;i<=3;i++)tr[u].pw[i]=tr[tr[u].l].pw[i]+tr[tr[u].r].pw[i];
return u;
}
int kth(int u,int l,int r,int d,ll &k)
{
if(l==r)return l;
int mid=(l+r)>>1;
if(k<=tr[tr[u].l].sum[d])return kth(tr[u].l,l,mid,d,k);
k-=tr[tr[u].l].sum[d];
return kth(tr[u].r,mid+1,r,d,k);
}
void query(int u,int v,int l,int r,int x,i128 res[4])
{
if(x<l)return;
if(r<=x)
{
for(int i=0;i<=3;i++)res[i]+=tr[u].pw[i]-tr[v].pw[i];
return;
}
int mid=(l+r)>>1;
query(tr[u].l,tr[v].l,l,mid,x,res);
if(x>mid)query(tr[u].r,tr[v].r,mid+1,r,x,res);
}
ll count_full(int d,int x,int k,int p)
{
if(d==0)return pos[k]<p;
i128 v[4]={};
query(rt[x],rt[k-1],1,n,p-1,v);
if(d==1)return v[0];
i128 z1=v[1]-(i128)k*v[0];
if(d==2)return z1+v[0];
i128 z2=v[2]-(i128)2*k*v[1]+(i128)k*k*v[0];
if(d==3)return (z2+3*z1+2*v[0])/2;
i128 z3=v[3]-(i128)3*k*v[2]+(i128)3*k*k*v[1]-(i128)k*k*k*v[0];
return (z3+6*z2+11*z1+6*v[0])/6;
}
ll solve(int d,int x,int k,ll len)
{
if(k>x)return 0;
if(d==0)return x==k;
int p=kth(rt[x],1,n,d-1,len);
return count_full(d-1,x,k,p)+solve(d-1,a[p],k,len);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s,q;
cin>>n>>s>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[a[i]]=i;
}
for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,n,pos[i],i);
while(q--)
{
int k;
ll len;
cin>>k>>len;
cout<<solve(s,n,k,len)<<'\n';
}
return 0;
}
```