UVALive 7271-A Math Problem【二进制数位DP】

矫情吗；* 2023-06-01 06:13 8阅读 0赞

题目链接：[https://vjudge.net/problem/UVALive-7271][https_vjudge.net_problem_UVALive-7271]

题意：Stan is crazy about math. One day, he was confronted with an interesting integer function defined  
on positive integers, which satisfies f(1) = 1 and for every positive integer n, 3 × f(n) × f(2n + 1) =  
f(2n) × (1 + 3f(n)), f(2n) < 6 × f(n).  
He wanted to know, in the range of 1 to n, for a given k, what are f(i) mod k like. For simplicity,  
you could just calculate the number of i which satisfies f(i) mod k = t for every t in range of 0 to k–1  
as g(t), and tell Stan what is all g(x) xor up is.

定义了一个f函数，我们不难发现f\[i\] 就是i的二进制下为1的位的3的幂次方的和，g（x）函数就是f(1) ~ f(n) 中mod k = x的个数。

由于n范围1e18， 我们考虑用数位DP来求解，dp\[i\]\[j\] 表示第i位，余数为j的个数，那么我们就在二进制上进行数位DP就可以了。

这道题uva好像数据有问题，可以到这里交[打开链接][Link 1]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll dp[65][70000], p[65]; //dp[i][j]表示第i位余数为j的答案
    int a[65], k;
    
    void init()
    {
        ll ret = 1;
        p[0] = 1;
        for(int i = 1; i <= 61; ++i)
        {
            ret = ret * 3 % k;
            p[i] = ret;
        }
    }
    ll dfs(int pos, int sum, int limit)
    {
        if(pos == -1) return sum == 0; //为0的话说明可以模数为0
        if(!limit && dp[pos][sum] != -1) return dp[pos][sum];
        int up = limit ? a[pos] : 1; //二进制最大为1
        ll ret = 0;
        for(int i = 0; i <= up; ++i)
        {
            ll tmp = sum;
            if(i) tmp = (tmp - p[pos] + k) % k; //该位为1的话就减去该位权
            ret += dfs(pos - 1, tmp, limit && (i == up));
        }
        if(!limit) dp[pos][sum] = ret;
        return ret;
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            memset(dp, -1, sizeof(dp));
            ll n;
            scanf("%lld%d", &n, &k);
            init();
            ll tmp = 0;
            int tot = 0;
            ll x = n;
            while(x) //拆分成二进制存储
            {
                a[tot++] = x & 1;
                x >>= 1;
            }
            for(int i = 0; i < k; ++i)
            {
                ll ans = dfs(tot - 1, i, 1);
                if(i == 0) ans--; //算的是[0, i]的区间，所以要减去1
                tmp ^= ans;
            }
            printf("%lld\n", tmp);
        }
        return 0;
    }

[https_vjudge.net_problem_UVALive-7271]: https://vjudge.net/problem/UVALive-7271
[Link 1]: http://hihocoder.com/problemset/problem/1259