BZOJ-3231 [SDOI2008]递归数列
2024-09-29 18:00:21
转成矩阵连乘后,矩阵快速幂加速解决。
一开始没把需要longlong的变量补全。。而且没初始化2333
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#define rep(i, l, r) for(int i=l; i<=r; i++)
#define clr(x, c) memset(x, c, sizeof(x))
#define maxn 20
#define ll long long
#define l(x) x*2
#define r(x) x*2+1
using namespace std;
inline ll read()
{
ll x=0, f=1; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while (isdigit(ch)) x=x*10+ch-'0', ch=getchar();
return x*f;
}
int n;
ll q;
ll m[maxn][maxn], m2[maxn][maxn], b[maxn], c[maxn], a[maxn], a2[maxn]; ll Query(ll k)
{
if (k<=n) {ll now=0; rep(i, 1, k) now+=b[i]; return now;} else k-=n;
clr(m, 0);
rep(i, 1, n) m[n][n+1-i]=m[n+1][n+1-i]=c[i];
rep(i, 1, n-1) m[i][i+1]=1; m[n+1][n+1]=1;
rep(i, 1, n+1) a[i]=b[i];
while (k)
{
if (k&1)
{
clr(a2, 0);
rep(i, 1, n+1) rep(j, 1, n+1) a2[i]=(a2[i]+a[j]*m[i][j])%q;
rep(i, 1, n+1) a[i]=a2[i];
}
clr(m2, 0);
rep(i, 1, n+1) rep(j, 1, n+1) rep(o, 1, n+1) m2[i][j]=(m2[i][j]+m[i][o]*m[o][j])%q;
rep(i, 1, n+1) rep(j, 1, n+1) m[i][j]=m2[i][j];
k=k>>1;
}
return a[n+1];
} int main()
{
n=read();
rep(i, 1, n) b[i]=read(), b[n+1]+=b[i];
rep(i, 1, n) c[i]=read();
ll x=read(), y=read(); q=read();
rep(i, 1, n) b[i]%=q, c[i]%=q;
printf("%lld", (Query(y)-Query(x-1)+2*q)%q);
return 0;
}
最新文章
- jQuery常用的插件及功能汇总-持续
- Winform图片拖拽与缩放
- java Integer和int的拆箱与装箱
- 登陆界面Login
- android上让我放弃使用wstring来操作中英文字符串 转
- /lib64/libc.so.6: version `GLIBC_2.14&#39; not found问题
- cocos2d-x for android:SimpleGame分析
- .woff 文件404,配置到web.config
- Spring Boot使用redis做数据缓存
- Delphi中methodaddress的汇编代码解析
- JAVA基础--super关键字
- yum命令被锁 Existing lock /var/run/yum.pid
- js设置,获取,删除Cookie
- 基于Redis的分布式锁两种实现方式
- Promise(一)
- 公司项目接触到了FormData,总结一下
- 701 C. They Are Everywhere
- android 6 中init.rc的生成过程【转】
- 2018.09.01 09:08 Genesis
- windows及linux环境下永久修改pip镜像源的方法