【思维】单调栈+dp——2020 联想杯 G

/*
用一个递增单调栈维护b[1..i-1]
将bi更新进单调栈，栈顶第二个元素+1 到bi区间的最小值都改成bi，然后求个和就行 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 998244353
#define N 10000007

ll n,p,x,y,z,b[N],ans[N],sum[N];
ll getnxt(int i){
    return (x*ans[i]%p+b[i]*y%p+z)%p;
}

int main(){
    cin>>n>>p>>x>>y>>z>>b[1];
    ans[1]=b[1];sum[1]=b[1];
    
    stack<int>stk; 
    stk.push(1);
    for(int i=2;i<=n;i++){
        b[i]=getnxt(i-1);
        while(stk.size()>0 && b[stk.top()]>=b[i])
            stk.pop();
        int L;
        if(stk.size())L=stk.top();
        else L=0;
        stk.push(i);
        sum[i]=(sum[L]+b[i]*(i-L)%mod)%mod;
        ans[i]=(ans[i-1]+sum[i])%mod;
    }
    ll anss=0;
    for(int i=1;i<=n;i++)anss^=ans[i];
    cout<<anss<<‘\n‘;
}