生活随笔
收集整理的這篇文章主要介紹了
2020 ICPC 上海 Sum of Log 数位dp + 状态剪枝
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
思路：
觀察可以發(fā)現(xiàn)，由于i&j=0i \And j=0i&j=0，所以log2(i+j)log_2(i+j)log2?(i+j)表示的應(yīng)該是i+ji+ji+j的111的最高位。
一個顯然的dpdpdp狀態(tài)就出來了f[pos][flag1][flag2][maxlen]f[pos][flag1][flag2][maxlen]f[pos][flag1][flag2][maxlen]表示到了pospospos位，flag1,flag2flag1,flag2flag1,flag2分別表示x,yx,yx,y是否能選到上界，maxlenmaxlenmaxlen就是最高位。這個的復(fù)雜度是30?2?2?3030*2*2*3030?2?2?30的，由于T≤1e5T\le 1e5T≤1e5，而且只給了1s1s1s，這個顯然會TTT的很慘，所以考慮如何優(yōu)化。
如果我們?nèi)サ?span id="ze8trgl8bvbq" class="katex--inline">maxlenmaxlenmaxlen之后，f[pos][flag1][flag2]f[pos][flag1][flag2]f[pos][flag1][flag2]求出來的是什么呢？是滿足i&j=0i\And j=0i&j=0的數(shù)的個數(shù)，由于最高位也是數(shù)的一個特征，所以想要在dpdpdp中維護(hù)是不太可能的事情了，考慮每一位只有可能是i,ji,ji,j當(dāng)中的一個為111，那么我們可以通過枚舉最高位是111，讓后用去掉maxlenmaxlenmaxlen的dpdpdp算出有多少個，之后乘上長度不就行啦，這樣求一次的復(fù)雜度就降為30+30?2?230+30*2*230+30?2?2了，就可以穩(wěn)過辣。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int x
,y
;
LL f
[31][2][2];
int a
[100],b
[100];LL
dp(int pos
,int flag1
,int flag2
) {if(pos
==-1) return 1;if(f
[pos
][flag1
][flag2
]!=-1) return f
[pos
][flag1
][flag2
];int x
=flag1
? 1:a
[pos
];int y
=flag2
? 1:b
[pos
];LL ans
=0;for(int i
=0;i
<=x
;i
++) {for(int j
=0;j
<=y
;j
++) {if(i
==1&&j
==1) continue;ans
+=dp(pos
-1,flag1
||i
<x
,flag2
||j
<y
);ans
%=mod
;}}return f
[pos
][flag1
][flag2
]=ans
;
}void solve() {for(int i
=30;i
>=0;i
--) {a
[i
]=x
>>i
&1;b
[i
]=y
>>i
&1;}
}int main()
{
int _
; cin
>>_
;while(_
--) {memset(f
,-1,sizeof(f
));scanf("%d%d",&x
,&y
); solve();int len1
=(int)log2(x
),len2
=(int)log2(y
);LL ans
=0;for(int i
=0;i
<=len1
;i
++) ans
+=dp(i
-1,i
<len1
,i
<=len2
)*(i
+1),ans
%=mod
;for(int i
=0;i
<=len2
;i
++) ans
+=dp(i
-1,i
<=len1
,i
<len2
)*(i
+1),ans
%=mod
;printf("%lld\n",ans
);}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的2020 ICPC 上海 Sum of Log 数位dp + 状态剪枝的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
