Description

小 F 是一位 Hack 國的居民，他生活在一條長度為 n 的街道上，這個街道上總共有 n 個商店。每個商店里售賣著不同的 Hack 技能包，每個商店本身也會有個便利值。初始時，每個商店的便利值均為 0。每一天，街道上都會有一些商店優化改造。
具體來說，對于每一天，優化改造的商店都是一個連續的區間 l ～ r，每次優化改造也會有一個優化參數 k。對于所有 l ≤ i ≤ r ，第 i 個商店的便利值會增加
小 F 想知道，m 天之后，每個商店的便利值分別是多少。由于小 F 并不喜歡高精度，因此你只需要輸出便利值對 10^9 + 7 取模的結果。

Input

從文件sequence.in中讀入數據。
第 1 行，兩個整數 n, m 表示街道的長度與天數。
接下來的 m 行，每行三個整數 l, r, k，表示第 i 天優化改造的商店區間和優化參數。

Output

輸出到文件sequence.out中，共 n 行。
每行 1 個整數，表示第 i 個商店的便利值對 109 + 7 取模的結果。

Sample Input

5 3
1 4 3
2 5 0
3 4 2

Sample 2

見選手目錄下的sequence/sequence2.in與sequence/sequence2.ans。
該組樣例的數據范圍同第 1 個測試點。

Sample Output

1
5
12
24
1

第 1 次操作之后，每個商店的便利值分別為 1, 4, 10, 20, 0。
第 2 次操作之后，每個商店的便利值分別為 1, 5, 11, 21, 1。
第 3 次操作之后，每個商店的便利值分別為 1, 5, 12, 24, 1。

Data Constraint

對于 100% 的數據，滿足 1 ≤ n, m ≤ 5 × 10^5, 0 ≤ k ≤ 20。除此之外，對于每個數據點，還滿足以下限制。

Solution

• 對于一個點 $x$，區間加操作加的數為$$C_{x+k?l}^k=\frac{1}{k!}?(x?l+1)?(x?l+2)?\dots ?(x?l+k)$$

• 我們發現可以暴力展開這個關于 $x$ 的多項式，并將其當做一個標記（長度為 $20$）。

• 之后在 $l$ 處加上這個標記，在 $r+1$ 處減去這個標記。

• 最后求答案時做前綴和，每次得到位置 $i$ 的一個多項式，將 $i$ 代入 $x$ 算即可。

• 時間復雜度 $O(n{k}^2)$ ，吸氧就能過啦。

• 如果用 $k$ 階差分可以做到 $O(nk)$ 。

Code

#pragma GCC optimize(2) #include<cstdio> #include<cstring> #include<cctype> using namespace std; typedef long long LL; const int N=5e5+5,mo=1e9+7; int f[21],g[21],h[N][21],d[21],c[21]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int ksm(int x,int y) {int s=1;while(y){if(y&1) s=(LL)s*x%mo;x=(LL)x*x%mo;y>>=1;}return s; } int main() {freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);int n=read(),m=read();f[0]=g[0]=1;for(int i=1;i<=20;i++) f[i]=(LL)f[i-1]*i%mo;g[20]=ksm(f[20],mo-2);for(int i=19;i;i--) g[i]=(LL)g[i+1]*(i+1)%mo;while(m--){int l=read(),r=read(),k=read();if(!k){h[l][0]++;h[r+1][0]=(h[r+1][0]-1+mo)%mo;continue;}c[0]=(mo-l+1)%mo;c[1]=1;int len=1;for(int i=2;i<=k;i++){c[++len]=0;for(int j=0;j<=len;j++) d[j]=c[j];for(int j=1;j<=len;j++) c[j]=d[j-1];for(int j=c[0]=0;j<len;j++) c[j]=(c[j]+(LL)d[j]*(i-l+mo))%mo;}for(int i=0;i<=len;i++){h[l][i]=(h[l][i]+(LL)c[i]*g[k])%mo;h[r+1][i]=(h[r+1][i]-(LL)c[i]*g[k]%mo+mo)%mo;}}memset(c,0,sizeof(c));for(int i=1;i<=n;i++){for(int j=0;j<=20;j++) c[j]=(c[j]+h[i][j])%mo;int ans=0,base=1;for(int j=0;j<=20;j++){ans=(ans+(LL)c[j]*base)%mo;base=(LL)base*i%mo;}write(ans),putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5922. 【NOIP2018模拟10.23】sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。