开始的时候看到这个题目有点懵逼,因为没仔细看条件,以为有几个条件是保证对于每一个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;
}