题目链接:uva 11651 - Krypton
Number System
题目大意:给定进制base,和分数score,求在base进制下,有多少个数的值为score,要求不能有连续相同的数字以及前导0.计算一个数的值即为相邻两位数的平方差和。
解题思路:因为score很大,所以直接dp肯定超时,但是即使对于base=6的情况,每次新添一个数score最大增加25(0-5),所以用dp[i][j]预处理出base平方以内的总数,然后用矩阵快速幂计算。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
const int maxn = 155;
const ll MOD = 1ll<<32;
struct Mat {
int r, c;
ll arr[maxn][maxn];
Mat (int r = 0, int c = 0) { set(r, c); }
void set(int r, int c) {
this->r = r;
this->c = c;
memset(arr, 0, sizeof(arr));
}
Mat operator * (const Mat& u) {
Mat ret(r, u.c);
for (int k = 0; k < c; k++) {
for (int i = 0; i < r; i++) {
if (arr[i][k] == 0)
continue;
for (int j = 0; j < u.c; j++)
ret.arr[i][j] = (ret.arr[i][j] + arr[i][k] * u.arr[k][j]) % MOD;
}
}
return ret;
}
};
int base, N;
ll dp[maxn][maxn], score;
void init () {
scanf("%d%llu", &base, &score);
N = (base-1) * (base-1);
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= N; i++)
dp[0][i] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < base; j++) {
for (int k = 0; k < base; k++) {
int f = (j - k) * (j - k);
if (i + f > N || f == 0)
continue;
dp[i+f][j] = (dp[i+f][j] + dp[i][k]) % MOD;
}
}
}
}
Mat change () {
Mat ret(N*base, 1);
for (int i = 1; i <= N; i++)
for (int j = 0; j < base; j++)
ret.arr[(i-1)*base+j][0] = dp[i][j];
return ret;
}
Mat build () {
int n = N * base;
Mat x(n, n);
for (int i = base; i < n; i++)
x.arr[i-base][i] = 1;
for (int i = 0; i < base; i++) {
for (int j = 0; j < base; j++) {
if (i == j)
continue;
int k = N - (i-j) * (i-j);
x.arr[(N-1)*base+i][k*base+j] = 1;
}
}
return x;
}
Mat pow_mat (Mat ret, int n) {
Mat x = build();
while (n) {
if (n&1)
ret = x * ret;
x = x * x;
n >>= 1;
}
return ret;
}
ll solve () {
ll ans = 0;
if (score <= N) {
for (int i = 1; i < base; i++)
ans = (ans + dp[score][i]) % MOD;
return ans;
}
Mat ret = change();
ret = pow_mat(ret, score-N);
for (int i = 1; i < base; i++)
ans = (ans + ret.arr[(N-1)*base+i][0]) % MOD;
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
init();
printf("Case %d: %llu\n", kcas, solve());
}
return 0;
}
分享到:
相关推荐
apk文件 kodi-17.6-Krypton-arm64-v8a(电视直播视频)apk文件 kodi-17.6-Krypton-arm64-v8a(电视直播视频)apk文件 kodi-17.6-Krypton-arm64-v8a(电视直播视频)apk文件 kodi-17.6-Krypton-arm64-v8a(电视直播...
pvr.iptvsimple
资源来自pypi官网。 资源全名:python-heideltime-krypton-0.0.1.tar.gz
开源项目-krypton97-go-relay-starter-kit.zip,Minimalist go-relay-starter-kit ready to use out of the box!
PVR真空泵选型手册,欢迎需要的各位下载查阅。希望可以帮到大家
kodi默认使用的英文输入法,要打汉字需设置成百度输入法
C#winform第三方控件库KryptonSuite4.4.0-C#.rar,利用该控件库可以做出比利用软件自身控件更漂亮的界面
Enigma2 PVR 用于Enigma2 PVR客户端插件。 Enigma2是一个开放源代码的电视接收器/ DVR平台,基于Linux的固件(OS映像)可以加载到来自不同制造商的许多基于Linux的机顶盒(卫星,地面,电缆或它们的组合)上。...
ComponentFactory krypton Toolkit 免费的48个windows控件
Krypton.Toolkit 基于WinForm的皮肤控件,很实用,很强大
Cracked latest Krypton ComponentFactory Toolkit 4.4.0 1- Replace all dll's in <intallpath>\Bin\ and <intallpath>\Bin\PublisherSigned 2- Run register.bat from <intallpath>\Bin\
ComponentFactory.Krypton.Design
免费用户界面控件 Krypton Toolkit,与DotNetBar差不多,不过是免费的啊
软件名称:Krypton匿名浏览器:Krypton Anonymous APK名称:co.kr36.krypton.x 最新版本:101-903 支持ROM:4.1及更高版本 界面语言:英文软件 软件大小:19.77 M 开发者: Kr36 LLC 一个永远安全和保护个人隐私的...
您可以从此处下载最新的JAR文件,并使用java -jar Krypton-VERSION.jar运行它。如果您有任何疑问,请随时在我们的Discord服务器中提问。 或者,如果您愿意,可以使用git clone ...
$ cd KryPtoN-Music-Bot $ pip install -r requirements.txt 设置config configs.py并进行编辑 执行! $ python3 -m krypton 赫鲁库 生成字符串会话[重要] 下载此文件 $ pip3 install pyrogram TgCrypto $ python...
免费用户界面控件 Krypton Toolkit,与DotNetBar差不多,不过是免费的啊
大家看清除,可是“Krypton.Suite”哦!!!
Component Factory krypton Toolkit 4.3.1.0 免费的48个windows控件
资源来自pypi官网。 资源全名:Krypton-0.1.2.tar.gz