关于固定前一半和固定后一半的区别
查看原帖
关于固定前一半和固定后一半的区别
511170
KaruAWA楼主2024/8/17 15:14

原做法来自这篇讨论区。如果我统计的时候固定后面九位,枚举前面九位的超集,并且在转移答案的时候固定前面九位,枚举后面九位的子集的话就可以通过此题。

但是如果我统计的时候固定前面九位,枚举后面九位的超集,并且在转移时固定后面九位,枚举前面九位的子集的话就只能拿到 65pts65pts。评测记录。

后面这种做法的代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int T=(1<<9);
const int N=524287+5;
int n;
int dp[N];
int ansi;

signed main(){
    ios::sync_with_stdio(false);
    cin>>n;

    for(int i=1;i<=n;++i){
        int s;
        cin>>s;
        int x=s/T,y=s%T,sum=0;
        // cerr<<x<<" "<<y<<"\n";
        // cerr<<(x<<9)<<" ";
        for(int t=y;t<=T;t=(t+1)|y){
            sum=(sum+dp[(x<<9)|t])%mod;
            // cerr<<((x<<9)|t)<<" ";
        }
        ansi=(ansi+sum)%mod;
        sum=(sum+1)%mod;

        dp[y]=(dp[y]+sum)%mod;
        for(int t=x;t;t=(t-1)&x) dp[(t<<9)|y]=(dp[(t<<9)|y]+sum)%mod;
    }
    cout<<ansi;
    return 0;
}

个人感觉这两种做法都行,但是没有找到后面这种做法为什么没过。谢谢各位!

2024/8/17 15:14
加载中...