1 条题解

  • 1
    @ 2018-09-28 16:36:53

    我们首先枚举一下有多少个奇数(0-5个)出现在了数中,然后把它们(注意有些奇数数量有多种方式,例如出现1个奇数可能是出现1,3,5,7,或者9,所以计算ans时有些地方乘了5、10)的数量加起来,就是所有可能性的和。
    上面的变换,使得计算时,不需要在下面的状态中特殊考虑一个奇数位根本不存在的情况,简化了状态的设置。
    任何一个数字都有一个状态(a, b)(a, b均不超过5),表示该数当前有a个奇数位的数量不符合要求,有b个偶数位的数量不符合要求。
    在(a, b)状态,并且长度为x位的数的数量,可以从x-1位的值递推出来。绚丽多彩的数,就是在(0, 0)状态的数。
    因为题目要求位数不超过n,而不要求位数正好为n,我们再引入一个X状态(代码中表示为36状态),意思是数字还没有开始。
    使用矩阵乘法优化一下这个递推,就可以做出来了。

    #include <cstdio>
    #include <algorithm>
    
    #define ll long long
    #define encode(badodd, badeven) (6 * (badodd) + (badeven))
    
    using namespace std;
    
    ll n, p;
    
    ll matrix_a[37][37];
    
    ll fastpow[61][37][37];
    
    ll matrix_b[37][37];
    ll matrix_temp[37][37];
    
    void matmul(ll ans[37][37], ll a[37][37], ll b[37][37])
    {
        for (int i = 0; i <= 36; i++) {
            for (int j = 0; j <= 36; j++) {
                ans[i][j] = 0;
                for (int k = 0; k <= 36; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                    ans[i][j] %= p;
                }
            }
        }
    }
    
    void matcopy(ll to[37][37], ll from[37][37])
    {
        for (int i = 0; i <= 36; i++) {
            for (int j = 0; j <= 36; j++) {
                to[i][j] = from[i][j];
            }
        }
    }
    
    ll calc(int oddcnt)
    {
        for (int i = 0; i <= 36; i++) {
            for (int j = 0; j <= 36; j++) {
                matrix_a[i][j] = 0;
            }
        }
        matrix_a[36][36] = 1;
        for (int i = 0; i <= oddcnt; i++) {
            for (int j = 0; j <= 5; j++) {
                matrix_a[encode(i, j)][encode(i - 1, j)] = i;
                matrix_a[encode(i, j)][encode(i + 1, j)] = oddcnt - i;
                matrix_a[encode(i, j)][encode(i, j - 1)] = j;
                matrix_a[encode(i, j)][encode(i, j + 1)] = 5 - j;
            }
        }
        matrix_a[36][encode(oddcnt - 1, 0)] = oddcnt;
        matrix_a[36][encode(oddcnt, 1)] = 4;
        
        matcopy(fastpow[0], matrix_a);
        for (int i = 1; i <= 60; i++) {
            matmul(fastpow[i], fastpow[i - 1], fastpow[i - 1]);
        }
        for (int i = 0; i <= 36; i++) {
            for (int j = 0; j <= 36; j++) {
                if (i == j) {
                    matrix_b[i][j] = 1;
                } else {
                    matrix_b[i][j] = 0;
                }
            }
        }
        ll cur = 1;
        for (int i = 0; i <= 60; i++) {
            if (n & cur) {
                matmul(matrix_temp, matrix_b, fastpow[i]);
                matcopy(matrix_b, matrix_temp);
            }
            cur *= 2;
        }
        return matrix_b[36][0];
    }
    
    int main()
    {
        scanf("%lld%lld", &n, &p);
        /*int nval, pval;
        scanf("%d%d", &nval, &pval);
        n = nval;
        p = pval;*/
        ll ans = (calc(5) + 5 * calc(4) + 10 * calc(3)
                  + 10 * calc(2) + 5 * calc(1) + calc(0)) % p;
        printf("%lld", ans);
        return 0;
    }
    
    
    
  • 1

信息

ID
2035
难度
8
分类
(无)
标签
(无)
递交数
12
已通过
6
通过率
50%
上传者