![【BZOJ2326】【HNOI2011】数学作业 [矩阵乘法][DP] 【BZOJ2326】【HNOI2011】数学作业 [矩阵乘法][DP]](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
数学作业
Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
Input
输入文件只有一行为用空格隔开的两个正整数N和M。
Output
输出仅包含一个非负整数,表示Concatenate(1~N) MOD M的值。
Sample Input
12345678910 1000000000
Sample Output
345678910
HINT
1<=N<=10^8 , 1<=M<=10^9
Main idea
给定一个n,m,创造一个数字顺序连接1~n,输出这个数对m取模的值。
Solution
n<=10^18,排除找规律的可能性,立马想到了用矩阵乘法优化DP,令f[i]表示1~i的值,那么:
然后我们只要推出矩阵即可,轻松想到了:
然后分段矩乘得到答案。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std; const int ONE=; long long n,MOD;
long long a[ONE][ONE],b[ONE][ONE];
long long Index; void Mul(long long a[ONE][ONE],long long b[ONE][ONE],long long ans[ONE][ONE])
{
long long jilu[ONE][ONE];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
jilu[i][j]=;
for(int k=;k<=;k++)
jilu[i][j]=(jilu[i][j] + a[i][k]*b[k][j]%MOD) % MOD;
} for(int i=;i<=;i++)
for(int j=;j<=;j++)
ans[i][j]=jilu[i][j];
} void Matrix(long long a[ONE][ONE],long long b[ONE][ONE],long long t)
{
while(t)
{
if(t&) Mul(a,b,a);
Mul(b,b,b);
t>>=;
}
} int main()
{
cin>>n>>MOD;
a[][]=; long long len=;
for(;;)
{
len*=;
memset(b,,sizeof(b));
for(int i=;i<=;i++)
{
for(int j=;j<=i;j++)
b[i][j]=;
}
b[][]=len % MOD; if(len<=n) Index=len-len/;
else Index=n-len/+;
Matrix(a,b,Index);
if(len>n) break;
} printf("%lld",a[][]);
}