做网站哪里找程序员,网络营销课程教案,昆明网站建设工作室,wordpress手机页面模板正题
题目链接:https://www.luogu.com.cn/problem/P4721 题目大意
给出序列ggg#xff0c;然后f01f_01f01 fi∑j1ifi−jgjf_{i}\sum_{j1}^if_{i-j}g_jfij1∑ifi−jgj
求序列fff 解题思路
使用分治后用NTTNTTNTT计算前区间对后区间的贡献即可。
时间复杂度O(nlo…正题
题目链接:https://www.luogu.com.cn/problem/P4721 题目大意
给出序列ggg然后f01f_01f01 fi∑j1ifi−jgjf_{i}\sum_{j1}^if_{i-j}g_jfij1∑ifi−jgj
求序列fff 解题思路
使用分治后用NTTNTTNTT计算前区间对后区间的贡献即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,XJQ998244353;
ll n,g[N],f[N],a[N],b[N],R[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;b1;xx*x%XJQ;}return ans;
}
void NTT(ll *f,ll logn,ll op){ll n1logn;for(ll i0;in;i)if(iR[i])swap(f[i],f[R[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(3,(XJQ-1)/p);if(op-1)tmppower(tmp,XJQ-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[leni]%XJQ;f[leni](f[i]-ttXJQ)%XJQ;f[i](f[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}if(op-1){ll tmppower(n,XJQ-2);for(ll i0;in;i)f[i]f[i]*tmp%XJQ;}return;
}
void cdq(ll l,ll r,ll logn){if(!logn) return;if(ln)return;ll n1logn,midlr1;cdq(l,mid,logn-1);for(ll i0;in;i)R[i](R[i1]1)|((i1)?n1:0);memset(a(r-l)/2,0,sizeof(ll)*(r-l)/2);memcpy(a,fl,sizeof(ll)*(r-l)/2);memcpy(b,g,sizeof(ll)*(r-l));NTT(a,logn,1);NTT(b,logn,1);for(ll i0;in;i)a[i]a[i]*b[i]%XJQ;NTT(a,logn,-1);for(ll i(r-l)/2;ir-l;i)f[li](f[li]a[i])%XJQ;cdq(mid,r,logn-1);return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,g[i]);f[0]1;ll logn;for(logn0;(1logn)n;logn);cdq(0,1logn,logn);for(ll i0;in;i)printf(%lld ,(f[i]XJQ)%XJQ);
}
