题目链接:BZOJ - 2326
题目分析
数据范围达到了 10^18 ,显然需要矩阵乘法了!
可以发现,向数字尾部添加一个数字 x 的过程就是 Num = Num * 10^k + x 。其中 k 是 x 的位数。
那么位数相同的数字用矩阵乘法处理就可以了。
[Num, x, 1] * [10^k, 0, 0] = [Num*10^k+x, x+1, 1]
[ 1, 0, 0]
[ 0, 1, 1]
枚举位数,做多次矩阵乘法。
其中两个整数相乘可能会爆 LL ,那么就用类似快速幂的慢速乘。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; typedef long long LL; LL n, Mod; struct Matrix
{
int x, y;
LL A[5][5];
void Clear() {
memset(A, 0, sizeof(A));
}
void SetXY(int a, int b) {
x = a; y = b;
}
} M0, M_Ans, M_t; LL MulNum(LL a, LL b) {
LL f = a, ret = 0;
while (b) {
if (b & 1) {
ret += f;
if (ret > Mod) ret %= Mod;
}
b >>= 1;
f <<= 1;
if (f > Mod) f %= Mod;
}
return ret;
} Matrix Mul(Matrix Ma, Matrix Mb) {
Matrix ret;
ret.SetXY(Ma.x, Mb.y);
ret.Clear();
for (int i = 1; i <= ret.x; ++i) {
for (int j = 1; j <= ret.y; ++j) {
for (int k = 1; k <= Ma.y; ++k) {
ret.A[i][j] += MulNum(Ma.A[i][k], Mb.A[k][j]);
ret.A[i][j] %= Mod;
}
}
}
return ret;
} Matrix Pow(Matrix Ma, LL b) {
Matrix f, ret;
f = Ma;
ret.SetXY(Ma.x, Ma.y);
ret.Clear();
for (int i = 1; i <= ret.x; ++i) ret.A[i][i] = 1;
while (b) {
if (b & 1) ret = Mul(ret, f);
b >>= 1;
f = Mul(f, f);
}
return ret;
} int main()
{
scanf("%lld%lld", &n, &Mod);
LL Temp, Ans;
M0.SetXY(1, 3);
M0.Clear();
M0.A[1][1] = 0; M0.A[1][2] = 1; M0.A[1][3] = 1;
M_t.SetXY(3, 3);
Temp = 1;
for (int i = 1; i <= 18; ++i) {
Temp *= 10ll;
if (Temp > n) break;
M_t.Clear();
M_t.A[1][1] = Temp;
M_t.A[2][1] = M_t.A[2][2] = M_t.A[3][2] = M_t.A[3][3] = 1;
M_t = Pow(M_t, Temp - Temp / 10);
M0 = Mul(M0, M_t);
}
M_t.Clear();
M_t.A[1][1] = Temp;
M_t.A[2][1] = M_t.A[2][2] = M_t.A[3][2] = M_t.A[3][3] = 1;
M_t = Pow(M_t, n - Temp / 10 + 1);
M0 = Mul(M0, M_t);
Ans = M0.A[1][1];
printf("%lld\n", Ans);
return 0;
}
[BZOJ 2326] [HNOI2011] 数学作业 【矩阵乘法】的更多相关文章
-
BZOJ 2326: [HNOI2011]数学作业(矩阵乘法)
传送门 解题思路 NOIp前看到的一道题,当时想了很久没想出来,NOIp后拿出来看竟然想出来了.注意到有递推\(f[i]=f[i-1]*poww[i]+i\),\(f[i]\)表示\(1-i\)连接起 ...
-
BZOJ 2326: [HNOI2011]数学作业( 矩阵快速幂 )
BZOJ先剧透了是矩阵乘法...这道题显然可以f(x) = f(x-1)*10t+x ,其中t表示x有多少位. 这个递推式可以变成这样的矩阵...(不会用公式编辑器...), 我们把位数相同的一起处理 ...
-
bzoj 2326: [HNOI2011]数学作业【dp+矩阵快速幂】
矩阵乘法一般不满足交换律!!所以快速幂里需要注意乘的顺序!! 其实不难,设f[i]为i的答案,那么f[i]=(f[i-1]w[i]+i)%mod,w[i]是1e(i的位数),这个很容易写成矩阵的形式, ...
-
bzoj 2326: [HNOI2011]数学作业
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #defin ...
-
[BZOJ2326] [HNOI2011] 数学作业 (矩阵乘法)
Description Input Output Sample Input Sample Output HINT Source Solution 递推式长这样:$f[n]=f[n-1]*10^k+n$ ...
-
【bzoj2326】[HNOI2011]数学作业 矩阵乘法
题目描述 题解 矩阵乘法 考虑把相同位数的数放到一起处理: 设有$k$位的数为$[l,r]$,那么枚举从大到小的第$i$个数(即枚举$r-i+1$),考虑其对$Concatenate(l..r)$的贡 ...
-
BZOJ-2326 数学作业 矩阵乘法快速幂+快速乘
2326: [HNOI2011]数学作业 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1564 Solved: 910 [Submit][Statu ...
-
[HNOI2011]数学作业 --- 矩阵优化
[HNOI2011]数学作业 题目描述: 小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题: 给定正整数 N 和 M ,要求计算\(Concatenate(1..N)\; Mod\; ...
-
【BZOJ2326】【HNOI2011】数学作业 [矩阵乘法][DP]
数学作业 Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss] Description Input 输入文件只有一行为用空 ...
随机推荐
-
Sender
多个对象用同一个方法的时候,想对多个对象分别操作的话就用Sender. BackGroundWorker worker1 = sender as BackGroundWork. 分别去取当前的对象 ...
-
Unity3d 查找所选的是否引用过某资源
一.使用方式: 1.选择要被查找的资源,右键->Find Reference 2.把资源拽入Res,点Find 3.输出结果见Console //代码 using UnityEngine; us ...
-
DateTools时间插件
import java.text.DateFormat;import java.text.ParsePosition;import java.text.SimpleDateFormat;import ...
-
玩转Android---事件监听篇---第2篇
事件监听篇---第二篇 下面是各种常用控件的事件监听的使用 ①EditText(编辑框)的事件监听---OnKeyListener ②RadioGroup.RadioButton(单选按钮)的事件监听 ...
-
docker exec 系统找不到指定的路径。
相关问题和答案 >docker exec -it a1 echo "hello..." > /var/www/html/index.html 系统找不到指定的路径. & ...
-
python常用模块之re模块(正则)
python种的re模块常用的5种方法,分别是re.match re.search re.findall re.split re.sub. 在介绍五种方法之前,需要介绍一下正则的基础. . ...
-
测试教程网.unittest教程.5. 实例: 找出所有是弱密码的用户
From: http://www.testclass.net/pyunit/test_example_3/ 背景 当我们的测试数据是下面这些的时候,我们的用例是有问题的. [ {"name& ...
-
WeakReference与SoftReference
WeakReference与SoftReference都可以用来保存对象的实例引用,这两个类与垃圾回收有关. WeakReference是弱引用,其中保存的对象实例可以被GC回收掉.这个类通常用于在某 ...
-
用 Java 实现一个快速排序算法
快速排序是排序算法中效率最高的一种,它是利用递归的原理,把数组无限制的分成两个部分,直到所有数据都排好序为止. 快速排序是对冒泡排序的一种改进.它的基本思想是通过一趟排序将要排序的数据分 ...
-
c++ 栈(顺序表)
栈可以用顺序表(数组)也可以用链表来储存内容,本文采用顺序表(数组)来保存内部元素.代码如下: 1 #include <iostream> 2 using namespace std; ...