ZigZagK的博客
[思维+组合+NTT]LOJ6261【一个人的高三楼】题解
[思维+组合+NTT]LOJ6261【一个人的高三楼】题解
2019年3月18日 18:41
LOJ
查看标签

题目概述

给出一个数组,求这个数组的 $k$ 次前缀和(前缀和的前缀和的前缀和……)。

解题报告

就是这题套个NTT,水博客真开心。可能略有卡常……

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=100000,maxt=1<<18,MOD=998244353; int n,INV[maxn+5],a[maxt+5],c[maxt+5];LL K; int rev[maxt+5],pw[2][maxt+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void writei(int x){ static int buf[30],len=0;do buf[len++]=x%10,x/=10; while (x); while (len) putchar(buf[--len]+48); } inline void Make(int n){ INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD; c[0]=1;for (int i=1;i<=n;i++) c[i]=(K-1+i)%MOD*INV[i]%MOD*c[i-1]%MOD; } inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} inline void Pre(int n){ for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1)); for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2); } inline void NTT(int *a,int n,int f){ for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int k=1;k<n;k<<=1){ int gn=pw[f<0][k<<1],g=1,x,y; for (int i=0;i<n;i+=k<<1,g=1) for (int j=0;j<k;j++,g=(LL)g*gn%MOD) x=a[i+j],y=(LL)a[i+j+k]*g%MOD,a[i+j]=(x+y)%MOD,a[i+j+k]=(x+MOD-y)%MOD; }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(K);Make(n);for (int i=0;i<n;i++) readi(a[i]); int t;for (t=1;t<(n<<1);t<<=1);Pre(t);NTT(a,t,1);NTT(c,t,1); for (int i=0;i<t;i++) a[i]=(LL)a[i]*c[i]%MOD;NTT(a,t,-1); for (int i=0;i<n;i++) writei(a[i]),puts("");return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 2206 天前,最后更新于 2206 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏