hdu5432Rikka with Array (数位dp+十进制转化为二进制)

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an array A of
length n，and
the ith
element of A is
equal to the sum of all digits of i in
binary representation. For example,A[1]=1,A[3]=2,A[10]=2.

Now, Yuta wants to know the number of the pairs (i,j)(1≤i<j≤n) which
satisfy A[i]>A[j].

It is too difficult for Rikka. Can you help her?

Input

The first line contains a number T(T≤10)——The
number of the testcases.

For each testcase, the first line contains a number n(n≤10300).

Output

For each testcase, print a single number. The answer may be very large, so you only need to print the answer modulo 998244353.

Sample Input

1
10

Sample Output

When $n=10$, $A$ is equal to $1,1,2,1,2,2,3,1,2,2$.

So the answer is $7$.

题意：定义A[i]为i化为二进制后的1的个数，给你一个数n，你要在1~n之间找到两个数a,b，使得a<b且A[a]>A[b].问总共有多少这样的对数.

思路：这题和普通的数位dp不同，普通的数位dp是求单个数内的方案数，但是这道题是求对数，所以不能用之前的方法。这道题中我们要在记忆化搜索中同时枚举两个数，一个为大数，一个为小数，然后用dp[pos][cha][flag][same][lim]表示前pos位，大小两数化为二进制后1的个数差的绝对值为cha，flag表示是否小数化为二进制后的1的个数大于大数，same表示pos位前两个数是不是完全相同，lim表示大数是不是还有限制。据说题解只开了三维，感觉三维的条件太少了，我只会写五维的。。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<bitset>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef long double ldb;

#define inf 99999999

#define pi acos(-1.0)

#define maxn 1005

#define MOD 998244353

char s[maxn];

int dp[maxn][maxn][2][2][2];   //dp[pos][cha][flag1][same][lim]表示前pos位，大小数1的个数差的绝对值是cha,小数中1的个数是不是大于大数中的个数

int wei[maxn],num[maxn];

int dfs(int pos,int cha,int flag,int same,int lim)   //same表示大数和小数是不是前几位都一样

{

    int i,j;

    if(pos==0){

        if(flag==1)return 1;

        return 0;

    }

    if(dp[pos][cha][flag][same][lim]!=-1 ){

        return dp[pos][cha][flag][same][lim];

    }

    int ans=0;

    if(same==1){

        if(lim==1){

            if(wei[pos]==0){

                 ans=ans+dfs(pos-1,0,0,1,1);  //都取0

                 if(ans>=MOD)ans-=MOD;

            }

            else if(wei[pos]==1){

                ans=ans+dfs(pos-1,0,0,1,1);if(ans>=MOD)ans-=MOD;  //都取1

                ans=ans+dfs(pos-1,0,0,1,0);if(ans>=MOD)ans-=MOD;  //都取0

                ans=ans+dfs(pos-1,1,0,0,1);if(ans>=MOD)ans-=MOD;   //大数取1，小数取0

            }

        }

        else if(lim==0){

            ans=ans+dfs(pos-1,0,0,1,0);if(ans>=MOD)ans-=MOD;

            ans=ans+dfs(pos-1,0,0,1,0);if(ans>=MOD)ans-=MOD;

            ans=ans+dfs(pos-1,1,0,0,0);if(ans>=MOD)ans-=MOD;

        }

    }

    else if(same==0){

        if(lim==1){

            if(wei[pos]==1){

                ans=ans+dfs(pos-1,cha,flag,same,0);if(ans>=MOD)ans-=MOD;  //都加0

                ans=ans+dfs(pos-1,cha,flag,same,1);if(ans>=MOD)ans-=MOD;  //都加1

                if(cha==0){

                    ans=ans+dfs(pos-1,1,0,same,1);if(ans>=MOD)ans-=MOD; //大数加1

                    ans=ans+dfs(pos-1,1,1,same,0);if(ans>=MOD)ans-=MOD;  //小数加1

                }

                else if(cha>0){

                    if(flag==1){

                        int flag1;

                        if(cha==1)flag1=0;

                        else flag1=1;

                        ans=ans+dfs(pos-1,cha-1,flag1,same,1);if(ans>=MOD)ans-=MOD; //大数加1

                        ans=ans+dfs(pos-1,cha+1,1,same,0);if(ans>=MOD)ans-=MOD;  //小数加1

                    }

                    else if(flag==0){

                        ans=ans+dfs(pos-1,cha+1,0,same,1 );if(ans>=MOD)ans-=MOD; //大数加1

                        ans=ans+dfs(pos-1,cha-1,0,same,0);if(ans>=MOD)ans-=MOD;  //小数加1

                    }

                }

            }

            else if(wei[pos]==0){

                ans=ans+dfs(pos-1,cha,flag,same,1);if(ans>=MOD)ans-=MOD;  //都加0

                if(cha==0){

                    ans=ans+dfs(pos-1,cha+1,1,same,1);if(ans>=MOD)ans-=MOD; //大数加0，小数加1

                }

                else if(cha>0){

                    if(flag==1){

                        ans=ans+dfs(pos-1,cha+1,1,same,1);if(ans>=MOD)ans-=MOD;

                    }

                    else if(flag==0){

                        ans=ans+dfs(pos-1,cha-1,0,same,1);if(ans>=MOD)ans-=MOD;

                    }

                }

            }

        }

        else if(lim==0){

            ans=ans+dfs(pos-1,cha,flag,same,0);if(ans>=MOD)ans-=MOD;  //都加0

            ans=ans+dfs(pos-1,cha,flag,same,0);if(ans>=MOD)ans-=MOD;  //都加1

            if(cha==0){

                ans=ans+dfs(pos-1,1,0,same,0);if(ans>=MOD)ans-=MOD;  //大数加1

                ans=ans+dfs(pos-1,1,1,same,0);if(ans>=MOD)ans-=MOD;  //小数加1

            }

            else if(cha>0){

                if(flag==1){

                    int flag1;

                    if(cha==1)flag1=0;

                    else flag1=1;

                    ans=ans+dfs(pos-1,cha-1,flag1,same,0 );if(ans>=MOD)ans-=MOD; //大数加1

                    ans=ans+dfs(pos-1,cha+1,1,same,0);if(ans>=MOD)ans-=MOD;  //小数加1

                }

                else if(flag==0){

                    ans=ans+dfs(pos-1,cha+1,0,same,0 );if(ans>=MOD)ans-=MOD; //大数加1

                    ans=ans+dfs(pos-1,cha-1,0,same,0);if(ans>=MOD)ans-=MOD;  //小数加1

                }

            }

        }

    }

    dp[pos][cha][flag][same][lim]=ans;

    return ans;

}

void solve()

{

    int i,j;

    int len=strlen(s+1);

    for(i=len;i>=1;i--){

        num[i]=s[len+1-i]-'0';

    }

    int tot=0;

    while(len){

        for(i=len-1;i>=1;i--){

            num[i]+=(num[i+1]&1)*10;

            num[i+1]>>=1;

        }

        if(num[1]&1)wei[++tot]=1;

        else wei[++tot]=0;

        num[1]>>=1;

        if(num[len]==0)len--;

    }

    memset(dp,-1,sizeof(dp));     //这里要注意，必须每一个样例都要初始化一遍，因为不同的数，dp[pos][cha][flag1][same][lim]的意义不同

    printf("%d\n",dfs(tot,0,0,1,1)%MOD);

}

int main()

{

    int n,m,i,j,T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",s+1);

        solve();

    }

    return 0;

}

巴特西

hdu5432Rikka with Array (数位dp+十进制转化为二进制)

最新文章

热门文章