正題

題目鏈接:https://ac.nowcoder.com/acm/contest/20108/B

---

題目大意

給出一個長度為$n$的序列$a$，每次

• 如果$n$是偶數(shù)，則對于所有的$i<n$令新的$a_i^{\prime }=a_i^{\prime }+a_{i+1}^{\prime }$
• 如果$n$是奇數(shù)，則對于所有的$i<n$令新的$a_i^{\prime }=a_i^{\prime }?a_{i+1}^{\prime }$

$1\le n\le 10^5,1\le a_i\le 10^9$

---

解題思路

對于一個位置它操作$k$次之后肯定可以用后面的若干個數(shù)表示，設(shè)多項式$f_k(x)={\sum }_{i=0}^{\infty }{b}_i{x}^i$有$a_p^{\prime }={\sum }_{i=0}^n{b}_i\times a_{p+i}$。

那么對于這個多項式如果$n$是奇數(shù)那么有$f_k(x)=f_{k?1}(x)\times (1+x)$，否則$f_k(x)=f_{k?1}(x)\times (1?x)$。

也就是每次$(1+x)$和$(1?x)$交替乘$n?1$次，如果$n$是奇數(shù)，那么
$$f_{n?1}(x)=((1+x)(1?x){)}^{\frac{n?1}{2}}=(1?x^2{)}^{\frac{n?1}{2}}$$
用二項式定理拆開暴力算就好了，

如果$n$是偶數(shù)就直接再乘個$1+x$就好了。

時間復(fù)雜度：$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,P=1e9+7; ll n,ans,fac[N],inv[N],f[N]; ll C(ll n,ll m) {return fac[n]*inv[m]%P*inv[n-m]%P;} signed main() {scanf("%lld",&n);n--;inv[0]=inv[1]=fac[0]=1;for(ll i=2;i<=n;i++)inv[i]=P-(P/i)*inv[P%i]%P;for(ll i=1;i<=n;i++)inv[i]=inv[i-1]*inv[i]%P,fac[i]=fac[i-1]*i%P;for(ll i=0;i<=n/2;i++)f[i*2]=(i&1)?(P-C(n/2,i)):(C(n/2,i));if(n&1){for(ll i=n;i>=1;i--)f[i]=f[i]+f[i-1];}for(ll i=0,x;i<=n;i++)scanf("%lld",&x),(ans+=f[i]*x%P)%=P;printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021牛客OI赛前集训营-交替【生成函数】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。