数位DP 补题

Palindrome Function

题意分析

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

分析

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

代码


/*made in mrd*/
#include
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<
#define bug3(x,y,z) cout<=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 #"< .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/

Xor

分析

file

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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<
数位DP

相关

数位dp学习记录

[ICPC2020济南L] Bit Sequence - 数位dp

codeforces597 div2 F 数位dp

数位dp的学习

【题解】CF1290F Making Shapes | 20211215 模拟赛 图形【数位DP】

洛谷P2602 [ZJOI2010] 数字计数 （数位DP）

标签