Curious Array

admin管理员组

文章数量:1612098

                                      Curious Array

题目描述：

            这个题目大概讲述的是，输入一个长度为n的a数组，然后有m个操作，每次操作对于任意的，相应的加上，然后题目让我们输出经过m次操作后的a数组。

题目分析：

            由于题目当中的n与m最大达到1e5，因此可能给我一种误解，认为这是线段树的题目，但是如果用线段树去做的话，那么我们会发现组合数的相加比较难以去处理，对于本题来说，线段树不是最好的做法。

            这个题目的正解应用到组合数学当中差分数列的相关知识，首先我们列出杨辉三角，找出当中的规律。

           从上表可以发现，对于每个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;
}

本文标签： curiousArray