一道十分好的数位DP
考虑二进制下每一位最多选1个1
详细见代码注释
#include<bits/stdc++.h> #define int long long using namespace std; int n; int r[12]; int c[12][70]; int dp[70][2048]; int mod=1e9+9; int dfs(int x,int pos) { if(dp[x][pos]) return dp[x][pos]; if(x==0) return 1; int ps=pos;//预计算ps for(int i=1;i<=n;i++) ps|=((c[i][x]==1)<<(i-1)); dp[x][pos]=dfs(x-1,ps);//此位填0 for(int i=1;i<=n;i++){//此位填1,枚举用哪个来填 int t=(pos>>(i-1))&1;//第i位是否可以自由填 int h= t==1?1:c[i][x];//若可以自由填,赋值1,反正赋值c if(h) dp[x][pos]=( dp[x][pos]+dfs( x-1,ps^( (t==0)<<(i-1) ) ) )%mod;//特判编号i是否自由,若不自由,则赋值为不自由 } return dp[x][pos]%mod; } signed main() { cin>>n; for(int i=1;i<=n;i++) cin>>r[i]; for(int i=1;i<=n;i++) for(int j=1;j<=60;j++) c[i][j]= (r[i]>>(j-1))&1; //1e18处理到60位即可 cout<<dfs(60,0); return 0; }