AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

【位运算\or\DP】CF--2400DP

作者: 作者的头像   yankai ,  2024-11-30 13:32:30 ,  所有人可见 ,  阅读 17


0


https://codeforces.com/contest/2038/problem/D
给一个数组,要求将数组拆分成若干段(约等于放隔板的意思),要求每一段所有元素的OR是递增的。有多少种拆分方法。数组元素取值范围小于1e9。

一个结论:对于一个位置,以该位置为右边界(或左边界)的所有区间,OR的结果数量级是$log_2^{1e9}$。因为只能增加是1的位数,而不会减少。

1.使用$dp[i][j]$,状态表示为考虑前i个元素,最后一段的结尾的OR值是j。 那么他的状态转移:就是$$\sum dp[m][n]\ \ \ \ \forall m<i,n<=j,且m+1位置到i位置的OR结果是j \\ 最后的答案是:\sum dp[n][v]$$
2.但是不可能枚举$j$,所以必须在枚举每个$i$时提前处理好所有$(v,r)$表示从$r$位置OR到$i$的结果是$v$。因为不同$v$的数量是log级别的。
3.然后对每个$v$,状态转移是$dp[i][v] +=dp[m][n] \ \ \ \ \forall m<r,n<=v $但是这样还是不行,我们应该考虑提前处理好这些符合要求的$dp[m][n]$的和。
4.注意到对于$v$,随着$r$的减少$v$是递增的,所以对每个$v$存在一个区间,这个区间里所有位置OR到$i$的结果都是$v$。要得到这个区间,$(v,r)$的r维护成最小的$r$,使得$r$到位置$i$OR的结果是$v$。然后这个区间就是$[r,r’],r’是上一个v的r再减1。$
5.如果求得这个区间,转移就可以使用某种维护区间和的数据结构,不用枚举m,只需要枚举n了。但是区间内每个数的n的取值范围不同,也不可能枚举,唯一的共性是都小于等于v。联想到最后的答案是也要加上它最后一段所有取值的dp值,因此考虑“离线”处理dp,按v从小到大处理,则状态转移时不需要枚举n,只需要加上当前位置它所有的dp值即可。这个dp转移描述为$$(v,i,l,r):代表从区间[l,r]或到i位置的OR值是v\\ 则这步状态转移应该是dp[i] += \sum_{k=l}^{k=r} dp[k]$$注意状态转移的先后顺序,此状态转移时,对于同一个v,dp[l~r]也应该先于dp[i]处理好,所以按照v从小到大排序,v相同时按照i从小到大排序的顺序进行状态转移。
6.分析到这,只需要单点修改和区间查询,使用树状数组即可。于是先遍历一边数组,求出所有的状态$(v,i,l,r)$,然后排序一遍。然后使用树状数组求dp值。最后输出答案$dp[n]$,注意初始值$dp[0][0] = 1$由于模版的树状数组最小下标是1,因此所有下标往右平移一格。

7.时间复杂度:处理一次dp转移logn,每个位置有$log_2^{1e9}$的状态。最终时间复杂度$O(nlog^n log^{1e9})$

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const ll mod =  998244353;

struct fenwick{
    vector<ll> tr;
    int n;
    fenwick(int n):n(n){tr.resize(n+5,0);}
    ll lowbit(ll x){
        return x&-x;
    }
    void add(ll x,ll v){
        for(;x<=n;x+=lowbit(x)){
            tr[x] = (tr[x] + v)%mod;
        }
    }
    ll query(ll x){
        ll res = 0;
        for(;x;x-=lowbit(x)){
            res = (res + tr[x])%mod;
        }
        return res;
    }
    ll rangeSum(ll l,ll r){
        return (query(r) - query(l-1)+mod)%mod;
    }
};
int n;
vector<ll> a;
void solve(){
    cin>>n;
    a.resize(n+5);
    for(int i=2;i<=n+1;i++) cin>>a[i];
    fenwick tr(n+1);
    tr.add(1,1);
    vector<array<ll,4>> seg;
    vector<array<ll,2>> f;
    f.push_back({0,2});
    for(int i=2;i<=n+1;i++){
        for(auto &[v,r]:f){
            v|=a[i];
        }
        auto nf = f;
        f.clear();
        for(auto [v,r]:nf){
            if(!f.empty() && f.back()[0]==v) continue;
            f.push_back({v,r});
        }
        f.push_back({0,i+1});
        for(int j=0;j+1<f.size();j++){
            auto [v,r]  = f[j];
            seg.push_back({v,i,r,f[j+1][1]-1});
        }
    }
    sort(seg.begin(),seg.end());
    for(auto [v,r,i,j]:seg){
        tr.add(r,tr.rangeSum(i-1,j-1));
    }
    cout<<tr.rangeSum(n+1,n+1)<<endl;
}

int main(){     
    ifstream test_file("in.txt");
    if (test_file) {
        freopen("in.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息