首页 > 代码库 > BZOJ2326 [HNOI2011]数学作业
BZOJ2326 [HNOI2011]数学作业
首先,列方程
我们定义s[i] = 10 ^ ((int) log(i))
于是,f[i] = (f[i - 1] * s[i] + i) % p
反正总之就是个沙茶递推
然后我们来看优化。。。怎么感觉像矩阵乘法呢?
发现要按照log(i)即i的位数分类讨论,在相同位数的时候令矩阵为
s[i] 0 0
1 1 0
0 1 1
即可
1 /************************************************************** 2 Problem: 2326 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:16 ms 7 Memory:808 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 12 using namespace std;13 typedef long long ll;14 15 ll n, p;16 17 struct Matrix {18 ll x[4][4];19 20 Matrix (int X) {21 int i, j;22 for (i = 1; i <= 3; ++i)23 for (j = 1; j <= 3; ++j)24 if (i == j) x[i][j] = X;25 else x[i][j] = 0;26 }27 28 ll* operator [] (int X) {29 return x[X];30 }31 };32 33 inline void operator *= (Matrix &x, Matrix y) {34 int i, j, k;35 Matrix res(0);36 for (i = 1; i <= 3; ++i)37 for (j = 1; j <= 3; ++j)38 for (k = 1; k <= 3; ++k)39 (res[i][j] += x[i][k] * y[k][j]) %= p;40 x = res;41 };42 43 Matrix pow(Matrix x, ll y) {44 Matrix res(1);45 while (y) {46 if (y & 1) res *= x;47 x *= x, y >>= 1;48 }49 return res;50 }51 52 int main() {53 ll i;54 Matrix ans(1), a(0);55 scanf("%lld%lld", &n, &p);56 a[1][1] = 10 % p, a[2][1] = a[2][2] = a[3][2] = a[3][3] = 1;57 for (i = 10; i <= n; i *= 10, a[1][1] = i % p)58 ans *= pow(a, i - i / 10);59 ans *= pow(a, n - i / 10 + 1);60 printf("%lld\n", (ans[2][1] + ans[3][1]) % p);61 return 0;62 }
BZOJ2326 [HNOI2011]数学作业
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。