2020上海ICPC区域赛——C题Sum of Log
题目链接：https://ac.nowcoder.com/acm/contest/9925/C
题意
给你
x
x
x
和
y
y
y
，让你求出
∑
i
=
0
x
∑
j
=
[
i
=
=
0
]
y
[
i
\sum^{x}_{i=0}\sum^{y}_{j=[i==0]}[i
∑
i
=
0
x
∑
j
=
[
i
=
=
0
]
y
[
i
&
j
=
0
]
[
l
o
g
2
(
i
+
j
)
+
1
j=0][log_{2}(i+j)+1
j
=
0
]
[
l
o
g
2
(
i
+
j
)
+
1
。
题解
首先我们要把题目中的公式转换一下，
当
i
i
i
&
j
=
=
0
j==0
j
=
=
0
时
⌊
l
o
g
2
(
i
+
j
)
+
1
⌋
\lfloor log_{2}(i+j)+1 \rfloor
⌊
l
o
g
2
(
i
+
j
)
+
1
⌋
即表示
i
i
i
和
j
j
j
中最高的非
0
0
0
二进制位。
eg：
20
20
2
0
&
8
=
=
0
8==0
8
=
=
0
，
20
20
2
0
的二进制位为
10100
10100
1
0
1
0
0
，
8
8
8
的二进制位为
01000
01000
0
1
0
0
0
，
⌊
l
o
g
2
(
20
+
8
)
+
1
⌋
=
5
\lfloor log_{2}(20+8)+1 \rfloor=5
⌊
l
o
g
2
(
2
0
+
8
)
+
1
⌋
=
5
，即为
20
20
2
0
的最高非
0
0
0
二进制位。
因此问题就变的简单了许多。
这次数位
d
p
dp
d
p
的状态和
牛客多校第六场的H题
类似。
首先我们需要维护数位
d
p
dp
d
p
中固定的一维，即枚举到了第几位。
后面两维也比较套路，即一维维护是否超过
x
x
x
数位上限，一维维护是否超过
y
y
y
数位上限。
还有一维维护是否前一位是否是前导
0
0
0
。
剩下的状态就需要我们仔细考虑了。
第一印象肯定是直接维护最高的非
0
0
0
二进制位。
但是算一下数据范围发现会超时。
那么我们怎么优化就比较关键了。
因为我们要维护的是最高的非
0
0
0
二进制位，
而我们之前已经维护了一维来纪录前导
0
0
0
，每当当前位的前一位是前导
0
0
0
且当前位为
1
1
1
时，即表示当前位会对后面所有合法数的个数产生贡献，因此这个状态已经足够我们维护答案了。
状态：
d
p
[
p
o
s
]
[
s
x
]
[
s
y
]
[
l
e
a
d
]
dp[pos][sx][sy][lead]
d
p
[
p
o
s
]
[
s
x
]
[
s
y
]
[
l
e
a
d
]
表示当前位为
p
o
s
pos
p
o
s
，sx表示是否已经超过
x
x
x
数位上限，sy表示是否已经超过
y
y
y
数位上限，
l
e
a
d
lead
l
e
a
d
表示前一位是否为前导
0
0
0
。
剩下的过程算是数位
d
p
dp
d
p
的套路，枚举x的数位和
y
y
y
的数位也算是牛客多校的套路。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int mod = 1e9+7;
int a[40],b[40];
ll dp[40][2][2][2];
int len;
ll dfs(int pos,int sx,int sy,int lead){
if(pos==-1) return 1;
if(dp[pos][sx][sy][lead]!=-1) return dp[pos][sx][sy][lead];
ll ans=0;
int up1=(sx?a[pos]:1);
int up2=(sy?b[pos]:1);
rp(i,0,up1){
rp(j,0,up2){
if(i&j) continue;
ll num=1;
if(lead&&(i||j)) num=pos+1;
ans=(ans+1ll*dfs(pos-1,sx&&i==up1,sy&&j==up2,lead&&!i&&!j)*num%mod)%mod;
}
}
return dp[pos][sx][sy][lead]=ans;
}
void solve(){
int x=read(),y=read();
mst(dp,-1);
len=0;
while(x||y){
a[len]=(x&1);
b[len]=(y&1);
y>>=1;
x>>=1;
len++;
}
cout<<(dfs(len-1,1,1,1)-1+mod)%mod<<endl;
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
int T=read();
while(T--) solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}