设 \(f(n,k)\) 为用 \(k\) 张牌组成 \(n\) 的方案数,则
\(f(n,k)=C_4^0 f(n−k,k)+C_4^1 f(n−k,k−1)+C_4^2f(n−k,k−2)+C_4^3 f(n−k,k−3)+ C_4^4 f(n−k,k−4)\)
也就是考虑这 \(k\) 张牌里有多少张 \(1\) ,倘若有 \(x\) 张,则剩下的(没有 \(1\))组成的数是 \(n-x\) 。
又因为这里边没有 \(1\) ,所以可以和每张牌权值都 \(-1\) 后的情况相对应,等价于 \(k-x\) 张牌(可以有 \(1\))组成 \(n-k\)
发现这样的 \(DP\) 是二维的,我们把这二维展开成一维的转移,用矩阵优化一下就 \(ok\) 了
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
int n, k, ans;
const int N = 105, mod = 1e9 + 9;
int C4[7] = {1, 4, 6, 4, 1};
int f[12][12];
struct ju
{
LL v[N][N];
friend ju operator *(const ju &a, const ju &b)
{
ju c; memset(c.v, 0, sizeof(c.v));
for (int i = 1; i <= 100; ++i)
for (int j = 1; j <= 100; ++j)
for (int k = 1; k <= 100; ++k)
(c.v[i][j] += a.v[i][k] * b.v[k][j]) %= mod;
return c;
}
} A, B, base;
ju ksm(ju a, LL b)
{
ju res; memset(res.v, 0, sizeof(res.v));
for (int i = 1; i <= 100; ++i)res.v[i][i] = 1;
for (; b; b >>= 1, a = a * a)
if (b & 1)res = res * a;
return res;
}
void YYCH()
{
f[0][0] = 1;
for (int i = 1; i <= 10; ++i)
for (int j = 1; j <= i; ++j)
for (int k = 0; k <= min(j, 4); ++k)
f[i][j] += f[i - j][j - k] * C4[k];
int cnt = 0;
for (int i = 10; i >= 1; --i)for (int j = 10; j >= 1; --j)A.v[1][++cnt] = f[i][j];
for (int i = 1; i <= 10; ++i)
for (int j = 0; j <= min(i - 1, 4); ++j)
base.v[i * 10 - (i - j) + 1][10 - i + 1] = C4[j];
for (int i = 11; i <= 100; ++i)base.v[i - 10][i] = 1;
}
int main()
{
YYCH();
while (scanf("%d%d", &n, &k) && n && k)
{
ans = 0;
if (n <= 10)
{
for (int i = 1; i <= k; ++i)ans += f[n][i];
}
else
{
B = A * ksm(base, n - 10);
for (int i = 1; i <= k; ++i)(ans += B.v[1][10 - i + 1]) %= mod;
}
printf("%d\n", ans);
}
return 0;
}