原做法来自这篇讨论区。如果我统计的时候固定后面九位,枚举前面九位的超集,并且在转移答案的时候固定前面九位,枚举后面九位的子集的话就可以通过此题。
但是如果我统计的时候固定前面九位,枚举后面九位的超集,并且在转移时固定后面九位,枚举前面九位的子集的话就只能拿到 65pts。评测记录。
后面这种做法的代码如下:
#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;
}
个人感觉这两种做法都行,但是没有找到后面这种做法为什么没过。谢谢各位!