代理商加盟网站,营销策划公司是做什么的,禁止拿我们的网站做宣传,云南网站设计CF1245F Daniel and Spring Cleaning
题意#xff1a;
给定l#xff0c;r#xff0c;求∑alr∑blr[aba⊕b]\sum_{al}^{r}\sum_{bl}^{r}[aba⊕b]∑alr∑blr[aba⊕b]
题解#xff1a;
对于这个式子#xff0c;只有当a和b都不为0时成立#xff0c;也就是我们不求 对…CF1245F Daniel and Spring Cleaning
题意
给定lr求∑alr∑blr[aba⊕b]\sum_{al}^{r}\sum_{bl}^{r}[aba⊕b]∑alr∑blr[aba⊕b]
题解
对于这个式子只有当a和b都不为0时成立也就是我们不求 对于这个式子有f(x,y)f(y,x) 考虑差分f(r,r)-f(l-1,r)-f(r,l-1)f(l-1,l-1) 答案为f(r,r)-2f(l-1,r)f(l-1,l-1) 数位dp转移即可数位dp还是dfs的转移好写
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn50;
ll dp[maxn][2][2][2];
int b[maxn],a[maxn];
ll dfs(int len,int flag1,int flag2,int flag3){if(!len){return flag3;}if(dp[len][flag1][flag2][flag3]!-1)return dp[len][flag1][flag2][flag3];ll res0;int up1flag1?a[len]:1;int up2flag2?b[len]:1;for(int i0;iup1;i){for(int j0;jup2;j){bool Fflag3;if((ij)!0)F0;resdfs(len-1,(iup1)flag1,(jup2)flag2,F);}}return dp[len][flag1][flag2][flag3]res;
}ll solve(ll x,ll y){if(x0||y0)return 0;int num10,num20; memset(dp,-1,sizeof(dp));for(int i0;i40;i){a[i]0;b[i]0;}while(x){a[num1]x%2;x/2;}while(y){b[num2]y%2;y/2;}ll ansdfs(32,1,1,1);return ans;
}
int main()
{rd_test();int t;read(t);while(t--){ll l,r;read(l,r);coutsolve(r,r)-2ll*solve(l-1,r)solve(l-1,l-1)endl;}return 0;//Time_test();
}
