首页 > 代码库 > UVA 11651 - Krypton Number System(DP+矩阵快速幂)
UVA 11651 - Krypton Number System(DP+矩阵快速幂)
UVA 11651 - Krypton Number System
题目链接
题意:给一个进制base,一个分数score求该进制下,有多少数满足一下条件:
1、没有连续数字
2、没有前导零
3、分数为score,分数的计算方式为相邻数字的平方差的和
思路:先从dp入手,dp[i][j]表示组成i,最后一个数字为j的种数,然后进行状态转移,推出前面一步能构成的状态,也就是到dp[(b - 1) * (b - 1)][x]。
然后可以发现后面的状态,都可以由前面这些状态统一转移出来,这样就可以利用矩阵快速幂进行优化,时间复杂度为O(n^3log(score))
这题矩阵快速幂姿势不够优美还会超时,矩阵相乘时候需要优化
代码:
#include <cstdio> #include <cstring> typedef unsigned long long ll; const int N = 155; const ll MOD = (1ULL<<32); int n; struct Mat { ll v[N][N]; Mat() { memset(v, 0, sizeof(v)); } void init() { memset(v, 0, sizeof(v)); } void init_one() { memset(v, 0, sizeof(v)); for (int i = 0; i < n; i++) v[i][i] = 1; } Mat operator * (Mat c) { Mat ans; for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { if (!v[i][k]) continue; for (int j = 0; j < n; j++) ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j] % MOD) % MOD; } } return ans; } } B; Mat pow_mod(Mat x, int k) { Mat ans; ans.init_one(); while (k) { if (k&1) ans = ans * x; x = x * x; k >>= 1; } return ans; } ll dp[40][10], A[N]; int t, b, s, m; void init() { scanf("%d%d", &b, &s); m = (b - 1) * (b - 1); n = m * b; memset(dp, 0, sizeof(dp)); for (int i = 0; i < b; i++) dp[0][i] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j < b; j++) { for (int k = 0; k < b; k++) { if (k == j) continue; int tmp = (k - j) * (k - j); if (i - tmp < 0) continue; dp[i][j] = (dp[i][j] + dp[i - tmp][k]) % MOD; } } } } void build() { B.init(); for (int i = b; i < n; i++) B.v[i][i - b] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j < b; j++) { for (int k = 0; k < b; k++) { if (j == k) continue; if (i + (k - j) * (k - j) == m + 1) { B.v[(i - 1) * b + j][n - b + k] = 1; } } } } } ll solve() { ll ans = 0; if (s <= m) { for (int i = 1; i < b; i++) ans = (ans + dp[s][i]) % MOD; return ans; } for (int i = 1; i <= m; i++) { for (int j = 0; j < b; j++) A[(i - 1) * b + j] = dp[i][j]; } build(); B = pow_mod(B, s - m); for (int i = n - b + 1; i < n; i++) { for (int j = 0; j < n; j++) ans = (ans + A[j] * B.v[j][i] % MOD) % MOD; } return ans; } int main() { int cas = 0; scanf("%d", &t); while (t--) { init(); printf("Case %d: %llu\n", ++cas, solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。