【洛谷P4882】lty loves 96!

开始的时候看到这个题目有点懵逼,因为没仔细看条件,以为有几个条件是保证对于每一个abc
我们考虑,对于一个数字,只有最后两个加进去的才是有意义的,之前怎么摆最后只需要保留已经满不满足第三个大条件即可。所以我们可以设一个裸的状态dp[i][j][x][y][0/1]表示当前已经放了i位数,有j个9/6,第i位为y,i-1位为x,是否满足第三个条件的方案数。那么转移方程也比较显然了,这里就不再写转移方程,具体分析下情况。我们每次转移的时候枚举最后三位数。如果后三位数能满足条件,则能从非法转移到合法,否则只能从非法转移到非法。原本合法的一定转移过来。
注意,这个题目是认为倒数第三位为模数c的qwq

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int mo = 1e8;

int n, m, t;

struct in
{
    int a[55];
    void init(int x)
    {
        memset(a, 0, sizeof(a)), a[a[0] = 1] = x;
    }
}dp[2][51][10][10][2];

in operator + (in a, in b)
{
    int d = max(a.a[0], b.a[0]);
    for(ri i = 1; i <= d; i ++)
        a.a[i] += b.a[i], a.a[i + 1] += a.a[i] / mo, a.a[i] %= mo;
    while(a.a[d + 1] > 0)
        d ++, a.a[d + 1] += a.a[d] / mo, a.a[d] %= mo;
    a.a[0] = d; return a;
}

inline void print(in a)
{
    int mx = a.a[0]; printf("%d", a.a[mx]);
    for(ri i = mx - 1; i >= 1; i --)
        printf("%08d", a.a[i]);
    printf("\n");
}

inline bool check(int x)
{
    return x == 9 || x == 6;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    //freopen("qwq.out", "w", stdout);
    re(n), re(m);
    if(n == 1)
    {
        printf(m == 0 ? "9" : "2"); return 0;
    }
    else if(n == 2)
    {
        printf(m == 0 ? "90" : (m == 1 ? "34" : "4")); return 0;
    }
    for(ri i = 0; i < 10; i ++)
        for(ri j = 0; j < 10; j ++)
            dp[t][check(i) + check(j)][i][j][0].init(1);
    for(ri i = 3; i <= n; i ++)
    {
        t ^= 1;
        for(ri j = 0; j < i; j ++)
            for(ri x = 0; x < 10; x ++)
                for(ri y = 0; y < 10; y ++)
                    dp[t][j][x][y][0].init(0), dp[t][j][x][y][1].init(0); 
        for(ri j = 0; j < i; j ++)
            for(ri x = 0; x < 10; x ++)
                for(ri y = 0; y < 10; y ++)
                    for(ri z = 0; z < 10; z ++)
                    {
                        dp[t][check(z) + j][z][y][1] = dp[t][check(z) + j][z][y][1] + dp[t ^ 1][j][y][x][1];
                        if(check(x + y + z)
                        || (x && check((y * y + z * z) % x)))
                            dp[t][check(z) + j][z][y][1] = dp[t][check(z) + j][z][y][1] + dp[t ^ 1][j][y][x][0];
                        else
                            dp[t][check(z) + j][z][y][0] = dp[t][check(z) + j][z][y][0] + dp[t ^ 1][j][y][x][0];
                    }
    }
    in ans; ans.init(0);
    for(ri i = 1; i < 10; i ++)
        for(ri j = 0; j < 10; j ++)
            for(ri k = m; k <= n; k ++)
                ans = ans + dp[t][k][i][j][1];
    print(ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注