网站维护的协议,泉州自助建站,响应式学校网站模板下载,上海网站建设网站制简单的数据结构题
首先考虑计算要求的式子#xff0c;不妨设l1,rnl1,rnl1,rn。 ∑i1naik∏j̸i1−aiajai−aj\sum_{i1}^{n}a_i^k\prod_{j\noti}\frac{1-a_ia_j}{a_i-a_j}∑i1naik∏jiai−aj1−aiaj ∑i1naik∏j̸i1ai−aj∏j̸i(1−aiaj)\sum_{i1}^{n}a_…简单的数据结构题
首先考虑计算要求的式子不妨设l1,rnl1,rnl1,rn。
∑i1naik∏j̸i1−aiajai−aj\sum_{i1}^{n}a_i^k\prod_{j\noti}\frac{1-a_ia_j}{a_i-a_j}∑i1naik∏jiai−aj1−aiaj
∑i1naik∏j̸i1ai−aj∏j̸i(1−aiaj)\sum_{i1}^{n}a_i^k\prod_{j\noti}\frac{1}{a_i-a_j}\prod_{j\noti}(1-a_ia_j)∑i1naik∏jiai−aj1∏ji(1−aiaj)
∑i1naik∏j̸i1ai−aj∑l0n−1[xn−1−l]∏j̸i(x−aiaj)\sum_{i1}^{n}a_i^k\prod_{j\noti}\frac{1}{a_i-a_j}\sum_{l0}^{n-1}[x^{n-1-l}]\prod_{j\noti}(x-a_ia_j)∑i1naik∏jiai−aj1∑l0n−1[xn−1−l]∏ji(x−aiaj)
∑i1naik∏j̸i1ai−aj∑l0n−1ail[xn−1−l]∏j̸i(x−aj)\sum_{i1}^{n}a_i^k\prod_{j\noti}\frac{1}{a_i-a_j}\sum_{l0}^{n-1}a_i^l[x^{n-1-l}]\prod_{j\noti}(x-a_j)∑i1naik∏jiai−aj1∑l0n−1ail[xn−1−l]∏ji(x−aj)
∑l0n−1∑i1naikl∏j̸i1ai−aj[xn−1−l]∏j̸i(x−aj)\sum_{l0}^{n-1}\sum_{i1}^{n}a_i^{kl}\prod_{j\noti}\frac{1}{a_i-a_j}[x^{n-1-l}]\prod_{j\noti}(x-a_j)∑l0n−1∑i1naikl∏jiai−aj1[xn−1−l]∏ji(x−aj)
∑l0n−1∑i1n[xn−1−l](aikl∏j̸i1ai−aj)x0∏j̸i(x−aj)\sum_{l0}^{n-1}\sum_{i1}^{n}[x^{n-1-l}](a_i^{kl}\prod_{j\noti}\frac{1}{a_i-a_j})x^0\prod_{j\noti}(x-a_j)∑l0n−1∑i1n[xn−1−l](aikl∏jiai−aj1)x0∏ji(x−aj)
∑l0n−1∑i1n[xn−1−l]aikl∏j̸ix−ajai−aj\sum_{l0}^{n-1}\sum_{i1}^{n}[x^{n-1-l}]a_i^{kl}\prod_{j\noti}\frac{x-a_j}{a_i-a_j}∑l0n−1∑i1n[xn−1−l]aikl∏jiai−ajx−aj
∑l0n−1[xn−1−l]∑i1naikl∏j̸ix−ajai−aj\sum_{l0}^{n-1}[x^{n-1-l}]\sum_{i1}^{n}a_i^{kl}\prod_{j\noti}\frac{x-a_j}{a_i-a_j}∑l0n−1[xn−1−l]∑i1naikl∏jiai−ajx−aj 根据拉格朗日插值
f(x)f(x)f(x)是一个过点(x1,y1),(x2,y2),...,(xn,yn)的函数(x_1,y_1),(x_2,y_2),...,(x_n,y_n)的函数(x1,y1),(x2,y2),...,(xn,yn)的函数
记M∏i1n(x−xi)M\prod_{i1}^{n}(x-x_i)M∏i1n(x−xi)则
f(x)≡∑i1nyi∏j̸ix−xjxi−xj(modM)f(x)\equiv \sum_{i1}^{n}y_i\prod_{j\noti}\frac{x-x_j}{x_i-x_j}(mod\space M)f(x)≡∑i1nyi∏jixi−xjx−xj(mod M) 函数f(x)xklf(x)x^{kl}f(x)xkl过点(a1,a1kl),(a2,a2kl),...,(an,ankl)(a_1,a_1^{kl}),(a_2,a_2^{kl}),...,(a_n,a_n^{kl})(a1,a1kl),(a2,a2kl),...,(an,ankl)
∴xkl≡∑i1naikl∏j̸ix−ajai−aj(mod(x−a1)(x−a2)...(x−an))\therefore x^{kl}\equiv\sum_{i1}^{n}a_i^{kl}\prod_{j\noti}\frac{x-a_j}{a_i-a_j}(mod\space(x-a_1)(x-a_2)...(x-a_n))∴xkl≡∑i1naikl∏jiai−ajx−aj(mod (x−a1)(x−a2)...(x−an))
∴原式∑l0n−1[xn−1−l](xklmod(x−a1)(x−a2)...(x−an))\therefore原式\sum_{l0}^{n-1}[x^{n-1-l}](x^{kl}\mod(x-a_1)(x-a_2)...(x-a_n))∴原式∑l0n−1[xn−1−l](xklmod(x−a1)(x−a2)...(x−an)) 注意到0≤k≤20\leq k\leq20≤k≤2且l≤n−1l\leq n-1l≤n−1所以kl≥nkl\geq nkl≥n的情况不多分类讨论即可
1.若kl≤n−1kl\leq n-1kl≤n−1xklx^{kl}xkl的次数低于modmodmod的多项式
原式∑l1n−1[xn−1−l]xkl∑l1n−1[n−1−lkl]原式\sum_{l1}^{n-1}[x^{n-1-l}]x^{kl}\sum_{l1}^{n-1}[n-1-lkl]原式∑l1n−1[xn−1−l]xkl∑l1n−1[n−1−lkl]
解得ln−k−12l\frac{n-k-1}{2}l2n−k−1
则当n−k−1≡0(mod2)n-k-1\equiv 0(mod\space 2)n−k−1≡0(mod 2)且0≤n−k−10\leq n-k-10≤n−k−1时原式为1否则为0 即当n−k−1≡1(mod2)n-k-1\equiv1(mod\space 2)n−k−1≡1(mod 2)或n1,k2n1,k2n1,k2时原式为0否则为1
2.若kl≥nkl\geq nkl≥n
∵l≤n−1\because l\leq n-1∵l≤n−1 ∴k≥1\therefore k\geq1∴k≥1
2.1若k1k1k1
此时有ln−1ln-1ln−1
原式[x0](xnmod(x−a1)(x−a2)...(x−an))原式[x^0](x^n\mod(x-a_1)(x-a_2)...(x-a_n))原式[x0](xnmod(x−a1)(x−a2)...(x−an)) [x0](xn−(x−a1)(x−a2)...(x−an))[x^0](x^n-(x-a_1)(x-a_2)...(x-a_n))[x0](xn−(x−a1)(x−a2)...(x−an)) (−1)n1a1a2...an(-1)^{n1}a_1a_2...a_n(−1)n1a1a2...an
2.2若k2k2k2
此时有ln−2或ln−1ln-2或ln-1ln−2或ln−1
2.2.1若 ln−2ln-2ln−2
∵l≥0\because l\geq0∵l≥0 ∴n̸1\therefore n\not1∴n1
原式[x1](xnmod(x−a1)(x−a2)...(x−an))原式[x^1](x^n\mod(x-a_1)(x-a_2)...(x-a_n))原式[x1](xnmod(x−a1)(x−a2)...(x−an)) [x1](xn−(x−a1)(x−a2)...(x−an))[x^1](x^n-(x-a_1)(x-a_2)...(x-a_n))[x1](xn−(x−a1)(x−a2)...(x−an)) (−1)n∑i1n∏j̸iaj(-1)^n\sum_{i1}^{n}\prod_{j\noti}a_j(−1)n∑i1n∏jiaj
2.2.2若 ln−1ln-1ln−1
原式[x0](xn1mod(x−a1)(x−a2)...(x−an))原式[x^0](x^{n1}\mod(x-a_1)(x-a_2)...(x-a_n))原式[x0](xn1mod(x−a1)(x−a2)...(x−an)) [x0](xn1−(xa1a2...an)⏟大除法得出(x−a1)(x−a2)...(x−an))[x^0](x^{n1}-\begin{matrix}\underbrace{(xa_1a_2...a_n)}\\大除法得出\end{matrix}(x-a_1)(x-a_2)...(x-a_n))[x0](xn1−(xa1a2...an)大除法得出(x−a1)(x−a2)...(x−an)) (−1)n1∑i1nai∏j1naj(-1)^{n1}\sum_{i1}^{n}a_i\prod_{j1}^{n}a_j(−1)n1∑i1nai∏j1naj
当n1,k2n1,k2n1,k2时两处的特判可以相互抵消于是可以不需要特判。
于是只要维护∑i1nai\sum_{i1}^{n}a_i∑i1nai ∏i1nai\prod_{i1}^{n}a_i∏i1nai ∑i1n∏j̸iaj\sum_{i1}^{n}\prod_{j\noti}a_j∑i1n∏jiaj在区间乘的操作下用线段树解决
#includeiostream
#includecstdio
using namespace std;
const int mod998244353;
const int N300010;
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
struct Node{int sum,pro,ans;Node(){sum0;pro1;ans0;}Node(int a,int b,int c){suma,prob,ansc;}
}t[N2];
int n,m,a[N],laz[N2];
int add(int a,int b){return abmod?ab-mod:ab;}
int dec(int a,int b){return a-b0?a-bmod:a-b;}
int mul(int a,int b){return 1ll*a*b%mod;}
int power(int a,int b){int res1;while(b){if(b1) resmul(res,a);amul(a,a);b1;}return res;
}
Node merge(Node a,Node b){Node c;c.sumadd(a.sum,b.sum);c.promul(a.pro,b.pro);c.ansadd(mul(a.ans,b.pro),mul(a.pro,b.ans));return c;
}
void pushup(int u){t[u]merge(t[u1],t[u1|1]);
}
void build(int u,int l,int r){laz[u]1;if(lr){t[u]Node(a[l],a[l],1);return;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);
}
void modify(int u,int l,int r,int x){t[u].summul(t[u].sum,x);t[u].promul(t[u].pro,power(x,r-l1));t[u].ansmul(t[u].ans,power(x,r-l));laz[u]mul(laz[u],x);
}
void pushdown(int u,int l,int r){if(laz[u]!1){int mid(lr)1;modify(u1,l,mid,laz[u]);modify(u1|1,mid1,r,laz[u]);laz[u]1;}
}
void update(int u,int l,int r,int a,int b,int x){if(alrb){modify(u,l,r,x);return;}pushdown(u,l,r);int mid(lr)1;if(amid) update(u1,l,mid,a,b,x);if(bmid) update(u1|1,mid1,r,a,b,x);pushup(u);
}
Node query(int u,int l,int r,int a,int b){if(alrb) return t[u];pushdown(u,l,r);int mid(lr)1;Node resNode(0,1,0);if(amid) resmerge(res,query(u1,l,mid,a,b));if(bmid) resmerge(res,query(u1|1,mid1,r,a,b));return res;
}
int main(){nread();mread();for(int i1;in;i) a[i]read();build(1,1,n);int opt,l,r,k;while(m--){optread();lread();rread();kread();if(opt1)update(1,1,n,l,r,k);else{int dr-l1,ans0;if(!((d-k-1)1)) ans;Node nowquery(1,1,n,l,r);if(k1){if(d1) ansadd(ans,now.pro);else ansdec(ans,now.pro);}if(k2){if(!(d1)) ansadd(ans,now.ans);else ansdec(ans,now.ans);if(d1) ansadd(ans,mul(now.sum,now.pro));else ansdec(ans,mul(now.sum,now.pro));}printf(%d\n,ans);}}return 0;
}
