Palindrome Function

题意分析

给定左区间和右区间在k进制下是回文数有多少

分析

考虑每一个进制下的区间合法方案

代码

/*made in mrd*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define fi first
#define se second
#define lu u<<1
#define ru u<<1|1
#define pb push_back
#define bug1(x) cout<<x<<endl
#define bug2(x,y) cout<<x<<' '<<y<<endl
#define pii pair<int,int>
#define bug3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl
int a,b,c,d,n;
int bit;
int s[N];
int len;
int q[N];
int f[40][30][50];// 代表 当前位置 长度 k进制
int dfs(int pos,int len,int limit,int zero,int ok)
{
    if(!pos) return ok;
    if(!limit&&!zero&&f[pos][len][bit]>=0) return f[pos][len][bit];
    int end=limit?s[pos]:bit-1;
    int res=0;
    for(int i=0;i<=end;i++)
    {
        q[pos]=i;
        if(i==0&&zero) res+=dfs(pos-1,len-1,limit&&i==s[pos],zero,ok);
        else if(pos>len/2) res+=dfs(pos-1,len,limit&&i==s[pos],0,1);
        else if(i==q[len-pos+1]) res+=dfs(pos-1,len,limit&&i==s[pos],0,1);
    }
    if(!limit&&!zero) f[pos][len][bit]=res;
    return res;
}
int dp(int x)
{
    len =0;
    while(x)
    {
        s[++len]=x%bit;
        x/=bit;
    }
    return dfs(len,len,1,1,1);
}
signed main() {
    cin>>n;
    mem(f,-1);
    int t=1;
    while(n--)
    {
        int res=0;
        cin>>a>>b>>c>>d;
        for(int i=c;i<=d;i++)
        {
            bit=i;
            int cnt=(dp(b)-dp(a-1));
            res=res+cnt*i+(b-a+1-cnt);
        }
        cout<<"Case #"<<t++<<":"<<" "<<res<<endl;
    }
    return 0;
}
/*
* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
* └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ |   │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│  '│ Enter  │               │ 4 │ 5 │ 6 │   │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
* │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/

Xor

分析

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;

int A,B,K,W;
ll dp[63][3][3][2][2][2];
int vis[63][3][3][2][2][2];
ll bit[63];

int getbool(bool x) {
    return x? 1:0;
}

int getbit(int x,int y) {
    return (x&y)? 1:0;
}

ll dfs(int wei,int c1,int c2,bool lim1,bool lim2,bool lim3) {
    if(vis[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)]) return dp[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)];
    if(wei == -1) {
        return c1 >= 0 && c2 >= 0? 1:0;
    }
    int lt1 = lim1? getbit(bit[wei],A):1;
    int lt2 = lim2? getbit(bit[wei],B):1;
    int lt3 = lim3? getbit(bit[wei],W):1;
    int t = getbit(K,bit[wei]);
    ll res = 0;
    for(int i=0;i<=lt1;i++) {
        for(int j=0;j<=lt2;j++) {
            int x = i,y = j;
            int nc1 = c1*2 + (x-y) + t, nc2 = c2*2 + (y-x) + t;
            if(nc1 < -1 || nc2 < -1 || (x^y) > lt3) continue;
            res += dfs(wei-1,min(nc1,1),min(1,nc2),(lim1 && x == lt1),(lim2 && y == lt2),(lim3 && (x^y) == lt3));
        }
    }
    vis[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)]= 1;
    dp[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)] = res;
    return res;
}

int main() {
    bit[0] = 1;
    for(int i=1;i<=35;i++) bit[i] = (bit[i-1]<<1);
    int tes;
    scanf("%d",&tes);
    while(tes--) {
        scanf("%d%d%d%d",&A,&B,&K,&W);
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        printf("%lld\n",dfs(35,0,0,true,true,true));
    }

    return 0;
}

C - Sum of Log

题意

两个数x,y&起来==0并且 求log(x+y)+1;

分析

数位dp
dp[wei][flag][lim1][lim2]

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
 
int A,B,K,W;
ll dp[63][2][2][2];// 第几个位 最高位置 限制1 限制2
ll bit[63];
ll sum; 
int getbit(int x,int y) {
    return (x&y)? 1:0;
}
ll dfs(int wei,bool lim1,bool lim2,int flag) {
	if(wei==-1)
	{
		return 1;
	}
	if(dp[wei][flag][lim1][lim2]>-1) return dp[wei][flag][lim1][lim2];
    int lt1 = lim1? getbit(bit[wei],A):1;
    int lt2 = lim2? getbit(bit[wei],B):1;
    ll res = 0;
    for(int i=0;i<=lt1;i++) {
        for(int j=0;j<=lt2;j++) {
			if(i&j) continue;
			if(i==j)
			{
				res+=dfs(wei-1,lim1&&i==lt1,lim2&&j==lt2,flag);
			}
			else {
				ll cnt=0;
				cnt=dfs(wei-1,lim1&&i==lt1,lim2&&j==lt2,1);
				if(!flag) sum+=cnt*(wei+1)%mod,sum%=mod;
				res+=cnt;
				res%=mod;
			}
        }
    }
	if(dp[wei][flag][lim1][lim2]==-1)dp[wei][flag][lim1][lim2]=res;
	return res;
}
 
int main() {
    bit[0] = 1;
    for(int i=1;i<=35;i++) bit[i] = (bit[i-1]<<1);
    int tes;
    scanf("%d",&tes);
    while(tes--) {
		 sum=0;
		scanf("%d %d",&A,&B);
 		memset(dp,-1,sizeof(dp));
       dfs(35,1,1,0);
	   cout<<sum<<endl;
    }
 
    return 0;
}