前缀和专题(C学完多项式后补代码

前言: 之前对前缀和的了解仅仅局限与一维前缀和、二维前缀和以及前缀和的变形如前缀积、前缀异或。经过zngg的讲解后，才发现我对前缀和的了解远远不够。很喜欢智乃上课讲过的一句话：“不能把前缀和仅仅看作是前缀和，而是看成一种思想。”

OI Wiki对于前缀和的详解：https://oi-wiki.org/basic/prefix-sum/

upd: 图片说明

A 智乃酱的区间乘积

这是一题很裸的前缀积的题，没有做过前缀积的可以通过前缀和也能联想过来
ps:注意因为取模的原因不能使用除法，因此需要使用乘法逆元

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48511064

ll a[N],s[N];

ll fpow(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

void solve(){
    int n,m;cin>>n>>m;
    s[0]=1;
    rep(i,1,n) cin>>a[i],s[i]=s[i-1]*a[i]%mod;
    while(m--){
        int l,r;cin>>l>>r;
        cout<<s[r]*fpow(s[l-1],mod-2)%mod<<"\n";
    }
}

B 智乃酱的子集与超集

这题需要掌握高维前缀和(SOSDP)的知识

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48582573

ll a[N];
ll f[1<<N];//f[i]:选择集合为i的二进制(0不选 1选)的价值
ll sum1[1<<N],sum2[1<<N];//sum1子集前缀和 sum2超集前缀和

void solve(){
    int n,m;cin>>n>>m;
    rep(i,0,n-1) cin>>a[i];

    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i>>j&1) f[i]^=a[j];
        }
        sum1[i]=sum2[i]=f[i];
    }

    for(int j=0;j<n;j++){
        for(int i=0;i<(1<<n);i++){
            if(i>>j&1) sum1[i]+=sum1[i^(1<<j)];
            else sum2[i]+=sum2[i^(1<<j)];
        }
    }

    while(m--){
        int k;cin>>k;
        ll s=0;//选中的集合
        while(k--){
            int x;cin>>x;x--;
            s|=(1<<x);
        }
        cout<<sum1[s]<<" "<<sum2[s]<<"\n";
    }
}

C 智乃酱的前缀和与差分

这题求高阶差分与高阶前缀和
前置芝士：多项式
 论生成函数对序列高阶差分与高阶前缀和求解的优化

D 智乃酱的静态数组维护问题多项式

性质1:若 $f\left( x \right)$ 为n次多项式，则 $\Delta ^{n+1}f(x)=0$
性质2:n次多项式的n+1阶差分余项只有n+1项

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48611818

int n,m,q;
ll a[N],c[10],d1[10],d2[10];

//前缀和
void S(ll a[],int n,int cnt){
    while(cnt--){
        for(int i=1;i<=n;i++) (a[i]+=a[i-1])%=mod;
    }
}

//差分
void D(ll a[],int n,int cnt){
    while(cnt--){
        for(int i=n;i>=1;i--) (a[i]+=mod-a[i-1])%=mod;
    } 
}

//多项式函数f(x) a[]为系数
ll f(ll x,ll a[],int k){
    ll ans=0,base=1;
    for(int i=k;i>=0;i--){
        (ans+=base*a[i]%mod)%=mod;
        (base*=x)%=mod;
    }
    return ans;
}


void solve(){
    cin>>n>>m>>q;
    rep(i,1,n) cin>>a[i];
    D(a,n,6);//性质1
    while(m--){
        int l,r,k;cin>>l>>r>>k;
        rep(i,0,k) cin>>c[i];
        rep(i,1,6){//性质2
            d1[i]=f(i,c,k);  //a[l]+=d1[i];
            d2[i]=f(i+r-l+1,c,k); //a[r+1]-=d2[i];
        }
        D(d1,6,6);D(d2,6,6);
        rep(i,1,6){
            (a[l+i-1]+=d1[i])%=mod;
            (a[r+i]+=mod-d2[i])%=mod;
        }
    }

    S(a,n,7);
    while(q--){
        int l,r;cin>>l>>r;
        cout<<(a[r]-a[l-1]+mod)%mod<<"\n";
    }
}

E 智乃酱的双塔问题

前置芝士：矩阵求逆
这题就是一种特殊的前缀思想——前缀矩阵积

dp[i][0]表示走到左塔的第i层的方案数
dp[i][1]表示走到右塔的第i层的方案数

dp[i][0] = dp[i-1][0] + "右塔的i-1层到左塔的第i层存在梯子"?dp[i-1][1]:0;
dp[i][1] = dp[i-1][1] + "左塔的i-1层到第i层的右塔存在梯子"?dp[i-1][0]:0;

根据上面两个dp转移方程推出下面的两个矩阵形式

/的情况:

$\left[ \begin{matrix} dp_{i,0} & dp_{i,1} \end{matrix} \right]= \left[ \begin{matrix} dp_{i-1,0} & dp_{i-1,1} \end{matrix} \right] * \left[ \begin{matrix} 1&1\\0&1 \end{matrix} \right]$

\的情况:

$\left[ \begin{matrix} dp_{i,0} & dp_{i,1} \end{matrix} \right]= \left[ \begin{matrix} dp_{i-1,0} & dp_{i-1,1} \end{matrix} \right] * \left[ \begin{matrix} 1&0\\1&1 \end{matrix} \right]$

这样就可以把后面的矩阵叠加起来，利用前缀矩阵积快速求解

问题：对于最后是Mat ans=b*sum[ht-1];而不是Mat ans=sum[ht-1]*b;的理解
假设 $A*B$ 要把前边前面的 $A$ 消去，只能 $A^{-1}*A*B$ ，所以要把矩阵逆元放在前边

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48600890

struct Mat{
    int n;
    vector<vector<ll>> mat;

    Mat() {}

    Mat(int _n) {
        n = _n;
        mat.resize(n + 1, vector<ll>(n + 1, 0));
    }

    vector<ll>& operator[](int x) {
        return mat[x];
    }

    void identify() {
        for (int i = 1; i <= n; i++) {
            mat[i][i] = 1;
        }
    }

    void print(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cout<<mat[i][j]<<" \n"[j==n];
    }

    //交换某两行
    void SWAP(int x,int y){
        for(int i=1;i<=n;i++) swap(mat[x][i],mat[y][i]);
    }

    //将某一行的所有元素乘上k加到另一行去
    void add(int i, int j, ll val) {
        for (int k = 1; k <= n; k++) {
            mat[i][k] = (mat[i][k] + mat[j][k] * val % mod + mod) % mod;
        }
    }

    //将某一行的所有元素乘上k
    void multiply(int i, ll val) {
        for (int j = 1; j <= n; j++) {
            mat[i][j] = (mat[i][j] * val % mod + mod) % mod;
        }
    }
};

Mat operator * (Mat x, Mat y){
    Mat z(x.n);
    for (int i = 1; i <=x.n; i++) {
        for (int j = 1; j <= y.n; j++) {
            for (int k = 1; k <= x.n; k++) {
                z[i][j] = (z[i][j] + x[i][k] * y[k][j] % mod) % mod;
            }
        }
    }
    return z;
}

ll fpow(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

Mat sum[N],A,B;

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;s=" "+s;
    sum[0]=Mat(2);
    sum[0].mat[1][1]=sum[0].mat[2][2]=1;
    // s[0].print();
    A=Mat(2);
    A.mat[1][1]=A.mat[1][2]=A.mat[2][2]=1;
    // A.print();
    B=Mat(2);
    B.mat[1][1]=B.mat[2][1]=B.mat[2][2]=1;
    // B.print();
    for(int i=1;i<n;i++){
        if(s[i]=='/') sum[i]=sum[i-1]*A;
        else sum[i]=sum[i-1]*B;
        // sum[i].print();
    }


    n=2;
    while(m--){
        int hs,ht,ps,pt;cin>>hs>>ht>>ps>>pt;
        Mat a=sum[hs-1];
        // a.print();
        Mat b(n);
        b.identify();
        // b.print();
        auto gauss = [&]() -> bool {
            for (int i = 1; i <= n; i++) {
                if (!a[i][i]) {
                    for (int j = i + 1; j <= n; j++) {
                        if (a[j][i]) {
                            a.SWAP(i,j);
                            b.SWAP(i,j);
                            break;
                        }
                    }
                }
                if (!a[i][i]) {
                    return 0;
                }
                ll inv = fpow(a[i][i], mod - 2);
                a.multiply(i, inv);
                b.multiply(i, inv);
                for (int j = i + 1; j <= n; j++) {
                    b.add(j, i, -a[j][i]);
                    a.add(j, i, -a[j][i]);
                }
            }
            for (int i = n - 1; i >= 1; i--) {
                for (int j = i + 1; j <= n; j++) {
                    b.add(i, j, -a[i][j]);
                    a.add(i, j, -a[i][j]);
                }
            }
            return 1;
        };

        gauss();

        // sum[ht-1].print();
        // b.print();

        Mat ans=b*sum[ht-1];
        // ans.print();
        cout<<ans[ps+1][pt+1]<<"\n";
    }
}

F 牛牛的猜球游戏

这题就是一种特殊的前缀思想——前缀置换
如果不仔细思考的话刚开始很容易被误以为是线段树维护矩阵乘
下面引用zngg的官方题解：
https://ac.nowcoder.com/discuss/542124?type=101&order=0&pos=1&page=1&source_id=discuss_tag_nctrack&channel=-1

对于前缀和，如果仅将其理解成一段区间的数字求和。这个理解是远不够深入的。实际上除了前缀和，前缀亦或和，乃至前缀积。
可以把前缀和算法抽象成，如果可以储存和查询某种前缀的影响，并且能够快速消除前缀影响，那么就可以知道任意区间的影响。
如果这样去理解，那么主席树就是对于修改操作影响的“前缀和”，带修的主席树不过是用树状数组维护“前缀和”罢了。
对于本题，显然可以用一个二维数组存储每一步交换的“前缀影响”。
然后想怎么去消除“前缀影响”。
这部分画个图来讲一下，首先简化一下问题，假设只有3个球，进行了3次连续操作，交换0,1，交换1,2，交换0,1。

假设现在要消除前2次的影响，可以在初始状态上做手脚。
也就是一开始球不是0∼9按顺序排列好的，而是某种顺序。
这种顺序在进行完前2次换球之后恰好变成了0∼9按照顺序排列。
为了求出能够抵消前2次顺序，最暴力最笨的方法是倒着爬回去。
那么不管怎么，现在起码有了O(n^2)预处理，O(1)查询的算法了。
然后继续优化，我们想，其实没必要每次都一步一步爬，可以用路径压缩的思路，只保留从初始状态到当前操作时球被换到哪里就可以了。

根据这个“从初始状态到当前操作时球被换到哪里”的定义，发现这不就是前缀和么。
在算法实现上分为两步
1、先求出能够抵消前l-1次操作影响的初始序列
2、在该初始序列下进行前r次换球操作的前缀影响。
std进行了一些封装和重载，这样算法的前缀和部分看的更清楚。
std: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45244205

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48518819

int f[N][10];//f[i][j]:第i轮第j号球的下标
int a[N];

void solve(){
    int n,m;cin>>n>>m;
    rep(j,0,9) f[0][j]=j;
    rep(i,1,n){
        rep(j,0,9) f[i][j]=f[i-1][j];
        int l,r;cin>>l>>r;
        swap(f[i][l],f[i][r]);
    }
    while(m--){
        int l,r;cin>>l>>r;
        rep(j,0,9) a[f[l-1][j]]=j;
        rep(j,0,9) cout<<a[f[r][j]]<<" \n"[j==9];
    }
}

G 牛牛的Link Power I

这道题很直接能想到的就是O(n^2)的遍历每个link点，但是1e5的数据量是会TLE的
仔细考虑一下之前有很多地方已经重复计算

第i个1产生的能量是第i-1个1产生的能量加上dis(i-1,i)*i之前1的个数
求一边前缀和即可
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48518643

void solve(){
    int n;cin>>n;
    string s;cin>>s;s=" "+s;
    ll cnt=0,pre=0;
    ll res=0;
    vector<ll> ans(n+1);
    for(int i=1;i<=n;i++){
        ans[i]=ans[i-1];
        if(s[i]=='1'){
            ans[i]+=(i-pre)*cnt%mod;ans[i]%=mod;
            pre=i,cnt++;
            res+=ans[i];res%=mod;
        }
        // debug(ans[i]);
    }
    cout<<res<<"\n";
}

H 小w的糖果

这题考察的是差分

如果让区间进行加减某个常数这很容易使用差分实现
d[l]++,d[r+1]--;
然后使用前缀和复原即可

然而这么扩展到在某个区间加减一次函数、二次函数呢
https://blog.csdn.net/weixin_43571920/article/details/93328006
这篇blog说的很详细

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48518716

void solve(){
    int n,m;cin>>n>>m;
    vector<ll> a(n+5),b(n+5),c(n+5);
    while(m--){
        int op,l;cin>>op>>l;
        if(op==1) a[l]++;  //+1
        else if(op==2) b[l]++;  //+x
        else c[l]++,c[l+1]++;  //+x^2
    }

    for(int i=1;i<=n;i++){
        c[i]=(c[i-1]+c[i])%mod;
    }

    for(int i=1;i<=n;i++){
        b[i]=(b[i-1]+b[i])%mod;
        c[i]=(c[i-1]+c[i])%mod;
    }

    for(int i=1;i<=n;i++){
        a[i]=(a[i-1]+a[i])%mod;
        b[i]=(b[i-1]+b[i])%mod;
        c[i]=(c[i-1]+c[i])%mod;
        cout<<(a[i]+b[i]+c[i])%mod<<" \n"[i==n];
    }
}

I [NOIP2013]积木大赛

我们逆向思考：假设给定了每块积木的高度，每次可以将某一段区间中的所有高度减一，问最少操作多少次可以将所有高度变成0。
构造差分序列
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48511022

int pre,ans;

void solve(){
    int n;cin>>n;
    rep(i,1,n){
        int h;cin>>h;
        if(h>pre) ans+=h-pre;
        pre=h;
    }
    cout<<ans<<"\n";
}

J [NOIP2018]道路铺设

和上题同

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48511009

int pre,ans;

void solve(){
    int n;cin>>n;
    rep(i,1,n){
        int h;cin>>h;
        if(h>pre) ans+=h-pre;
        pre=h;
    }
    cout<<ans<<"\n";
}