簡單的數據結構題

首先考慮計算要求的式子，不妨設$l=1,r=n$。

${\sum }_{i=1}^n{a}_i^k{\prod }_{j=i}\frac{1?a_i{a}_j}{a_i?a_j}$

$={\sum }_{i=1}^n{a}_i^k{\prod }_{j=i}\frac{1}{a_i?a_j}{\prod }_{j=i}(1?a_i{a}_j)$

$={\sum }_{i=1}^n{a}_i^k{\prod }_{j=i}\frac{1}{a_i?a_j}{\sum }_{l=0}^{n?1}[x^{n?1?l}]{\prod }_{j=i}(x?a_i{a}_j)$

$={\sum }_{i=1}^n{a}_i^k{\prod }_{j=i}\frac{1}{a_i?a_j}{\sum }_{l=0}^{n?1}{a}_i^l[x^{n?1?l}]{\prod }_{j=i}(x?a_j)$

$={\sum }_{l=0}^{n?1}{\sum }_{i=1}^n{a}_i^{k+l}{\prod }_{j=i}\frac{1}{a_i?a_j}[x^{n?1?l}]{\prod }_{j=i}(x?a_j)$

$={\sum }_{l=0}^{n?1}{\sum }_{i=1}^n[x^{n?1?l}](a_i^{k+l}{\prod }_{j=i}\frac{1}{a_i?a_j})x^0{\prod }_{j=i}(x?a_j)$

$={\sum }_{l=0}^{n?1}{\sum }_{i=1}^n[x^{n?1?l}]a_i^{k+l}{\prod }_{j=i}\frac{x?a_j}{a_i?a_j}$

$={\sum }_{l=0}^{n?1}[x^{n?1?l}]{\sum }_{i=1}^n{a}_i^{k+l}{\prod }_{j=i}\frac{x?a_j}{a_i?a_j}$

---

根據拉格朗日插值：

$f(x)$是一個過點$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)的函數$

記$M={\prod }_{i=1}^n(x?x_i)$，則

$f(x)\equiv {\sum }_{i=1}^n{y}_i{\prod }_{j=i}\frac{x?x_j}{x_i?x_j}(modM)$

---

函數$f(x)=x^{k+l}$過點$(a_1,a_1^{k+l}),(a_2,a_2^{k+l}),...,(a_n,a_n^{k+l})$

$\therefore x^{k+l}\equiv {\sum }_{i=1}^n{a}_i^{k+l}{\prod }_{j=i}\frac{x?a_j}{a_i?a_j}(mod(x?a_1)(x?a_2)...(x?a_n))$

$\therefore 原式={\sum }_{l=0}^{n?1}[x^{n?1?l}](x^{k+l}\mathrm{m}\mathrm{o}\mathrm{d}(x?a_1)(x?a_2)...(x?a_n))$

---

注意到$0\le k\le 2$，且$l\le n?1$，所以$k+l\ge n$的情況不多，分類討論即可：

1.若$k+l\le n?1$（$x^{k+l}$的次數低于$mod$的多項式）：

$原式={\sum }_{l=1}^{n?1}[x^{n?1?l}]x^{k+l}={\sum }_{l=1}^{n?1}[n?1?l=k+l]$

解得$l=\frac{n?k?1}{2}$

則當$n?k?1\equiv 0(mod2)$且$0\le n?k?1$時原式為1，否則為0，
即當$n?k?1\equiv 1(mod2)$或$n=1,k=2$時原式為0，否則為1

2.若$k+l\ge n$：

$\because l\le n?1$ $\therefore k\ge 1$

2.1若$k=1$：

此時有$l=n?1$

$原式=[x^0](x^n\mathrm{m}\mathrm{o}\mathrm{d}(x?a_1)(x?a_2)...(x?a_n))$
$=[x^0](x^n?(x?a_1)(x?a_2)...(x?a_n))$
$=(?1{)}^{n+1}{a}_1{a}_2...a_n$

2.2若$k=2$：

此時有$l=n?2或l=n?1$

2.2.1若 $l=n?2$：

$\because l\ge 0$ $\therefore n=1$

$原式=[x^1](x^n\mathrm{m}\mathrm{o}\mathrm{d}(x?a_1)(x?a_2)...(x?a_n))$
$=[x^1](x^n?(x?a_1)(x?a_2)...(x?a_n))$
$=(?1{)}^n{\sum }_{i=1}^n{\prod }_{j=i}{a}_j$

2.2.2若 $l=n?1$：

$原式=[x^0](x^{n+1}\mathrm{m}\mathrm{o}\mathrm{d}(x?a_1)(x?a_2)...(x?a_n))$
$=[x^0](x^{n+1}?\begin{array}{c}(x+a_1+a_2+...+a_n)\\ 大除法得出\end{array}(x?a_1)(x?a_2)...(x?a_n))$
$=(?1{)}^{n+1}{\sum }_{i=1}^n{a}_i{\prod }_{j=1}^n{a}_j$

當$n=1,k=2$時，兩處的特判可以相互抵消，于是可以不需要特判。

于是只要維護${\sum }_{i=1}^n{a}_i$ ，${\prod }_{i=1}^n{a}_i$ ，${\sum }_{i=1}^n{\prod }_{j=i}{a}_j$，在區間乘的操作下用線段樹解決

#include<iostream> #include<cstdio> using namespace std; const int mod=998244353; const int N=300010; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } struct Node{int sum,pro,ans;Node(){sum=0;pro=1;ans=0;}Node(int a,int b,int c){sum=a,pro=b,ans=c;} }t[N<<2]; int n,m,a[N],laz[N<<2]; int add(int a,int b){return a+b>=mod?a+b-mod:a+b;} int dec(int a,int b){return a-b<0?a-b+mod:a-b;} int mul(int a,int b){return 1ll*a*b%mod;} int power(int a,int b){int res=1;while(b){if(b&1) res=mul(res,a);a=mul(a,a);b>>=1;}return res; } Node merge(Node a,Node b){Node c;c.sum=add(a.sum,b.sum);c.pro=mul(a.pro,b.pro);c.ans=add(mul(a.ans,b.pro),mul(a.pro,b.ans));return c; } void pushup(int u){t[u]=merge(t[u<<1],t[u<<1|1]); } void build(int u,int l,int r){laz[u]=1;if(l==r){t[u]=Node(a[l],a[l],1);return;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u); } void modify(int u,int l,int r,int x){t[u].sum=mul(t[u].sum,x);t[u].pro=mul(t[u].pro,power(x,r-l+1));t[u].ans=mul(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=(l+r)>>1;modify(u<<1,l,mid,laz[u]);modify(u<<1|1,mid+1,r,laz[u]);laz[u]=1;} } void update(int u,int l,int r,int a,int b,int x){if(a<=l&&r<=b){modify(u,l,r,x);return;}pushdown(u,l,r);int mid=(l+r)>>1;if(a<=mid) update(u<<1,l,mid,a,b,x);if(b>mid) update(u<<1|1,mid+1,r,a,b,x);pushup(u); } Node query(int u,int l,int r,int a,int b){if(a<=l&&r<=b) return t[u];pushdown(u,l,r);int mid=(l+r)>>1;Node res=Node(0,1,0);if(a<=mid) res=merge(res,query(u<<1,l,mid,a,b));if(b>mid) res=merge(res,query(u<<1|1,mid+1,r,a,b));return res; } int main(){n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);int opt,l,r,k;while(m--){opt=read();l=read();r=read();k=read();if(opt==1)update(1,1,n,l,r,k);else{int d=r-l+1,ans=0;if(!((d-k-1)&1)) ans++;Node now=query(1,1,n,l,r);if(k==1){if(d&1) ans=add(ans,now.pro);else ans=dec(ans,now.pro);}if(k==2){if(!(d&1)) ans=add(ans,now.ans);else ans=dec(ans,now.ans);if(d&1) ans=add(ans,mul(now.sum,now.pro));else ans=dec(ans,mul(now.sum,now.pro));}printf("%d\n",ans);}}return 0; }

總結

以上是生活随笔為你收集整理的简单的数据结构题（多项式、拉格朗日插值、线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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