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

链接&＃xff1a;https://www.nowcoder.com/acm/contest/147/H
来源&＃xff1a;牛客网

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

Let’s consider (k&＃43;1) arrays a[i] (0 <&＃61; i <&＃61; 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] &＃61; a[i-1][1] and a[i][j] &＃61; a[i][j-1] &＃43; a[i-1][j] (j >&＃61; 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] &＃43;&＃61; 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] &＃43;&＃61; 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 <&＃61; n <&＃61; 100000
1 <&＃61; m <&＃61; 100000
1 <&＃61; k <&＃61; 40
1 <&＃61; x <&＃61; n
0 <&＃61; 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&＃43;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&＃43;1) arrays are
1 0 2 0
1 1 3 3
1 2 5 8
1 3 8 16

//这是个有问题的博客
这道题做了很久很久&＃xff0c;还是没做出来&＃xff0c;完全不知道组合数用树状数组怎么维护&＃xff0c;各种骚操作都失败。就连看别人的代码也是一脸懵逼&＃xff0c;最后才发现这和树状数组其实没有什么特别大的关系&＃xff0c;它就是用来存一下数据的&＃xff0c;接下来就是令人绝望的组合恒等式

我也不知道这个是什么玩意&＃xff0c;以后搞懂了在说&＃xff08;数论不是我负责的&＃xff0c;以后也不会懂&＃xff09;&＃xff0c;先记着。
它每一个树状数组记录的是杨辉三角中的一排&＃xff0c;就算有负数也会加上一个mod&＃xff0c;在query的时候会消掉&＃xff0c;就比如说要求的答案是21&＃xff0c;他是通过1*0&＃43;3*1&＃43;3*4&＃43;1*6这么过来的。。。其实我也不懂&＃xff0c;调试别人代码的时候发现的这个规律

#include
using namespace std;
#define ll long long
const ll mod&＃61;1e9&＃43;7;
const int maxn&＃61;1e5&＃43;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&＃61;pos;j<&＃61;n;j&＃43;&＃61;lowbit(j))sum[i][j]&＃61;(sum[i][j]&＃43;val)%mod;
}
int query(int i,int pos)
{int ans&＃61;0;for(int j&＃61;pos;j>&＃61;1;j-&＃61;lowbit(j))ans&＃61;(ans&＃43;sum[i][j])%mod;return ans;
}
int main()
{c[1]&＃61;1;for(int i&＃61;2;i<&＃61;50;i&＃43;&＃43;)c[i]&＃61;(ll)(mod-mod/i)*c[mod%i]%mod;scanf("%d%d%d",&n,&m,&k);k-&＃61;1;int q,pos,val;while(m--){scanf("%d",&q);if(q&＃61;&＃61;0){scanf("%d%d",&pos,&val);ll u&＃61;1;for(int i&＃61;0;i<&＃61;k;i&＃43;&＃43;){add(i,pos,(ll)val*u%mod);u&＃61;(u*(k-pos-i)%mod&＃43;mod)%mod*c[i&＃43;1]%mod;}}else{scanf("%d",&pos);ll u&＃61;1,ans&＃61;0;for(int i&＃61;0;i<&＃61;k;i&＃43;&＃43;){ans&＃61;(ans&＃43;u*query(k-i,pos))%mod;u&＃61;u*(pos-i)%mod*c[i&＃43;1]%mod;}printf("%lld\n",ans);}}return 0;
}