You've got an array consisting of n integers: a[1], a[2], ..., a[n]. Moreover, there are m queries, each query can be described by three integers li, ri, ki. Query li, ri, ki means that we should add to each element a[j], where li ≤ j ≤ ri.
Record means the binomial coefficient, or the number of combinations from y elements into groups of x elements.
You need to fulfil consecutively all queries and then print the final array.
链接🔗
「CodeForces 407C」Curious Array
题解
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e5+100;
const int mod = 1e9+7;
typedef long long LL;
int n,m;
long long a[maxd],c[maxd][105],ans[maxd][105];
void init()
{
c[0][0] = 1ll;
for (int i = 1; i < maxd; ++i) {
c[i][0] = 1ll;
for (int j = 1; j <= i && j < 105; ++j) {
c[i][j] = (1ll * c[i-1][j-1] + c[i-1][j]) % mod;
}
}
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int j=1;j<=m;j++)
{
int l,r,k;
scanf("%d %d %d",&l,&r,&k);
//
for(int i=0;i<=k;i++) ans[l][i] = (1ll * ans[l][i] + c[k][k-i]) %mod;
// 减去前缀和
for(int i=0;i<=k;i++) ans[r+1][i] = (1ll *ans[r+1][i] - c[r-l+k+1][k-i]) %mod;
}
for (int i = 1; i < n; ++i)
for (int j = 101; j >= 1; --j)
ans[i+1][j-1] = (1ll * ans[i+1][j-1] + ans[i][j] + ans[i][j-1]) % mod;
for (int i = 1; i <= n; ++i) printf("%lld ",((ans[i][0] + a[i]) % mod + mod) % mod);
return 0;
}