前缀和与组合数
一道题会涉及组合数一般有这么几种可能
- 题目公式里直接带了组合数。
- 题目和排列组合相关
- 特殊的高维前缀和
第一种第二种比较明显的和组合数相关联。
而第三种就和组合数的性质相关。
我认为多次前缀和会与组合数产生联系的本质是组合数的一个公式。
\(C(m,n)=C(m-1,n-1)+C(m-1,n)\)
(我记\(C(m,n)\)为从\(m\)个物品中取\(n\)个物品的组合)
从一般到特殊感受一下。
常数数组的高维前缀和
以常数为\(1\)举例，不同常数乘一个倍数即可。
记原数组ar，\(f^k(ar)\)为\(ar\)的\(k\)次前缀和
数值角度
\(\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}
\hline ar&1&1&1&...\\\hline
f(ar)&1&2&3&...\\\hline
f^2(ar)&1&3&6&...\\\hline
f^3(ar)&1&4&10&...\\\hline
f^4(ar)&1&5&15&...\\\hline
....&...&...&...&...\\\hline
\end{array}\)
记\(ar(x,y)\)为第\(x\)行，第\(y\)列的数。
有\(ar(x,y)=\sum^y_{i=1} ar(x-1,i)\)
前缀和式\(ar(x,y)=ar(x,y-1)+ar(x-1,y)\)
这和\(C(m,n)=C(m-1,n-1)+C(m-1,n)\)非常相似。事实上可以发现\(a(x,y)=C(x+y-2,y-1)\)当然，行列从\(0\)开始编号的话就恰好是\(ar(x,y)=C(x+y,y)\)。
路径
事实上，考虑从起点\((0,0)到(x,y)\),一次只能横坐标加一或者纵坐标加一，不同的路径数量，也是\(C(x+y,y)\),这个更好理解，就是一共走\(x+y\)步，然后挑选\(y\)步选择纵坐标加一。
\(C(m,n)=C(m-1,n-1)+C(m-1,n)\)在路径上的体现就是\((x,y)\)可以从\((x-1,y)\)或者\((x,y-1)\)直接到达。
任意数组高维前缀和
首先定义数组的加法:数组\(a,b,c\),\(\forall i\in N,a_i=b_i+c_i\)就记为\(a=b+c\)
前缀和的性质: $a=b+c \lrarr f ^ k(a)=f ^ k(b)+f ^ k(c) $ ，这说明原数组的前缀和的贡献是可加的。那我们直接按位计算前缀和贡献。
我们首先得知道某一位的\(1\)会产生什么样子的贡献。
\(\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}
\hline a&1&0&0&...\\\hline
f(a)&1&1&1&...\\\hline
f^2(a)&1&2&3&...\\\hline
f^3(a)&1&3&6&...\\\hline
f^4(a)&1&4&10&...\\\hline
....&...&...&...&...\\\hline
\end{array}\)
规定从\(0\)开始编号
所以，记\(a_0\)位置为\((0,0)\),\(a_0\)对\([f^k(a)]_j\)的贡献是\(C(k+j,j)\)
同理的\(a_i\)对\([f^k(a)]_j\)的贡献是\(C(k+j-i,j-i)\)
那么\([f^k(a)] _j=\sum^j_{i=1} a_i\times C(k+j-i,j-i)\)
例题：Fenwick Tree
题目来源
https://codeforces.com/contest/1967/problem/C
codeforces round 942 div1 C
题目翻译
首先定义\(lowbit(i)\)为\(i\)转换为二进制，最小的为1的二进制位的权值。比如\(12=1100(B)=8+4,lowbit(12)=4\),\(lowbit(8)=8\)。
对于等长的数组\(s,a\)若满足$$s_k=(\sum^k_{i=k-lowbit(k)+1} a_i )mod\ 998244353$$则记为\(s=f(a)\)
\(f^k(a)=\begin{cases}a& if\ k=0 \\ f(f^{k-1}(a)) & if\ k\in N^* \end{cases}\)
给定数组长度\(n\)和\(k,b=f^k(a)\)求\(a\)
- 数据范围：\(0\le a_i,b_i<998244353,1\le n\le 2\cdot 10^5,1\le k\le 10^9\)
- 时空限制：\(3s,256MB\)
解法
先不考虑取模。
\(s_k=\sum^k_{i=k-lowbit(k)+1} a_i\)
这一部分其实是树状数组式的前缀和。
考虑\(a_i\)对\(s_k\)的贡献。
树状数组式的前缀和每一位如此提供贡献
void Modify(int x,int w){//a[x]=w
while(x<=n){
s[x]+=w;
x+=lowbit(x);//lowbit(x)=x&-x;
}
}
再看看\(a_1\)的贡献
\(\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}
\hline 下标&1&2&4&...&2^i\\\hline
a&1(系数)&0&0&...&0\\\hline
f(a)&1&1&1&...&1\\\hline
f^2(a)&1&2&3&...&i+1\\\hline
f^3(a)&1&3&6&...&C(i+2,2)\\\hline
f^4(a)&1&4&10&...&C(i+3,3)\\\hline
....&...&...&...&...&...\\\hline
f^k(a)&C(k-1,0)&C(k,1)&C(k+1,2)&...&C(k+i-1,k)\\\hline
\end{array}\)
对于\(a_2,a_3\)啥的都是一样的
下标序列生成方式即\(x+=lowbit(x)\)
然后，对于\(s_i\),\(a_i\)的贡献系数只有\(1\),只要\(s_i\)把\(a_1\sim a_i-1\)的贡献全部减去，就能求得\(a_i\)。
复杂度
下标序列长度和\(O(n\log n)\),
预处理\(O(\log n)\)后,求组合数\(O(1)\)
时间复杂度\(O(n \log n)\)
代码
点我查看代码
#include<bits/stdc++.h>
#define ll long long
//#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f
typedef int LL;
const signed maxn=(signed)1e6+5;
const signed mod=998244353;
inline LL Read(){
char ch=getchar();bool f=0;LL x=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1)x=-x;return x;
}
int add(int a,int b){
return ((a+=b)>=mod)?a-mod:a;
}
int mul(int x,int y){
return (ll) x*y%mod;
}
int fpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=mul(ans,a);
a=mul(a,a);b>>=1;
}
return ans;
}
int inv[105],jc[105];
int Ck(int n){
if(n<0) return 0;
return mul(jc[n],inv[n]);
}
void init(){
inv[0]=jc[0]=1;
for(int i=1;i<=100;++i) jc[i]=mul(jc[i-1],i);
inv[100]=fpow(jc[100],mod-2);
for(int i=99;i;--i) inv[i]=mul(inv[i+1],i+1);
}
void jck(int n,int k){
k%=mod;
int mx=std::__lg(n);
for(int i=1;i<=mx;++i) jc[i]=mul(jc[i-1],k+i-1);
}
int ar[maxn];
signed main()
{
LL T=Read();
init();
while (T--){
int n=Read(),k=Read();
for(int i=1;i<=n;++i) ar[i]=Read();
jck(n,k);
for(int i=1;i<=n;++i){
int x=i+(i&-i),c=1;
while(x<=n){
//printf("ck(%d)=%d\n",c,Ck(c));
ar[x]=add(ar[x],mod-mul(Ck(c),ar[i]));
++c;
x+=x&-x;
}
}
for(int i=1;i<=n;++i) printf("%d%c",ar[i]," \n"[i==n]);
}
return 0;
}