CodeForces 407C 組合數學(詳解)

2022-09-22 19:32:16 字數 1814 閱讀 2010

題面:

一句話題意:給一個長度為n的序列g,m次操作,每次操作(l,r,k)表示將g[l]~g[r]的每個數g[j](l<=j<=r)加上c(j-l+k,k),輸出經過m操作後的最終序列(mod 1e9+7)(n,m<=1e5,k<=100)。

題解:

首先看到這個題瞬間想到資料結構,但發現一次修改操作中每個點的增加值都不同後果斷放棄。又因為發現這題只有一次詢問,就考慮能不能先將每次操作存下來,最後再進行統一遞推。又看到了k好小。。於是就可以亂搞了!

我們先考慮組合數的遞推,c(n,m)=c(n-1,m)+c(n-1,m-1)。那麼觀察操作,假設我們在修改g[x],並且x>l,那麼g[x-1]已經修改完了,考慮g[x-1]的增加值為c(x-1-l+k,k),而g[x]的值增加了c(x-l+k,k),又因為c(x-l+k,k)=c(x-l-1,k)+c(x-l-1,k-1),但是,顯然只存下每個點的c(x-l+k,k)和每個點的c(x-l+k,k-1)是遠遠不夠的,因為這樣的話就只能推出c(x-l+k+1,k),而無法推出c(x-l+k+1,k-1),接著就無法推出c(x-l+k+2,k),等於說這次操作就無法遞推完。因此我們只要在每一次操作的l處處理出c(k,0~k),就可以做到遞推出每次操作對於每個數的增加值,欸那這有什麼用呢,欸當然有用了!又因為加法有交換律和結合律,所以我們只要在每個l上計算好,在r+1處減去,就可以o(n)遞推出整個序列!因為每在一個l處要處理c(k,0~k),處理m次,所以操作的總複雜度為o(mk),最終遞推每推一步都要推k次組合數。因此整套**的總複雜度為o(mk+nk)!!!!!

如果還有不懂的那就看**然後感性理解一下qwq

p.s. 對於組合數我們是要處理階乘的逆元(inv)的,有一個o(n)遞推1~n逆元的方法:

首先我們考慮如果知道了x+1~n的階乘的inv,如何得到x!的inv。。

根據逆元的定義:n!*inv(n!)=(n-1)!*n*inv(n!)=1=(n-1)!*inv((n-1)!),,欸所以inv((n-1)!)=inv(n!)*n

**:

1 #include2

3using

namespace

std;

45 typedef long

long

ll;6 typedef double

dd;7

const

int maxn=1e5+10;8

const ll p=1e9+7

;9 ll fac[maxn],inv[maxn],g[maxn],ad[maxn][110

];10

intn,m;

1112

ll qpow(ll x,ll b)

18return

sum;19}

2021

void

init()

2930 ll c(int x,int

y)34

35int

main()

4849

for(int i=1;i<=n;i++)

50for(int j=100;j>=0;j--)

51 ad[i][j]=(ad[i][j]+ad[i-1][j]+ad[i-1][j+1]+p)%p;

5253

54for(int i=1;i<=n;i++)

55 printf("

%lld

",(g[i]+ad[i][0]+p)%p);

5657

return

0;

58 }