[HNOI2002]Kathy函数

灰太狼 2021-11-13 15:14 214阅读 0赞

[题面][Link 1]

满足f(n)=n的n在二进制的形式下一定是一个回文数

#include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const int base = 1e8;
    const int N = 20;
    int aux[N << 3];
    struct bigint {
        int s[N], l;
        void CL() { l = 0; memset(s, 0, sizeof(s)); }
        void pr()
        {
            printf("%d", s[l]);
            for (int i = l - 1; i; i--)
                printf("%08d", s[i]);
        }
        void re_l()
        {
            int i, x = 0, k = 1, L = 0, fl, o;
            char c = getchar();
            for (; c < '0' || c > '9'; c = getchar());
            for (; c >= '0' && c <= '9'; c = getchar())
            {
                if (!(L - 1) && !aux[L])
                    L--;
                aux[++L] = c - '0';
            }
            CL();
            l = L / 8 + ((o = L % 8) > 0);
            for (i = 1; i <= o; i++)
                x = x * 10 + aux[i];
            if (o)
                s[l] = x;
            fl = !o ? l + 1 : l;
            for (i = o + 1, x = 0; i <= L; i++, k++)
            {
                x = x * 10 + aux[i];
                if (!(k ^ 8))
                {
                    s[--fl] = x;
                    x = k = 0;
                }
            }
            if (!l)
                l = 1;
        }
        ll toint()
        {
            ll x = 0;
            for (int i = l; i; i--)
                x = x * base + s[i];
            return x;
        }
        bigint operator = (int b)
        {
            CL();
            do
            {
                s[++l] = b % base;
                b /= base;
            } while (b > 0);
            return *this;
        }
        bigint operator = (ll b)
        {
            CL();
            do
            {
                s[++l] = b % base;
                b /= base;
            } while (b > 0);
            return *this;
        }
        bigint operator + (const int &b)
        {
            bigint c = *this;
            ll x = b;
            for (int i = 1; i <= l && x; i++)
            {
                x = x + c.s[i];
                c.s[i] = x % base;
                x /= base;
            }
            if(x)c.s[++c.l] = x;
            return c;
        }
        bigint operator + (const ll &b)
        {
            bigint c = *this;
            ll x = b;
            for (int i = 1; i <= l && x; i++)
            {
                x = x + c.s[i];
                c.s[i] = x % base;
                x /= base;
            }
            if (x)
                c.s[++c.l] = x;
            return c;
        }
        bigint operator + (bigint &b)
        {
            if (b.l < 3)
                return *this + b.toint();
            bigint c;
            ll x = 0;
            int k = l < b.l ? b.l : l;
            c.CL();
            c.l = k;
            for (int i = 1; i <= k; i++)
            {
                x = x + s[i] + b.s[i];
                c.s[i] = x % base;
                x /= base;
            }
            if (x)
                c.s[++c.l] = x;
            return c;
        }
        bigint operator / (const int &b)
        {
            bigint c;
            ll x = 0;
            c.CL();
            for (int i = l; i; i--)
            {
                c.s[i] = (x * base + s[i]) / b;
                x = (x * base + s[i]) % b;
            }
            for (c.l = l; !c.s[c.l] && c.l > 1; c.l--);
            return c;
        }
        bigint operator % (const int &b)
        {
            bigint c;
            ll x = 0;
            c.CL();
            for (int i = l; i; i--)
                x = (x * base + s[i]) % b;
            return c = x;
        }
        bool operator > (const bigint &b) const
        {
            if (l ^ b.l)
                return l > b.l;
            for (int i = l; i; i--)
                if (s[i] ^ b.s[i])
                    return s[i] > b.s[i];
            return false;
        }
        bigint operator += (bigint &b)
        {
            return *this = *this + b;
        }
        bool operator > (int b) const{
            bigint c;return *this > (c = b);
        }
    };
    
    bigint a;
    int num[350],tmp[350];bigint dp[350][2][350];
    bool pan[350][2][350];
    inline bigint dfs(int st,int len,int ok,bool limit){
        bigint ans,pp;ans=0;pp=0;
        if(len<1){//边界 
            if(ok&&st>0)ans=1;
            return ans;
        }
        if(!limit&&pan[len][ok][st])return dp[len][ok][st];//返回所记录的值 
        int ed=limit?num[len]:1;//处理枚举上限 
        for(int i=0;i<=ed;i++){
            tmp[len]=i;//记录每次选的数，方便判断是否满足回文 
            if(st==len&&!i)pp=dfs(st-1,len-1,ok,limit&&i==ed),ans+=pp;//如果一直都没选数 
            else pp=dfs(st,len-1,(ok&&len<=st/2)?tmp[st-len+1]==i:ok,limit&&i==ed),ans+=pp;//如果选了数 
        }
        if(!limit)dp[len][ok][st]=ans,pan[len][ok][st]=1;//记录 
        return ans;
    }
    int main(){
        a.re_l();ll Lenn=0;
        while(a>0){num[++Lenn]=(a%2).toint();a=(a/2);}//转成2进制存起来 
        bigint ans=dfs(Lenn,Lenn,1,1);
        ans.pr();
        return 0;
    }

转载于:https://www.cnblogs.com/ainiyuling/p/11249980.html

[Link 1]: https://www.luogu.org/problem/P2235