题目描述：
给出五个数（不超过2^63-1），让你求下面代码的sum值
for(ll i = a; i <= b; i++)
for(ll j = c; j<= d; j++)
if((i ^ j) > e)
sum += i^j;
算法分析：
先通过容斥原理，把问题变成“[0,a]和[0,b]”。这一部分的解法如下：
数位DP ， dp[i][j][k][len]表示前len长度，i = 0代表a的第len位取原值，i=1代表a的第len位取1，j同理，k=0表示e的第len位取0，k=1表示取原值的，方案数。
于是这种推，咱们可以根据i,j,k的不同写出状态转移。但是这题要求的是sum，而非方案数。所以按照这个状态再维护一个sum值。
tp 代表当a(len) xor b(len) = 1时的方案数。那么sum值应该等于tp * (2^len) + (上面dp转移中的len－1位的sum值)
代码：
fzu 2042
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 typedef long long ll;
6 const int N = 63;
7 int cha[100],chb[100],chc[100];
8 ll dp[2][2][2][100],pw[100],sum[2][2][2][100];
9 inline void work(ll a,int c[]){
10 for(int i = 0; i < 63; i++, a>>=1)
11 c[i] = a&1;
12 }
13 inline void prepare(ll a,ll b,ll c){
14 work(a,cha);
15 work(b,chb);
16 work(c,chc);
17 memset(dp,-1,sizeof(dp));
18 memset(sum,-1,sizeof(sum));
19 }
20 const int mod = (int)1e9+7;
21 ll dfs(int a=0,int b=0,int c=1,int l=N){
22 ll &ans = dp[a][b][c][l];
23 if(ans != -1) return ans;
24 ll &s = (sum[a][b][c][l] = 0);
25 int va = cha[l] || a;
26 int vb = chb[l] || b;
27 int vc = chc[l] && c;
28 if(0 == l) {
29 if(vc == 1) ans = 0;
30 else if(va && vb) { if(c) s = ans = 2; else s = 2,ans = 4;}
31 else if(va || vb) { if(c) s = ans = 1; else s = 1,ans = 2;}
32 else { if(c) ans = 0; else ans = 1;}
33 // cout<<va<<" "<<vb<<" "<<vc<<endl;
34 // cout<<"l: "<<l<<" "<<a<<" "<<b<<" "<<c<<" "<<ans<<" "<<s<<endl;
35 return ans;
36 }
37 ll tp = 0;
38 if(va && vb) {
39 if(vc == 1) {
40 tp = (ans = (dfs(1,b,1,l-1) + dfs(a,1,1,l-1)) % mod);
41 s = sum[1][b][1][l-1] + sum[a][1][1][l-1] % mod;
42 }
43 else {
44 ans = (dfs(a,b,c,l-1) + dfs(1,1,c,l-1) + (tp = dfs(a,1,0,l-1) + dfs(1,b,0,l-1))) % mod;
45 s = sum[a][b][c][l-1] + sum[1][1][c][l-1] + sum[a][1][0][l-1] + sum[1][b][0][l-1] ;
46 }}
47 else if(va || vb) {
48 if(vc) {tp = ans = dfs(a,b,c,l-1); s = sum[a][b][c][l-1]; }
49 else if(va) { ans = ((tp = dfs(a,b,0,l-1)) + dfs(1,b,c,l-1)) % mod; s = sum[a][b][0][l-1] + sum[1][b][c][l-1]; }
50 else { ans = ((tp = dfs(a,b,0,l-1)) + dfs(a,1,c,l-1)) % mod; s = sum[a][b][0][l-1] + sum[a][1][c][l-1];}
51 }
52 else {
53 if(vc) ans = 0;
54 else { ans = dfs(a,b,c,l-1); s= sum[a][b][c][l-1];}
55 }
56 s %= mod;
57 tp %= mod;
58 s = (s + tp * pw[l]) % mod;
59 // cout<<"l: "<<l<<" "<<a<<" "<<b<<" "<<c<<" "<<ans<<" "<<s<<" "<<tp<<endl;
60 return ans;
61 }
62 int main(){
63 pw[0] = 1;
64 for(int i = 1; i < 70; i++) pw[i] = (pw[i-1]<<1) % mod;
65 int tst;
66 cin >> tst;
67 for(int oo= 1; oo <=tst; oo++){
68 ll a,b,c,d,e;
69 cin >> a >> b >> c >> d >> e;
70 printf("Case %d: ",oo);
71 // cout<<"cal: "<<b<<" "<<d<<" "<<e<<endl;
72 prepare(b,d,e);
73 dfs();
74 ll ans =sum[0][0][1][N];
75 if(a && b){
76 // cout<<"cal: "<<a-1<<" "<<d<<" "<<e<<endl;
77 prepare(a-1,d,e);
78 dfs();
79 ans -=sum[0][0][1][N];
80 // cout<<"cal: "<<c-1<<" "<<b<<" "<<e<<endl;
81 prepare(c-1,b,e);
82 dfs();
83 ans -=sum[0][0][1][N];
84 // cout<<"cal: "<<a-1<<" "<<c-1<<" "<<e<<endl;
85 prepare(a-1,c-1,e);
86 dfs();
87 ans +=sum[0][0][1][N];
88 ans += 2*mod; ans %= mod;
89 }
90 printf("%d\n",(int)ans);
91 }
92 }
93 posted on 2012-10-10 14:56
西月弦 阅读(414)
评论(0) 编辑 收藏 引用 所属分类:
解题报告