xiaoyaowudi's blogGDKOI2023 D1T2 错排 & LNOI2022 T3 盒
GDKOI2023 D1T2 错排
给定 $T$ 组正整数 $n,m$，分别求有多少个 $1\sim n$ 的排列 $p$ 使得 $\forall 1\le i\le m,p_i\gt m$ 且 $\forall m\lt i\le n,p_i\neq i$，答案对 $998244353$ 取模。
$T,n,m\le 2\times 10^5$
题解
直接写出答案:
$$ \begin{aligned} &\sum_{i}\binom{n-m}{i}\left(-1\right)^i\left(n-m-i\right)^{\underline{m}}\left(n-m-i\right)!\\ =&\left(n-m\right)^{\underline{m}}\sum_{i}\binom{n-2m}{i}\left(-1\right)^i\left(n-m-i\right)! \end{aligned} $$
令 $f\left(A,B\right)=\sum_{i}\binom{A}{i}\left(-1\right)^i\left(B-i\right)!$，则:
$$ \begin{aligned} f\left(A,B\right)=&\sum_{i}\binom{A}{i}\left(-1\right)^i\left(B-i\right)!\\ =&\sum_{i}\left(\binom{A-1}{i}+\binom{A-1}{i-1}\right)\left(-1\right)^i\left(B-i\right)!\\ =&f\left(A-1,B\right)-f\left(A-1,B-1\right)\\ f\left(A,B\right)=&\sum_{i}\binom{A}{i}\left(-1\right)^i\left(B-i\right)!\\ =&\sum_{i}\binom{A}{i}\left(-1\right)^i\left(B-i-1\right)!\left(B-i\right)\\ =&Bf\left(A,B-1\right)+Af\left(A-1,B-2\right) \end{aligned} $$
同时维护 $f\left(A,B\right)$ 和 $f\left(A+1,B+1\right)$ 即可从 $\left(A,B\right)$ 转移到 $\left(A+1,B+1\right)$，$\left(A,B+1\right)$，逆操作同理。离线下来跑莫队即可。
Code
#include <iostream>
#include <algorithm>
#include <tuple>
#include <cmath>
constexpr int p(998244353),N(2e5+10);
int W(int k){return k>=p?k-p:k;}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;static int ans[N],bs[N],pr[N],ifac[N],fac[N],inv[N];
static std::tuple<int,int,int> qs[N];int c(0);
inv[1]=1;for(int i(2);i<N;++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
ifac[0]=fac[0]=1;for(int i(1);i<N;++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
pr[0]=1;for(int i(1);i<N;++i) pr[i]=W(pr[i-1]+((i&1)?p-ifac[i]:ifac[i]));
int mx(0);std::cin>>T;
for(int i(1);i<=T;++i)
{
int n,m;std::cin>>n>>m;
if(n>=2*m)
{
bs[i]=1ll*fac[n-m]*ifac[n-2*m]%p;
if(n-2*m==0) ans[i]=fac[n-m];
else if(!m) ans[i]=1ll*fac[n]*pr[n]%p;
else qs[++c]={n-2*m,m,i};
mx=std::max(mx,m);
}
}
int px(1),py(1),v1(1),v2(1),b(std::max(int(std::sqrt(mx)),1));
std::sort(qs+1,qs+c+1,[b](auto a,auto c)->bool
{
int b1((std::get<1>(a)-1)/b),b2((std::get<1>(c)-1)/b);
if(b1!=b2) return b1<b2;
if(b1&1) return std::get<0>(a)>std::get<0>(c);
else return std::get<0>(a)<std::get<0>(c);
});
for(int i(1);i<=c;++i)
{
auto [x,y,id]=qs[i];
while(py<y)
{
int v2p((1ll*px*v1+1ll*(px+py+1)*v2)%p);
int v1p(W(v1+v2));
++py;v2=v2p;v1=v1p;
}
while(px<x)
{
int v1p(v2);
int v2p((1ll*px*v1+1ll*(px+py)*v2)%p);
++px;v2=v2p;v1=v1p;
}
while(py>y)
{
int v2p((v2+1ll*(p-v1)*px)%p*inv[py]%p);
int v1p(W(v1-v2p+p));
--py;v2=v2p;v1=v1p;
}
while(px>x)
{
int v2p(v1);
int v1p((v2+1ll*(p-v1)*(px+py-1))%p*inv[px-1]%p);
--px;v2=v2p;v1=v1p;
}
ans[id]=v2;
}
for(int i(1);i<=T;++i) std::cout<<1ll*ans[i]*bs[i]%p<<"\n";
return 0;
}LNOI2022 T3 盒
有 $n$ 个不同的盒子排成一排。在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $S=\sum_{i=1}^na_i$。对于非负整数数组 $\left(b_1,b_2,\dots,b_n\right)$ 满足 $\sum_{i=1}^nb_i=S$，考察以下问题：
你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的恰好一个货物移动至另一个。对 $i,i+1\left(1\le i\lt n\right)$ 号盒子做一次操作的代价为 $w_i$。注意：将 $i$ 号盒子的一个货物移动到 $i+1$ 号盒子和将 $i+1$ 号盒子的一个货物移动到 $i$ 号盒子的代价都是 $w_i$。你需要保证在操作中不存在盒子中的货物数量是负数。
在以上问题下，定义从初始状态达到第 $i$ 个盒子拥有恰好 $b_i$ 个货物的状态的最小代价为 $val\left(b_1,b_2,\dots,b_n\right)$，你需要求出对所有满足 $\sum_{i=1}^nb_i=S$ 的非负整数数组 $\left(b_1,b_2,\dots,b_n\right)$，$val\left(b_1,b_2,\dots,b_n\right)$ 的和。输出这个答案对 $998244353$ 取模后的结果。
$T\le 5,n\le 5\times 10^5,S\le 2\times 10^6$
题解
考虑每一个 $w_i$ 对答案的贡献:
$$ \sum_{k=0}^{S}\binom{k+i-1}{i-1}\binom{S-k+n-i-1}{n-i-1}\left|S-\sum_{j\le i}a_j\right|w_i $$
令 $f\left(a,S,b,c\right)=\sum_{k=0}^a\binom{k+b}{b}\binom{S-k+c}{c},g\left(a,S,b,c\right)=\sum_{k=0}^a\binom{k+b}{b}\binom{S-k+c}{c}k$，$Pre_i=\sum_{j\le i}a_j$则只需要求出 $f\left(Pre_i,S,i-1,n-i-1\right)$，$g\left(Pre_i,S,i-1,n-i-1\right)$，$f\left(S-Pre_i,S,n-i-1,i-1\right)$ 和 $g\left(S-Pre_i,S,n-i-1,i-1\right)$。
注意到 $b+c=i-1+n-i-1=n-2$ 是一个定值，而且 $f\left(a,S,b,c\right)$ 转移到 $f\left(a+1,S,b,c\right)$，$g\left(a,S,b,c\right)$ 转移到 $g\left(a+1,S,b,c\right)$ 都是简单的，因此只需要考虑如何从 $f\left(a,S,b-1,c\right)$ 转移到 $f\left(a,S,b,c-1\right)$，以及如何从 $g\left(a,S,b-1,c\right)$ 转移到 $g\left(a,S,b,c-1\right)$ 即可。
根据组合数加法公式，有:
$$ \begin{aligned} f\left(a,S,b,c\right)&=\sum_{k=0}^a\binom{k+b}{b}\binom{S-k+c}{c}\\ &=\sum_{k=0}^a\left(\binom{k+b-1}{b-1}+\binom{k+b-1}{b}\right)\binom{S-k+c}{c}\\ &=f\left(a,S,b-1,c\right)+\sum_{k=0}^{a-1}\binom{k+b}{b}\left(\binom{S-k+c}{c}-\binom{S-k+c-1}{c-1}\right)\\ &=f\left(a,S,b-1,c\right)+f\left(a-1,S,b,c\right)-f\left(a-1,S,b,c-1\right) \end{aligned} $$
移一下项可以得到
$$ \begin{aligned} f\left(a,S,b,c-1\right)&=f\left(a-1,S,b,c-1\right)+\binom{a+b}{b}\binom{S-a+c-1}{c-1}\\ &=f\left(a,S,b-1,c\right)+f\left(a-1,S,b,c\right)-f\left(a,S,b,c\right)+\binom{a+b}{b}\binom{S-a+c-1}{c-1}\\ &=f\left(a,S,b-1,c\right)-\binom{a+b}{b}\binom{S-a+c}{c}+\binom{a+b}{b}\binom{S-a+c-1}{c-1} \end{aligned} $$
同理可得:
$$ \begin{aligned} g\left(a,S,b,c\right)=&\sum_{k=0}^a\binom{k+b}{b}\binom{S-k+c}{c}k\\ =&\sum_{k=0}^a\left(\binom{k+b-1}{b-1}+\binom{k+b-1}{b}\right)\binom{S-k+c}{c}k\\ =&g\left(a,S,b-1,c\right)+f\left(a-1,S,b,c\right)-f\left(a-1,S,b,c-1\right)+g\left(a-1,S,b,c\right)-g\left(a-1,S,b,c-1\right)\\ g\left(a,S,b,c-1\right)=&g\left(a-1,S,b,c-1\right)+\binom{a+b}{b}\binom{S-a+c-1}{c-1}a\\ =&g\left(a,S,b-1,c\right)-\binom{a+b}{b}\binom{S-a+c}{c}a+\binom{a+b}{b}\binom{S-a+c-1}{c-1}a\\ &+f\left(a-1,S,b,c\right)-f\left(a-1,S,b,c-1\right)\\ =&g\left(a,S,b-1,c\right)-\binom{a+b}{b}\binom{S-a+c}{c}(a+1)+\binom{a+b}{b}\binom{S-a+c-1}{c-1}\left(a+1\right)\\ &+f\left(a,S,b,c\right)-f\left(a,S,b,c-1\right) \end{aligned} $$
同时维护 $f\left(a,S,b,c\right),f\left(a,S,b+1,c\right),g\left(a,S,b,c\right)$ 即可
Code
#include <iostream>
#include <algorithm>
namespace fr{
#include <ctype.h>
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define putchar(c) (((O==obuf+(1<<23))?(fwrite(obuf,1,O-obuf,stdout),O=obuf):O),*O++=(c))
void rd(char *x){char c=getchar();while(isspace(c)) c=getchar();while(!isspace(c) && c!=EOF) *(x++)=c,c=getchar();*(x++)='\0';}
template<class T> void rd(T &x){T ret=0;bool flg=false;char c=getchar();while(!isdigit(c) && c!='-') c=getchar();
if(c=='-') c=getchar(),flg=true;while(isdigit(c)) ret=(ret<<1)+(ret<<3)+(c-'0'),c=getchar();if(flg) x=-ret;else x=ret;}
void pc(char c){putchar(c);}void flush(){fwrite(obuf,1,O-obuf,stdout),O=obuf;}
template<class T> void wr(T x){if(x<0) putchar('-'),x=-x;if(x==0) putchar('0');static int cnt,stk[110];cnt=0;while(x) stk[++cnt]=x%10,x/=10;
for(int i=cnt;i;--i) putchar(stk[i]+'0');}
}
using fr::rd;using fr::pc;using fr::wr;using fr::flush;
constexpr int N(2e6+5e5+10),p(998244353);
int ifac[N],fac[N],inv[N];
int binom(int a,int b){return 1ll*fac[a]*ifac[b]%p*ifac[a-b]%p;}
namespace calc
{
int vf,vg,vf1,S,a,b,c;//f(a,b,c),g(a,b,c),f(a,b+1,c);
void init(int _S,int _a,int _b,int _c)
{
S=_S;a=_a,b=_b,c=_c;
vf=0;vg=0;vf1=0;
for(int i(0);i<=a;++i)
{
vf=(vf+1ll*binom(i+b,b)*binom(S-i+c,c))%p;
vg=(vg+1ll*binom(i+b,b)*binom(S-i+c,c)%p*i)%p;
vf1=(vf1+1ll*binom(i+b+1,b+1)*binom(S-i+c,c))%p;
}
}
std::pair<int,int> qry(int _a,int _b)
{
while(b<_b)
{
int nvf( (vf +1ll*(p-binom(a+b+1,b+1))*binom(S-a+c,c) +1ll*binom(a+b+1,b+1)*binom(S-a+c-1,c-1))%p);
int nvf1((vf1+1ll*(p-binom(a+b+2,b+2))*binom(S-a+c,c) +1ll*binom(a+b+2,b+2)*binom(S-a+c-1,c-1))%p);
int nvg( (vg +1ll*(p-binom(a+b+1,b+1))*binom(S-a+c,c)%p*a+1ll*binom(a+b+1,b+1)*binom(S-a+c-1,c-1)%p*a
-nvf+vf1+p+1ll*binom(a+b+1,b+1)*binom(S-a+c-1,c-1)+1ll*(p-binom(a+b+1,b+1))*binom(S-a+c,c))%p);
vf=nvf;vf1=nvf1;vg=nvg;
++b;--c;
}
while(b>_b)
{
int nvf( (vf +1ll*binom(a+b,b)*binom(S-a+c+1,c+1) +1ll*(p-binom(a+b,b))*binom(S-a+c,c))%p);
int nvf1((vf1+1ll*binom(a+b+1,b+1)*binom(S-a+c+1,c+1)+1ll*(p-binom(a+b+1,b+1))*binom(S-a+c,c))%p);
int nvg( (vg +1ll*binom(a+b,b)*binom(S-a+c+1,c+1)%p*a+1ll*(p-binom(a+b,b))*binom(S-a+c,c)%p*a
-nvf1+vf+p+1ll*(p-binom(a+b,b))*binom(S-a+c,c)+1ll*binom(a+b,b)*binom(S-a+c+1,c+1))%p);
vf=nvf;vf1=nvf1;vg=nvg;
--b;++c;
}
while(a<_a)
{
++a;
vf=(vf+1ll*binom(a+b,b)*binom(S-a+c,c))%p;
vf1=(vf1+1ll*binom(a+b+1,b+1)*binom(S-a+c,c))%p;
vg=(vg+1ll*binom(a+b,b)*binom(S-a+c,c)%p*a)%p;
}
while(a>_a)
{
vf=(vf+1ll*(p-binom(a+b,b))*binom(S-a+c,c))%p;
vf1=(vf1+1ll*(p-binom(a+b+1,b+1))*binom(S-a+c,c))%p;
vg=(vg+1ll*(p-binom(a+b,b))*binom(S-a+c,c)%p*a)%p;
--a;
}
return {vf,vg};
}
}
int main()
{
inv[1]=1;for(int i(2);i<N;++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
fac[0]=ifac[0]=1;for(int i(1);i<N;++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
int T;
rd(T);
while(T--)
{
int n;rd(n);
static int a[N],b[N],pre[N];
for(int i(1);i<=n;++i) rd(a[i]),pre[i]=pre[i-1]+a[i];
for(int i(1);i<n;++i) rd(b[i]);
calc::init(pre[n],0,0,n-2);
int ans(0);
for(int i(1);i<n;++i)
{
auto [v1,v2]=calc::qry(pre[i],i-1);
ans=(ans+(1ll*pre[i]*v1+p-v2)%p*b[i])%p;
}
for(int i(1);i<n;++i)
{
auto [v1,v2]=calc::qry(pre[n]-pre[i],n-i-1);
ans=(ans+(1ll*(pre[n]-pre[i])*v1+p-v2)%p*b[i])%p;
}
std::cout<<ans<<"\n";
}
return 0;
}本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。