本文主要是介绍UVA 12297 Super Poker(矩阵快速幂),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
想到了一个递推式
f(n,k)=f(n−k,k)+f(n−k,k−1)∗4+f(n−k,k−2)∗6+f(n−k,k−3)∗4+f(n−k,k−4)
这里 f(n,k) 表示用k张牌组成和为N的方案数,在递推的时候考虑一共有多少张1。
①考虑有0张1:这时就相当于用k张没有任何限制的牌组成和为 n−k ,然后将每张牌的点数+1,这样自然就没有1了,这部分的方案数是 f(n−k,k) ;
②考虑有1张1:这时就相当于用k-1张没有任何限制的牌组成和为n-k,然后将每张牌的点数+1,这样也就没有1了,这时总和是n-1,再从4张1种任选一张1就可以使总和为n,这样就恰好用了k张牌,而且k张牌中只有1个1,这部分的方案数是 f(n−k,k−1)∗C(4,1) ,也就是 f(n−k,k−1)∗4 ;
③考虑有2张1:……(剩下的情况类似,就不再赘述了)。
但是N比较大,从而使用矩阵快速幂加速计算
矩阵的构造方法比较麻烦,我的思路是这样的
一般的矩阵快速幂都是用来优化一维的递推式,但是我们现在的是二维的递推式,但是因为二维的递推式的列数是相同的,所以我们可以考虑将 f(n,k)…f(n,0)、f(n−1,k)…f(n−1,0)…f(0,0) 这样展开来,从而维持了一维的特性。
同时呢,因为转移的时候是从 f(n−k,∗∗)→f(n,k) 那么我们的快速幂至少要有从最开始到第k项的值
那么这么一想我们就可以构造转移了,只要控制好转移的距离就行了。
//By LH
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;
const int MOD = 1e9+9;
const int d[5] = {1, 4, 6, 4, 1};int N, K;
LL ans;
LL f[15][15];
LL a[115][115], b[115][115], c[115][115];void calc()
{memset(f[0], 0, sizeof(f[0]));f[0][0] = 1;for(int i = 1; i <= 10; i ++)for(int j = 1; j <= 10; j ++){f[i][j] = 0;if(i >= j){for(int k = 0; k < 5; k ++)if (j - k >= 0) f[i][j] = (f[i][j] + d[k] * f[i - j][j - k]) % MOD;}}
}int main()
{calc();while (scanf("%d %d", &N, &K) != EOF){if (N+K == 0) break;ans = 0;if(N <= 10){for(int i = 1; i <= K; i ++)ans = (ans + f[N][i]) % MOD;printf("%lld\n", ans);continue;}memset(a, 0, sizeof(a));for(int i = 0; i < K; i++)for(int j = 0; j <= K; j++)a[i * (K + 1) + j][0] = f[K - 1 - i][j];memset(b, 0, sizeof(b));for(int j = 1; j <= K; j++){for(int k = 0; k < 5; k++)if (j-k >= 0) b[j][(j - 1) * (K + 1) + j - k] = d[k];}for(int i = 1; i < K; i ++)for(int j = 0; j <= K; j ++)b[i * (K + 1) + j][(i - 1) * (K + 1) + j] = 1;int tmp = N-K+1;while (tmp){if (tmp&1){memset(c, 0, sizeof(c));for (int i = 0; i < K*(K+1); i++)for (int j = 0; j < K*(K+1); j++)for (int k = 0; k < K*(K+1); k++)c[i][j] = (c[i][j] + b[i][k]*a[k][j])%MOD;for (int i = 0; i < K*(K+1); i++)for (int j = 0; j < K*(K+1); j++) a[i][j] = c[i][j];}memset(c, 0, sizeof(c));for (int i = 0; i < K*(K+1); i++)for (int j = 0; j < K*(K+1); j++)for (int k = 0; k < K*(K+1); k++)c[i][j] = (c[i][j] + b[i][k]*b[k][j])%MOD;for (int i = 0; i < K*(K+1); i++)for (int j = 0; j < K*(K+1); j++) b[i][j] = c[i][j];tmp >>= 1;}for (int i = 1; i <= K; i++) ans = (ans+a[i][0])%MOD;printf("%lld\n", ans);}return 0;
}
这篇关于UVA 12297 Super Poker(矩阵快速幂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!