训练记录番外篇（2）：2022 ICPC Gran Premio de Mexico 2da Fecha-Toy模板网

这篇具有很好参考价值的文章主要介绍了训练记录番外篇（2）：2022 ICPC Gran Premio de Mexico 2da Fecha。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2022 ICPC Gran Premio de Mexico 2da Fecha

2022.10.3
之前训得ak场，个人认为很edu。
（顺便一提，可能这个训练记录番外系列的比赛都非常edu，十分建议铜银选手单挑）

训练记录番外篇（2）：2022 ICPC Gran Premio de Mexico 2da Fecha

A. Advanced Player Setup

题意比较晦涩难懂，但是读完发现是个toposort。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m,k;
int ans;
int dis[200005],cost[200005];
int vis[200005],sz[100005];
vector<pii>p[200005];
int dp[1005],need[100005];
void topsort(int st){
    queue<int>q;
    dis[st]=1;
    q.push(st);
    while(q.size()){
        int u=q.front();q.pop();
        for(auto [v,w]:p[u]){
            if(v==1)continue;
            dis[v]=min(dis[v]+dis[u]+w,1000ll);
            sz[v]++;
            if(sz[v]==need[v]){
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==0)dis[i]=inf;
    }
}
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        p[u].push_back({v,w});
        need[v]++;
    }
    topsort(1);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=dis[i];j<=k;j++){
            (dp[j]+=dp[j-dis[i]])%=mod;
        }
    }
    for(int i=1;i<=k;i++){
        (ans+=dp[i])%=mod;
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    while (t--)
		solve();
}

B. Binahuatls Prophecy

发现能够成为答案的点非常少，爆搜出所有可以成为答案的点然后直接二分即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
vector<int>ans;
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
    for(int i=1;i<(1<<17);i++){
        int t=i,cnt=0,r=0;
        while(t){
            r=(r<<1)|(t%2);
            cnt++,t>>=1;
        }
        ans.push_back((i<<cnt)|(r));
        ans.push_back((i<<cnt-1)|(r));
    }
    sort(ans.begin(),ans.end());
}
void solve(){
    int l,r;cin>>l>>r;
    int rt=upper_bound(ans.begin(),ans.end(),r)-ans.begin();
    int lt=lower_bound(ans.begin(),ans.end(),l)-ans.begin();
    cout<<rt-lt<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    cin>>t;
    while (t--)
		solve();
}

C. Correcting School Enrollment Errors

小模拟题，锻炼码力+分类讨论能力。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m,cnt;
vector<pii>p[200005];
map<int,int>mp;
set<int>st,q[200005];
set<pii>ans[200005];
int id[200005];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int o,k;cin>>o>>k;
        if(mp.find(o)==mp.end()){
            mp[o]=++cnt;
        }
        int d=mp[o];
        for(int j=1;j<=k;j++){
            int x;cin>>x;
            q[d].insert(x);
        }
    }
    for(int i=1;i<=m;i++){
        int o,k;cin>>o>>k;
        if(mp.find(o)==mp.end()){
            mp[o]=++cnt;
        }
        int d=mp[o];
        for(int j=1;j<=k;j++){
            int x;cin>>x;
            if(q[d].find(x)==q[d].end()){
                ans[d].insert({x,-1});//需要删除的
            }
            else{
                q[d].erase(x);
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        for(auto &x:q[i]){
            ans[i].insert({x,1});//需要添加的
        }
    }
    int tot1=0,tot2=0,tot3=0;
    for(auto [x,i]:mp){
        if(ans[i].size()){
            tot1++;
            cout<<x<<" ";
            for(auto [y,z]:ans[i]){
                if(z>0){
                    cout<<"+";
                    tot3++;
                }
                else{
                    cout<<"-";
                    tot2++;
                }
                cout<<y<<" ";
            }
            cout<<endl;
        }
    }
    if(tot1==0){
        cout<<"GREAT WORK! NO MISTAKES FOUND!";
    }
    else{
        cout<<"MISTAKES IN "<<tot1<<" STUDENTS: "<<tot2<<" NOT REQUESTED, "<<tot3<<" MISSED";
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

D. District Capitalism Roads

BFS

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m;
int ans;
int dis[200005],cost[200005];
vector<pii>p[200005];
queue<int>q;
void bfs(int st){
    memset(dis,0x3f,sizeof dis);
    memset(cost,0x3f,sizeof cost);
    dis[st]=0;
    cost[st]=0;
    q.push(st);
    while(q.size()){
        int u=q.front();q.pop();
        for(auto [v,w]:p[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                cost[v]=w;
                q.push(v);
            }
            else if(dis[v]==dis[u]+1){
                cost[v]=min(cost[v],w);
            }
        }
    }
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        p[u].push_back({v,w});
        p[v].push_back({u,w});
    }
    bfs(1);
    for(int i=1;i<=n;i++){
        ans+=dis[i]*cost[i];
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

E. Express Warehouse Migration

签到

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m;
void solve(){
    cin>>n>>m;
    cout<<(n+m-1)/m;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

F. Famous Paintings

暴力。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m;
int x[105],y[105];
int dp[2000005];
int ans;
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                for(int t=k+1;t<=n;t++){
                    int dxij=x[i]-x[j],dyij=y[i]-y[j];
                    int dxjk=x[j]-x[k],dyjk=y[j]-y[k];
                    int dxkt=x[k]-x[t],dykt=y[k]-y[t];
                    int dxik=x[i]-x[k],dyik=y[i]-y[k];
                    int dxjt=x[j]-x[t],dyjt=y[j]-y[t];

                    if(dxij*dyjk-dxjk*dyij==0||
                       dxik*dykt-dxkt*dyik==0||
                       dxjk*dykt-dxkt*dyjk==0||
                       dxij*dyjt-dxjt*dyij==0  )
                       ans--;
                }
            }
        }
    }
    cout<<ans+n*(n-1)*(n-2)*(n-3)/24;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

G. Guadalajara trains

有点久远记不太清了，好像是前缀和。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m;
int a[1000005];
int d[1000005];
int lx[1000005],rx[1000005],ly[1000005],ry[1000005];
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>d[i];
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        lx[i]=rx[i-1]+d[i-1];
        rx[i]=lx[i]+a[i];
    }
    for(int i=n;i;i--){
        ly[i]=ry[i+1]+d[i];
        ry[i]=ly[i]+a[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=max(0ll,min(rx[i],ry[i])-max(lx[i],ly[i]));
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

H. How Many Laughs

容斥。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m,x;
int a[2000005];
int d[1000005];
int lx[1000005],rx[1000005],ly[1000005],ry[1000005];
int dp[2000005];
int ans;
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[1<<i];
    }
    for(int i=1;i<(1<<n);i++){
        int x=lowbit(i);
        if(i!=x){
            int d=__gcd(a[x],a[i-x]);
            a[i]=min(mod,a[x]*a[i-x]/d);
        }
        dp[i]=m/a[i];
    }
    for(int i=1;i<(1<<n);i++){
        if(__builtin_popcount(i)%2){
            ans+=dp[i];
        }
        else{
            ans-=dp[i];
        }
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

I. Inversion Counting

根号分治。注意分治的大小应该选为 $\frac{n} {\sqrt q}$ （同莫队）,这样复杂度是严格的 $\sqrt q)$ 。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,k,q,d=60,ans,cnt;
int a[100005],tr[100005],big[100005],sum[100005];
int id[100005];
vector<int>pos[100005],dp[100005],bigpos;
void add(int x,int k){for(;x<=n;x+=lowbit(x))tr[x]+=k;}
int qry(int x,int res=0){for(;x;x-=lowbit(x))res+=tr[x];return res;}
void update(int x,int y){
    if(!pos[x].size()||!pos[y].size())return;
    if(big[y]){//x->y==dp[x][big[y]],y->x==pos[x].size()*pos[y].size()-
        ans+=pos[x].size()*pos[y].size()-2*dp[x][big[y]];
        return;
    }
    if(big[x]){
        ans-=pos[x].size()*pos[y].size()-2*dp[y][big[x]];
        return;
    }
    for(int l=0,r=0,n=pos[x].size(),m=pos[y].size();l<n;){
        if(r==m||pos[x][l]<pos[y][r]){ans+=m-2*r;l++;}
        else{r++;}
    }
}
void solve(){
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
        add(a[i],1);
        ans+=i-qry(a[i]);
    }
    for(int i=1;i<=k;i++){
        id[i]=i;
        if(pos[i].size()>=d){
            big[i]=++cnt;
            bigpos.push_back(i);
        }
    }
    for(int i=1;i<=k;i++){
        if(pos[i].size()){
            dp[i].resize(cnt+1);
        }
    }
    for(int i=1;i<=n;i++){
        int x=a[i];
        for(auto &y:bigpos){//计算y->x数量
            dp[x][big[y]]+=sum[y];
        }
        sum[x]++;
    }
    while(q--){
        int x;cin>>x;
        update(id[x],id[x+1]);
        swap(id[x],id[x+1]);
        cout<<ans<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

J. Joining the KAK

爆搜

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,k,anslen,len,nowk;
string s;
char ans[1005];
int cnt[200];
void dfs(int now){
    for(int i='a';i<='z';i++){
        if(cnt[i]){
            ans[now]=i;
            nowk++;
            cnt[i]--;
            anslen=now;
            if(nowk==k)return;
            dfs(now+1);
            if(nowk==k)return;
            cnt[i]++;
        }
    }
}
queue<string>q;
int nowct[200];
string bfs(){
    q.push("");
    while(q.size()){
        auto s=q.front();q.pop();
        for(int i='a';i<='z';i++)nowct[i]=0;
        for(auto x:s)nowct[x]++;
        for(int i='a';i<='z';i++){
            if(nowct[i]<cnt[i]){
                nowk++;
                string t=s+(char)i;
                if(nowk==k)return t;
                q.push(t);
            }
        }
    }
}
void solve(){
    cin>>n>>k>>s;
    for(auto x:s){
        cnt[x]++;
    }
    cout<<bfs();
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}

K. Krystalova’s Trivial Problem

线段树维护平方和。

#include <bits/stdc++.h>
#define int long long 
#define endl '\n'
#define mid ((l+r)/2)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
const int inf=1e18,mod=1000000007;
const string yes="YES\n",no="NO\n";
int n,q,m;
int a[500005],b[500005],d[500005],h[500005];
string s;

struct seg_tree{
    vector<int>lazy,sz,tr,sum;
    seg_tree(){}
    seg_tree(int n):tr(n<<2),lazy(n<<2),sz(n<<2),sum(n<<2){}
    void push_up(int rt){tr[rt]=(tr[ls]+tr[rs])%mod;sum[rt]=(sum[ls]+sum[rs])%mod;}
    void build(int rt,int l,int r){
        sz[rt]=r-l+1;
        if(l==r){tr[rt]=a[l];sum[rt]=(a[l]*a[l])%mod;return;}
        build(lson);build(rson);
        push_up(rt);
    }
    void push_down(int rt){
        if(lazy[rt]){
            sum[ls]=(sum[ls]+2*lazy[rt]*tr[ls]%mod+lazy[rt]*lazy[rt]%mod*sz[ls]%mod)%mod;
            sum[rs]=(sum[rs]+2*lazy[rt]*tr[rs]%mod+lazy[rt]*lazy[rt]%mod*sz[rs]%mod)%mod;
            (tr[ls]+=lazy[rt]*sz[ls])%=mod;
            (tr[rs]+=lazy[rt]*sz[rs])%=mod;
            (lazy[ls]+=lazy[rt])%=mod;
            (lazy[rs]+=lazy[rt])%=mod;
            lazy[rt]=0;
        }
    }
    void change(int rt,int l,int r,int x,int k){}
    void update(int rt,int l,int r,int ql,int qr,int k){
        //cout<<rt<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<k<<endl; 
        if(ql<=l&&r<=qr){
            sum[rt]=(sum[rt]+2*k*tr[rt]%mod+k*k%mod*sz[rt]%mod)%mod;
            tr[rt]=(tr[rt]+k*sz[rt])%mod;
            (lazy[rt]+=k)%=mod;
            return;
        }
        push_down(rt);
        if(mid>=ql) update(lson,ql,qr,k);
        if(mid<qr) update(rson,ql,qr,k);
        push_up(rt);
    }
    int query(int rt,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return sum[rt];
        push_down(rt);
        if(mid>=qr)return query(lson,ql,qr);
        if(mid<ql) return query(rson,ql,qr);
        return (query(lson,ql,qr)+query(rson,ql,qr))%mod;
    }
}seg;
#undef mid
int l[500005],r[500005],w[500005];
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    seg=seg_tree(n);
    seg.build(1,1,n);
    while(q--){
        char op;cin>>op;
        if(op=='u'){
            int l,r,w;cin>>l>>r>>w;
            w=(w+mod)%mod;
            seg.update(1,1,n,l,r,w);
        }
        else{
            int l,r;cin>>l>>r;
            cout<<seg.query(1,1,n,l,r)<<endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(1);
    int t=1;
    while(t--){
        solve();
    }
}

L. Limited Increasing Sequences

dp文章来源地址https://www.toymoban.com/news/detail-401842.html

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return jie[n]*invjie[m]%mod*invjie[n-m]%mod;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,m;
int ans;
int dis[200005],cost[200005];
vector<pii>p[200005];
queue<int>q;
int dp[1000005];
void solve(){
    cin>>n;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int dx=(dp[i-1]+mod-dp[(i-1)/2])%mod;
        dp[i]=(dx+dp[i-1])%mod;
    }
    cout<<(dp[n]+mod-dp[n-1])%mod;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    //cin>>t;
    while (t--)
		solve();
}