admin管理员组文章数量:1612098
Curious Array
题目描述:
这个题目大概讲述的是,输入一个长度为n的a数组,然后有m个操作,每次操作对于任意的,相应的加上,然后题目让我们输出经过m次操作后的a数组。
题目分析:
由于题目当中的n与m最大达到1e5,因此可能给我一种误解,认为这是线段树的题目,但是如果用线段树去做的话,那么我们会发现组合数的相加比较难以去处理,对于本题来说,线段树不是最好的做法。
这个题目的正解应用到组合数学当中差分数列的相关知识,首先我们列出杨辉三角,找出当中的规律。
1 | ||||
1 | 1 | |||
1 | 2 | 1 | ||
1 | 3 | 3 | 1 | |
1 | 4 | 6 | 4 | 1 |
1 | 5 | 10 | 10 | 5 |
k=0 | k=1 | k=2 | k=3 | k=4 |
从上表可以发现,对于每个k,其中第i行的数值等于k-1的前i-1行数值的前缀和。
而对于每个,所形成的数列可以由数列经过求k+1次前缀和来得到。
当然对于r+1后面的数并不需要改变,因此我们在求每次前缀和的后面需要减去当前k状态下的l到r的区间总和,保证k+1求前面的前缀和的时候,后面的数不受影响,然后其实我们发现m个操作当中,k是不尽相同的,我们很容易会想到将k从大到小排序,排除不同k值互相之间的干扰,但是其实我们发现可以构造一个二维数组,每次操作将第k个一维数组的l位置加上1,然后后面的r+1位置减去相应的数,保证r+1位置后面的数数值不变,然后我们从k的最大值往回求前缀和,求到第0个一维数组的时候,我们就会发现第0个一维数组的每个值就是a[i]在m次操作后的增量,最后将a[i]加上相应的增量即为答案。
值得注意的是,上述运算可能数值很大,需要对1e9+7取模。
代码:
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <string>
#include <string.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#define reg register
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define lowbit(x) (x&(-x))
using namespace std;
const int Maxn=1e5+5;
const int Maxm=1e5+5;
const int Maxk=105;
int a[Maxn];
ll s[Maxk][Maxn],fac[Maxn*2],inv[Maxn*2];
ll Flt(ll p,int n)
{
ll ans=1;
while (n)
{
if (n&1) ans=(ans*p)%mod;
p=(p*p)%mod;
n>>=1;
}
return ans;
}
ll C(int n,int m)
{
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
fac[0]=inv[0]=1;
for (reg int i=1;i<=200000;i++) fac[i]=(fac[i-1]*1LL*i)%mod;
inv[200000]=Flt(fac[200000],mod-2);
for (reg int i=199999;i>=1;i--) inv[i]=(inv[i+1]*1LL*(i+1))%mod;
for (reg int i=1;i<=n;i++) scanf("%d",&a[i]);
while (m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
s[k][l]++;
for (reg int i=k;i>=0;i--) s[i][r+1]=(s[i][r+1]-C(k-i+r-l,k-i)+mod)%mod;
}
for (reg int i=100;i>=0;i--)
{
for (reg int j=1;j<=n;j++) s[i][j]=(s[i][j]+s[i+1][j]+s[i][j-1])%mod;
}
for (reg int i=1;i<=n;i++) printf("%lld ",(s[0][i]+a[i])%mod);
return 0;
}
版权声明:本文标题:Curious Array 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728631058a1167089.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论