[BZOJ 2326] [HNOI2011] 数学作业 【矩阵乘法】

时间:2022-02-27 06:56:37

题目链接: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] 数学作业 【矩阵乘法】的更多相关文章

  1. BZOJ 2326&colon; &lbrack;HNOI2011&rsqb;数学作业&lpar;矩阵乘法&rpar;

    传送门 解题思路 NOIp前看到的一道题,当时想了很久没想出来,NOIp后拿出来看竟然想出来了.注意到有递推\(f[i]=f[i-1]*poww[i]+i\),\(f[i]\)表示\(1-i\)连接起 ...

  2. BZOJ 2326&colon; &lbrack;HNOI2011&rsqb;数学作业&lpar; 矩阵快速幂 &rpar;

    BZOJ先剧透了是矩阵乘法...这道题显然可以f(x) = f(x-1)*10t+x ,其中t表示x有多少位. 这个递推式可以变成这样的矩阵...(不会用公式编辑器...), 我们把位数相同的一起处理 ...

  3. bzoj 2326&colon; &lbrack;HNOI2011&rsqb;数学作业【dp&plus;矩阵快速幂】

    矩阵乘法一般不满足交换律!!所以快速幂里需要注意乘的顺序!! 其实不难,设f[i]为i的答案,那么f[i]=(f[i-1]w[i]+i)%mod,w[i]是1e(i的位数),这个很容易写成矩阵的形式, ...

  4. bzoj 2326&colon; &lbrack;HNOI2011&rsqb;数学作业

    #include<cstdio> #include<iostream> #include<cstring> #include<cmath> #defin ...

  5. &lbrack;BZOJ2326&rsqb; &lbrack;HNOI2011&rsqb; 数学作业 &lpar;矩阵乘法&rpar;

    Description Input Output Sample Input Sample Output HINT Source Solution 递推式长这样:$f[n]=f[n-1]*10^k+n$ ...

  6. 【bzoj2326】&lbrack;HNOI2011&rsqb;数学作业 矩阵乘法

    题目描述 题解 矩阵乘法 考虑把相同位数的数放到一起处理: 设有$k$位的数为$[l,r]$,那么枚举从大到小的第$i$个数(即枚举$r-i+1$),考虑其对$Concatenate(l..r)$的贡 ...

  7. BZOJ-2326 数学作业 矩阵乘法快速幂&plus;快速乘

    2326: [HNOI2011]数学作业 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1564 Solved: 910 [Submit][Statu ...

  8. &lbrack;HNOI2011&rsqb;数学作业 --- 矩阵优化

    [HNOI2011]数学作业 题目描述: 小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题: 给定正整数 N 和 M ,要求计算\(Concatenate(1..N)\; Mod\; ...

  9. 【BZOJ2326】【HNOI2011】数学作业 &lbrack;矩阵乘法&rsqb;&lbrack;DP&rsqb;

    数学作业 Time Limit: 10 Sec  Memory Limit: 128 MB[Submit][Status][Discuss] Description Input 输入文件只有一行为用空 ...

随机推荐

  1. Sender

    多个对象用同一个方法的时候,想对多个对象分别操作的话就用Sender.  BackGroundWorker worker1 = sender as BackGroundWork.  分别去取当前的对象 ...

  2. Unity3d 查找所选的是否引用过某资源

    一.使用方式: 1.选择要被查找的资源,右键->Find Reference 2.把资源拽入Res,点Find 3.输出结果见Console //代码 using UnityEngine; us ...

  3. DateTools时间插件

    import java.text.DateFormat;import java.text.ParsePosition;import java.text.SimpleDateFormat;import ...

  4. 玩转Android---事件监听篇---第2篇

    事件监听篇---第二篇 下面是各种常用控件的事件监听的使用 ①EditText(编辑框)的事件监听---OnKeyListener ②RadioGroup.RadioButton(单选按钮)的事件监听 ...

  5. docker exec 系统找不到指定的路径。

    相关问题和答案 >docker exec -it a1 echo "hello..." > /var/www/html/index.html 系统找不到指定的路径. & ...

  6. python常用模块之re模块(正则)

    python种的re模块常用的5种方法,分别是re.match   re.search  re.findall  re.split  re.sub. 在介绍五种方法之前,需要介绍一下正则的基础. . ...

  7. 测试教程网&period;unittest教程&period;5&period; 实例&colon; 找出所有是弱密码的用户

    From: http://www.testclass.net/pyunit/test_example_3/ 背景 当我们的测试数据是下面这些的时候,我们的用例是有问题的. [ {"name& ...

  8. WeakReference与SoftReference

    WeakReference与SoftReference都可以用来保存对象的实例引用,这两个类与垃圾回收有关. WeakReference是弱引用,其中保存的对象实例可以被GC回收掉.这个类通常用于在某 ...

  9. 用 Java 实现一个快速排序算法

           快速排序是排序算法中效率最高的一种,它是利用递归的原理,把数组无限制的分成两个部分,直到所有数据都排好序为止. 快速排序是对冒泡排序的一种改进.它的基本思想是通过一趟排序将要排序的数据分 ...

  10. c&plus;&plus; 栈(顺序表)

    栈可以用顺序表(数组)也可以用链表来储存内容,本文采用顺序表(数组)来保存内部元素.代码如下:  1 #include <iostream> 2 using namespace std; ...