江苏省建设厅工会网站,教育app定制,开网上授课的网站应该怎么做,贵州住房和城乡建设部网站官网传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
观察可以发现#xff0c;由于ij0i \And j0ij0#xff0c;所以log2(ij)log_2(ij)log2(ij)表示的应该是ijijij的111的最高位。 一个显然的dpdpdp状态就出来了f[pos][flag1][fl…传送门
文章目录题意思路题意 思路
观察可以发现由于ij0i \And j0ij0所以log2(ij)log_2(ij)log2(ij)表示的应该是ijijij的111的最高位。 一个显然的dpdpdp状态就出来了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就是最高位。这个的复杂度是30∗2∗2∗3030*2*2*3030∗2∗2∗30的由于T≤1e5T\le 1e5T≤1e5而且只给了1s1s1s这个显然会TTT的很惨所以考虑如何优化。 如果我们去掉maxlenmaxlenmaxlen之后f[pos][flag1][flag2]f[pos][flag1][flag2]f[pos][flag1][flag2]求出来的是什么呢是满足ij0i\And j0ij0的数的个数由于最高位也是数的一个特征所以想要在dpdpdp中维护是不太可能的事情了考虑每一位只有可能是i,ji,ji,j当中的一个为111那么我们可以通过枚举最高位是111让后用去掉maxlenmaxlenmaxlen的dpdpdp算出有多少个之后乘上长度不就行啦这样求一次的复杂度就降为3030∗2∗23030*2*23030∗2∗2了就可以稳过辣。
// Problem: Sum of Log
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9925/C
// Memory Limit: 2097152 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-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 xflag1? 1:a[pos];int yflag2? 1:b[pos];LL ans0;for(int i0;ix;i) {for(int j0;jy;j) {if(i1j1) continue;ansdp(pos-1,flag1||ix,flag2||jy);ans%mod;}}return f[pos][flag1][flag2]ans;
}void solve() {for(int i30;i0;i--) {a[i]xi1;b[i]yi1;}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; cin_;while(_--) {memset(f,-1,sizeof(f));scanf(%d%d,x,y); solve();int len1(int)log2(x),len2(int)log2(y);LL ans0;for(int i0;ilen1;i) ansdp(i-1,ilen1,ilen2)*(i1),ans%mod;for(int i0;ilen2;i) ansdp(i-1,ilen1,ilen2)*(i1),ans%mod;printf(%lld\n,ans);}return 0;
}
/**/
