admin管理员组文章数量:1612099
文章目录
- 题意
- 题解
在退役之前,最后发几篇杂谈,就算只能再拿省二滚蛋,也要与命运抗争到底.
CF的评测机最近有点儿力不从心…
没想到做过的题又被考了一遍还是做不出,实在不甘心.
题意
给 一 个 序 列 , 有 n 次 操 作 , 每 一 次 给 [ l , r ] 加 上 C i − l + k k , 其 中 l ≤ i ≤ r . 最 后 输 出 操 作 完 的 序 列 . 给一个序列,有n次操作,每一次给[l,r]加上C_{i-l+k}^{k},其中l\leq i\leq r.\newline 最后输出操作完的序列. 给一个序列,有n次操作,每一次给[l,r]加上Ci−l+kk,其中l≤i≤r.最后输出操作完的序列.
题解
看到先操作再询问,又是区间加之类的,想到标算应该是差分.
但是区间加组合数不同于一般的差分,我们暂时想不到有什么方法处理.
那么我们先来考虑简单的情况.
当
k
=
0
k=0
k=0时,必然有加上的每一个数都等于
1
1
1.这时只要普通差分即可,不用多解释.
来看
k
=
1
k=1
k=1时的情况,此时加上的每一个数等于
i
−
l
+
1
,
i
∈
[
l
,
r
]
i-l+1,i\in[l,r]
i−l+1,i∈[l,r],也就是区间加了一个等差数列.
区间加等差数列的情况大家想必也都知道怎么差分.
洛谷p4231 三步必杀 洛谷经典差分题,区间加等差数列,推荐大家去做一做.
我们令
a
[
1
]
[
i
]
a[1][i]
a[1][i]表示二层差分数组,在
a
[
1
]
[
l
]
+
1
a[1][l]+1
a[1][l]+1,
a
[
1
]
[
r
+
1
]
−
1
a[1][r+1]-1
a[1][r+1]−1,这样子二层差分的结果在
[
l
,
r
]
[l,r]
[l,r]中就等于
1
,
1
,
1
,
1
,
1
,
1...
1,1,1,1,1,1...
1,1,1,1,1,1....如果在一层再差分一次,结果就是
1
,
2
,
3
,
4
,
5
,
6...
1,2,3,4,5,6...
1,2,3,4,5,6...,这时我们再在一层的
a
[
0
]
[
r
+
1
]
a[0][r+1]
a[0][r+1]的地方把多出来的
r
−
l
+
1
r-l+1
r−l+1减掉,就搞定了.
根据这样的情况大胆猜想,我们对于每一次操作都要差分
k
k
k层.
每一次把
a
[
k
]
[
l
]
+
1
a[k][l]+1
a[k][l]+1,然后用一个
j
j
j从
0
0
0到
k
k
k,分别把每一层差分从
r
+
1
r+1
r+1个位置开始会多加的数给减掉.可以发现这些结果全部是组合数.
因此只要用杨辉三角或者阶乘逆元预处理组合数,每一次
O
(
k
)
O(k)
O(k)差分,最后一遍
O
(
n
k
)
O(nk)
O(nk)处理从最后一层差分回第一层,并输出加上原数组的结果即可.
谢谢大家.
希望大家对差分的理解更深一层,也希望我对差分也能理解得更深一点.
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
int x=0,f=1;char c=gc();
for (;!isdigit(c);c=gc()) f^=c=='-';
for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
return f?x:-x;
}
template <typename mitsuha>
inline bool read(mitsuha &x){
x=0;int f=1;char c=gc();
for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
if (!~c) return 0;
for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
return x=f?x:-x,1;
}
template <typename mitsuha>
inline int write(mitsuha x){
if (!x) return 0&pc(48);
if (x<0) pc('-'),x=-x;
int bit[20],i,p=0;
for (;x;x/=10) bit[++p]=x%10;
for (i=p;i;--i) pc(bit[i]+48);
return 0;
}
inline char fuhao(){
char c=gc();
for (;isspace(c);c=gc());
return c;
}
}using namespace chtholly;
using namespace std;
const int yuzu=2e5,mod=1e9+7;
typedef ll rize[yuzu|10];
rize a[115],jic={1},inv;
namespace quick{ // 快速幂等公式
ll kasumi(ll a,ll b=mod-2) {
ll s=1;
for (;b;b>>=1,a=a*a%mod) if (b&1) s=s*a%mod;
return s;
}
void add(ll &a,ll b){if ((a+=b)>=mod) a-=mod;}
void sub(ll &a,ll b){if ((a-=b)<0) a+=mod;}
ll zuhe(int n,int m){return jic[n]*inv[m]%mod*inv[n-m]%mod;}
}using namespace quick;
void preget(int n,int i=1) { // 预处理阶乘逆元
for (;i<=n;++i) jic[i]=jic[i-1]*i%mod;
inv[n]=kasumi(jic[n]);
for (i=n-1;~i;--i) inv[i]=inv[i+1]*(i+1)%mod;
}
int main() {
int i,j,n,m,l,r,k;
read(n),read(m),preget(yuzu);
static rize p;
for (i=1;i<=n;++i) p[i]=read();
for (i=1;i<=m;++i) {
l=read(),r=read(),k=read();
add(a[k][l],1);
for (j=0;j<=k;++j)
sub(a[j][r+1],zuhe(k-j+r-l,k-j)); // 稍微算一下,可以发现每一层多加的数也是组合数.
}
for (i=100;~i;--i)
for (j=1;j<=n;++j)
a[i][j]=(a[i][j]+a[i+1][j]+a[i][j-1])%mod;
for (i=1;i<=n;++i) write((a[0][i]+p[i])%mod),p32;
}
本文标签: 组合多层差分ampcodeforces
版权声明:本文标题:Codeforces 407C&408E Curious Array 组合数多层差分 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728631342a1167121.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论