Prefix Sum —— 树状数组+懵逼的组合恒等式

本文主要是介绍Prefix Sum —— 树状数组+懵逼的组合恒等式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://www.nowcoder.com/acm/contest/147/H
来源：牛客网

Niuniu has learned prefix sum and he found an interesting about prefix sum.

Let’s consider (k+1) arrays a[i] (0 <= i <= k)
The index of a[i] starts from 1.
a[i] is always the prefix sum of a[i-1].
“always” means a[i] will change when a[i-1] changes.
“prefix sum” means a[i][1] = a[i-1][1] and a[i][j] = a[i][j-1] + a[i-1][j] (j >= 2)

Initially, all elements in a[0] are 0.
There are two kinds of operations, which are modify and query.
For a modify operation, two integers x, y are given, and it means a[0][x] += y.
For a query operation, one integer x is given, and it means querying a[k][x].

As the result might be very large, you should output the result mod 1000000007.

输入描述:
The first line contains three integers, n, m, k.
n is the length of each array.
m is the number of operations.
k is the number of prefix sum.

In the following m lines, each line contains an operation.

If the first number is 0, then this is a change operation.
There will be two integers x, y after 0, which means a[0][x] += y;
If the first number is 1, then this is a query operation.

There will be one integer x after 1, which means querying a[k][x].

1 <= n <= 100000
1 <= m <= 100000
1 <= k <= 40
1 <= x <= n
0 <= y < 1000000007
输出描述:
For each query, you should output an integer, which is the result.
示例1
输入
复制
4 11 3
0 1 1
0 3 1
1 1
1 2
1 3
1 4
0 3 1
1 1
1 2
1 3
1 4
输出
复制
1
3
7
13
1
3
8
16
说明
For the first 4 queries, the (k+1) arrays are
1 0 1 0
1 1 2 2
1 2 4 6
1 3 7 13
For the last 4 queries, the (k+1) arrays are
1 0 2 0
1 1 3 3
1 2 5 8
1 3 8 16

//这是个有问题的博客
这道题做了很久很久，还是没做出来，完全不知道组合数用树状数组怎么维护，各种骚操作都失败。就连看别人的代码也是一脸懵逼，最后才发现这和树状数组其实没有什么特别大的关系，它就是用来存一下数据的，接下来就是令人绝望的组合恒等式
这里写图片描述
我也不知道这个是什么玩意，以后搞懂了在说（数论不是我负责的，以后也不会懂），先记着。
它每一个树状数组记录的是杨辉三角中的一排，就算有负数也会加上一个mod，在query的时候会消掉，就比如说要求的答案是21，他是通过1*0+3*1+3*4+1*6这么过来的。。。其实我也不懂，调试别人代码的时候发现的这个规律

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int maxn=1e5+5;
ll c[55];
ll sum[55][maxn];
int n,m,k;
int lowbit(int x)
{return x&(-x);
}
void add(int i,int pos,int val)
{for(int j=pos;j<=n;j+=lowbit(j))sum[i][j]=(sum[i][j]+val)%mod;
}
int query(int i,int pos)
{int ans=0;for(int j=pos;j>=1;j-=lowbit(j))ans=(ans+sum[i][j])%mod;return ans;
}
int main()
{c[1]=1;for(int i=2;i<=50;i++)c[i]=(ll)(mod-mod/i)*c[mod%i]%mod;scanf("%d%d%d",&n,&m,&k);k-=1;int q,pos,val;while(m--){scanf("%d",&q);if(q==0){scanf("%d%d",&pos,&val);ll u=1;for(int i=0;i<=k;i++){add(i,pos,(ll)val*u%mod);u=(u*(k-pos-i)%mod+mod)%mod*c[i+1]%mod;}}else{scanf("%d",&pos);ll u=1,ans=0;for(int i=0;i<=k;i++){ans=(ans+u*query(k-i,pos))%mod;u=u*(pos-i)%mod*c[i+1]%mod;}printf("%lld\n",ans);}}return 0;
}