正解:矩阵快速幂

解题报告:

我永远喜欢loj!

一看到这个就应该能想到矩阵快速幂?

然后就考虑转移式,发现好像直接想不好想,,,主要的问题在于这个*$i$,就很不好搞$QAQ$

其实不难想到,$\sum_{i=1}^{n}a_i\cdot(n-i)$这样一个式子是可以在矩阵快速幂中推出来的(类似这个形式的都可,,,就随着编号递增系数递减这样子$QwQ$

具体来说就是表示成$\sum_{i=1}^{n}\sum_{j=1}^{i}a_j$,就欧克辣(具体实现后面港,,,

但是问题在于,它是$\sum_{i=1}^{n}a_i\cdot i$这样的,就随着编号递增系数递增这样子的$QwQ$

那显然就想到,变形嘛,就变成$\sum_{i=1}^{n}a_i\cdot n-\sum_{i=1}^{n}a_i\cdot(n-i)$这样子

然后就做完辣,,,?

剩下的就是考虑怎么表示出$\sum_{i=1}^{n}a_i$和$\sum_{i=1}^{n}a_i\cdot(n-i)$辣

对于第一个的话,可以考虑$\begin{bmatrix}\sum_{j=1}^{i-1} f_i \\ f_i\\ f_{i-1}\end{bmatrix}$$\cdot$$\begin{bmatrix}1 & 1 & 0\\ 0 & 1 & 1\\ 0 & 1 & 0\end{bmatrix}$,就欧克辣

然后第二个就差不多的方法,再加一维就好,$\begin{bmatrix}\sum _{j=1}^{i-1}\sum_{k=1}^{j}f_k\\ \sum_{j=1}^{i}f_j\\ f_{i+1}\\ f_{i}\end{bmatrix}$$\cdot$$\begin{bmatrix}1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 1\\0 & 0 & 1 & 0\end{bmatrix}$

欧克做完辣,,,

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

int n,mod;

struct matrix{int mat[][];il void clr(){memset(mat,,sizeof(mat));}}e1,e2,fib;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il matrix multi(matrix gd,matrix gs)

{

    matrix ret;ret.clr();

    rp(i,,)

        rp(j,,)

            rp(k,,)ret.mat[i][j]=(ret.mat[i][j]+gd.mat[i][k]*gs.mat[k][j]%mod)%mod;

    return ret;

}

il matrix power_1(ri x)

{matrix ret;ret.clr();ret.mat[][]=;while(x){if(x&)ret=multi(ret,e1);e1=multi(e1,e1);x>>=;}return ret;}

il matrix power_2(ri x)

{matrix ret;ret.clr();ret.mat[][]=;while(x){if(x&)ret=multi(ret,e2);e2=multi(e2,e2);x>>=;}return ret;}

namespace sub1

{

    il void main()

    {

        int fib1=,fib2=,as=;

        rp(i,,n){as=(as+1ll*fib1*i%mod)%mod;fib2+=fib1;fib1=fib2-fib1;if(fib2>=mod)fib2-=mod;}

        printf("%lld\n",as);

    }

}

main()

{

//    freopen("fib.in","r",stdin);freopen("fib.out","w",stdout);

    n=read();mod=read();

//    if(n<=100)return sub1::main(),0;

    e1.clr();e1.mat[][]=;e1.mat[][]=;e1.mat[][]=;e1.mat[][]=;e1.mat[][]=;

    e2.clr();e2.mat[][]=;e2.mat[][]=;e2.mat[][]=;e2.mat[][]=;e2.mat[][]=;e2.mat[][]=;e2.mat[][]=;

    matrix as1=power_1(n),as2=power_2(n);

    printf("%lld\n",((as1.mat[][]*n%mod-as2.mat[][])%mod+mod)%mod);

    return ;

}

最后放下代码就好辣!(跑得飞慢,,,QAQ

upd:

今天交流了下,,,发现我这个方法太呆了$TT$

说个神一点儿的方法

可以发现斐波拉契数列其实有个规律,,,就 $ 1+\sum_{j=1}^{i} f_{j}=f_{i} $ (其实是这个:$\sum_{i=1}^nf_i=f_{n+2}-f_2$

设$s_i=\sum_{j=1}^i$

可以得到,$ans=n\cdot s_n-(s_{1}+s_{2}+...+s_{n-1})$

代入上面那个然后变形一下可得,$ans=n\cdot f_{n+2}-f_{n+3}+n+2$

然后就傻逼题了,懒得放代码辽太$easy$辣$QAQ$

随机推荐

dataframe构建
data=[[[0],1]]df = pd.DataFrame(data, columns=['col1', 'col2']) df = pd.DataFrame({‘col1’:‘’,‘col2’: ...
网上很多laravel中cookie的使用方法。
https://blog.****.net/chen529834149/article/details/75244718 概述 Cookie的添加其实很简单,直接使用Cookie::make(),在使 ...
Postman使用入门
https://jingyan.baidu.com/article/0f5fb09907e3046d8334ea2f.html Postman测试管理的单位是测试集(Collections),测试集内 ...
****-Java培训 - 看看这次会有多少人跟风...
2019年5月8日,闲来无事(最近答辩还没事......),存个档. 看看这一波风口,记录互联网+教育.
h3c 广域网与OSI参考模型
SuperSocket主动从服务器端推送数据到客户端
关键字: 主动推送, 推送数据, 客户端推送, 获取Session, 发送数据, 回话快照通过Session对象发送数据到客户端前面已经说过,AppSession 代表了一个逻辑的 socke ...
js利用select标签生成简易计算功能
html中使用select option作为运算符的承接容器,输入值,选择不同运算符,计算结果. 文章地址 https://www.cnblogs.com/sandraryan/ <!DOCTY ...
[转]WebApi 后端文件传输至远程服务器
/* 功能说明:微信退款需要有数字证书,而我们公司是做小程序平台的,会帮商家自动退款,所以会要求商家把微信证书上传至我们服务器,以便微信退款. 使用HttpPostedFile 接受前端上传的文件, ...
四叶草（css）
<!DOCTYPE html><html><head> <meta charset="utf-8"> <style> . ...
2018-2-13-WPF-拖动时出现-Invalid-FORMATETC-structure
title author date CreateTime categories WPF 拖动时出现 Invalid FORMATETC structure lindexi 2018-2-13 17:2 ...

秒客网

$loj$10222 佳佳的$Fibonacci$ 矩阵快速幂

正解:矩阵快速幂

解题报告:

随机推荐

相关文章