hdu 6395 Sequence (简单矩乘)
2024-09-29 11:37:43
P/n大多数情况是不变的, 取值只有$O(\sqrt{P})$种, 可以用$p/(p/i)$跳过重复的值, 复杂度$O(logn\sqrt{P})$
要注意
- P跟模数P有冲突
- 要特判p/i==0和p/(p/i)>n的情况
- 题目给的$CF_{n-2}+DF_{n-1}$, 写矩阵要D在前C在后
//fn = D C x fn-1 //fn-1 1 0 0 fn-2 //1 0 0 1 1 struct Mat { ll v[4][4]; Mat() {memset(v, 0, sizeof v);} Mat operator * (const Mat& b) const { Mat c; REP(k,1,3)REP(i,1,3)REP(j,1,3) { c.v[i][j] = (v[i][k]*b.v[k][j]+c.v[i][j])%P; } return c; } Mat operator ^ (ll nn) { Mat b, a=*this; REP(i,1,3) b.v[i][i]=1; while(nn) { if(nn&1LL) b=b*a; nn>>=1LL,a=a*a; } return b; } }; void work() { int A, B, C, D, p, n; scanf("%d%d%d%d%d%d", &A, &B, &C, &D, &p, &n); if (n==1) return printf("%d\n",A),void(); if (n==2) return printf("%d\n",B),void(); Mat r; r.v[1][1]=r.v[2][2]=r.v[3][3]=1; REP(i,3,n) { Mat g; g.v[1][1]=D,g.v[1][2]=C,g.v[2][1]=g.v[3][3]=1,g.v[1][3]=p/i; if (p<i) { r = (g^(n-i+1))*r; break; } int k = p/(p/i); if (k<=n) r = (g^(k-i+1))*r; else r = (g^(n-i+1))*r; i = k; } ll ans = r.v[1][1]*B%P+r.v[1][2]*A%P+r.v[1][3]; printf("%lld\n", ans%P); } int main() { int t; scanf("%d", &t); while (t--) work(); }
最新文章
- 深入理解计算机系统(2.8)---浮点数的舍入,Java中的舍入例子以及浮点数运算(重要)
- 【BZOJ-3572】世界树 虚树 + 树形DP
- 如何安装mysql服务
- ios 手动添加mapview
- Day One studying english
- 玩转Android Camera开发(一):Surfaceview预览Camera,基础拍照功能完整demo
- 关于项目中遇到的NullPointerException异常时处理手段
- C++ trivial和non-trivial构造函数及POD类型(转)
- Java 8十个lambda表达式案例
- js计算日期天数差-2013-9-26
- 给UIImage添加蒙版
- Android 开发笔记-Eclipse中文乱码
- IOS开发之路三(XML解析之GDataXML的使用)
- 【JVM命令系列】javap
- Mycat 分片规则详解--ER关系表分片
- php之IP
- 程序员从技术开发到项目管理PM--思维转变
- ssm 连接两个数据库
- a no-risk path to IEEE P1687
- 【Ray Tracing in One Weekend 超详解】 光线追踪1-4