一本通1644【例 4】佳佳的 Fibonacci

时间:2021-09-25 16:21:48

1644:【例 4】佳佳的 Fibonacci

时间限制: 1000 ms         内存限制: 524288 KB

一本通1644【例 4】佳佳的 Fibonacci

一本通1644【例 4】佳佳的 Fibonacci

sol:搞了大概一个多小时什么结果都没,*去看题解,感觉自己菜到家了qaq

大家一起膜henry_y神仙

/*
原式
f[i] = f[i-1]+f[i-2]
T[n] = f[1]+f[2]*2+f[3]*3+...+f[n]*n 令
S[n] = f[1]+f[2]+f[3]+...+f[n]
n*S[n] = n*f[1]+n*f[2]+n*f[3]+...+n*f[n]

--> P[n] = n*S[n]-T[n]
--> P[n] = (n-1)*f[1]+(n-2)*f[2]+...+(n-n)*f[n]
因为
--> P[n-1] = (n-1)*S[n]-T[n-1]
--> P[n-1] = (n-2)*f[1]+(n-3)*f[2]+...+(n-1-(n-1))*f[n-1]

--> S[n-1] = f[1]+f[2]+f[3]+....+f[n-1]
所以
P[n]=P[n-1]+S[n-1]
*/
/*
P[i] S[i] f[i] f[i-1] 1 0 0 0
1 1 0 0
0 1 1 1
0 1 1 0
*/

矩阵

Ps:思路要打开

/*
f[i] = f[i-1]+f[i-2]
T[n] = f[1]+f[2]*2+f[3]*3+...+f[n]*n
S[n] = f[1]+f[2]+f[3]+...+f[n]
n*S[n] = n*f[1]+n*f[2]+n*f[3]+...+n*f[n]

--> P[n] = n*S[n]-T[n]
--> P[n] = (n-1)*f[1]+(n-2)*f[2]+...+(n-n)*f[n]
因为
--> P[n-1] = (n-1)*S[n]-T[n-1]
--> P[n-1] = (n-2)*f[1]+(n-3)*f[2]+...+(n-1-(n-1))*f[n-1]

--> S[n-1] = f[1]+f[2]+f[3]+....+f[n-1]
所以
P[n]=P[n-1]+S[n-1] P[i] S[i] f[i] f[i-1] 1 0 0 0
1 1 0 0
0 1 1 1
0 1 1 0
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
ll n,nn,Mod;
ll ans[][],power[][],a[][],c[][];
inline void Ad(ll &X,ll Y)
{
X+=Y;
X-=(X>=Mod)?Mod:;
return;
}
int main()
{
int i,j,k;
nn=n=read(); n--; R(Mod);
ans[][]=ans[][]=;
for(i=;i<=;i++) power[i][i]=;
a[][]=a[][]=a[][]=a[][]=a[][]=a[][]=a[][]=a[][]=;
while(n)
{
if(n&)
{
memset(c,,sizeof c);
for(i=;i<=;i++) for(j=;j<=;j++) for(k=;k<=;k++)
{
Ad(c[i][j],power[i][k]*a[k][j]%Mod);
}
memmove(power,c,sizeof power);
}
memset(c,,sizeof c);
for(i=;i<=;i++) for(j=;j<=;j++) for(k=;k<=;k++)
{
Ad(c[i][j],a[i][k]*a[k][j]%Mod);
}
memmove(a,c,sizeof a);
n>>=;
}
memset(c,,sizeof c);
for(i=;i<=;i++) for(j=;j<=;j++) for(k=;k<=;k++)
{
Ad(c[i][j],ans[i][k]*power[k][j]%Mod);
}
memmove(ans,c,sizeof ans);
Wl((ans[][]*nn%Mod-ans[][]+Mod)%Mod);
return ;
}
/*
input
5 5
output
1
*/

一本通1644【例 4】佳佳的 Fibonacci的更多相关文章

  1. 佳佳的Fibonacci

    #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #inclu ...

  2. 佳佳的 Fibonacci

    佳佳的 Fibonacci \(f_n=f_{n-1}+f_{n-2},f_1=f_2=1\),求\(f_1+2f_2+3f_3+...+nf_nmod\ m,1≤n,m≤2^{31}-1\). 解 ...

  3. TYVJ P3407 佳佳的魔法照片 Label&colon;语文很重要 语文很重要 语文很重要

    描述 佳佳的魔法照片(mphoto.pas\c\cpp) [题目背景] 佳佳的魔法照片(Magic Photo):如果你看过<哈利•波特>,你就会知道魔法世界里的照片是很神奇的.也许是因为 ...

  4. 【DFS】佳佳的魔法阵

    [vijos1284]佳佳的魔法阵 背景 也许是为了捕捉猎物(捕捉MM?),也许是因为其它原因,总之,佳佳准备设计一个魔法阵.而设计魔法阵涉及到的最关键问题,似乎就是那些带有魔力的宝石的摆放…… 描述 ...

  5. P1875 佳佳的魔法药水

    P1875 佳佳的魔法药水 题目描述 发完了 k 张照片,佳佳却得到了一个坏消息:他的 MM 得病了!佳佳和大家一样焦急 万分!治好 MM 的病只有一种办法,那就是传说中的 0 号药水 ……怎么样才能 ...

  6. 洛谷 P1875 佳佳的魔法药水

    P1875 佳佳的魔法药水 题目描述 发完了 k 张照片,佳佳却得到了一个坏消息:他的 MM 得病了!佳佳和大家一样焦急 万分!治好 MM 的病只有一种办法,那就是传说中的 0 号药水 --怎么样才能 ...

  7. 洛谷—— P1875 佳佳的魔法药水

    https://www.luogu.org/problemnew/show/1875 题目背景 发完了 k 张照片,佳佳却得到了一个坏消息:他的 MM 得病了!佳佳和大家一样焦急 万分!治好 MM 的 ...

  8. 「Vijos 1282」「OIBH杯NOIP2006第二次模拟赛」佳佳的魔法照片

    佳佳的魔法照片 背景 佳佳的魔法照片(Magic Photo):如果你看过<哈利·波特>,你就会知道魔法世界里的照片是很神奇的.也许是因为小魔法师佳佳长的太帅,很多人都找他要那种神奇的魔法 ...

  9. 「Vijos 1285」「OIBH杯NOIP2006第二次模拟赛」佳佳的魔法药水

    佳佳的魔法药水 背景 发完了k张照片,佳佳却得到了一个坏消息:他的MM得病了!佳佳和大家一样焦急万分!治好MM的病只有一种办法,那就是传说中的0号药水--怎么样才能得到0号药水呢?你要知道佳佳的家境也 ...

随机推荐

  1. Method threw &&num;39&semi;org&period;hibernate&period;exception&period;SQLGrammarException&&num;39&semi; exception&period; Cannot evaluate com&period;hotel&period;Object&lowbar;&dollar;&dollar;&lowbar;jvst485&lowbar;15&period;toString&lpar;&rpar;

    数据库字段和类Object属性不匹配,Method threw 'org.hibernate.exception.SQLGrammarException' exception. Cannot eval ...

  2. POJ 2195

    #include<iostream>//by Chengdacaizi #include<stdio.h> #include<vector> #include&lt ...

  3. IntelliJ IDEA 部署Tomcat及创建一个web工程

    一.部署Tomcat 二.新建一个web工程 1.新建一个Project 2.现在建立一个简单的web工程,所以只勾选下面选中的,此外,本版本(IntelliJ IDEA 14.1.5只支持3.1版本 ...

  4. C&num;实现SOAP调用WebService

    最近写了一个SOA服务,开始觉得别人拿到我的服务地址,然后直接添加引用就可以使用了,结果"大牛"告知不行. 让我写一个SOAP调用服务的样例,我有点愣了,因为没做过这方面的,于是搞 ...

  5. 指针与数组、大小端之 printf&lpar;&quot&semi;&percnt;x&comma;&percnt;x&comma;&percnt;x&bsol;n&quot&semi;&comma;&ast;&lpar;a&plus;1&rpar;&comma;ptr1&lbrack;-1&rsqb;&comma;&ast;ptr2&rpar;&semi;

    在X86系统下,以下程序输出的值为多少? #include <stdio.h> #include <stdlib.h> int main(void) { ]={,,,,}; ) ...

  6. JAVA基础知识总结:八

    面向对象语言的三大特性;封装.继承.多态 一.面向对象语言特性之封装 1.什么是封装? 一个类中某些属性,如果不希望外界直接访问,我们可以将这个属性作为私有的,可以给外界暴露出来一个访问的方法 使用封 ...

  7. 套接字(linux相关)

    前言:略 一.前因 一切从tcp.udp开始. 众所周知,网络模型一般有两种模型,一种为OSI概念模型(七层),另一种为tcp/ip网络模型(四层). tcp/ip应用层对应OSI的应用层.显示层.会 ...

  8. bzoj 4765&colon; 普通计算姬

    Description "奋战三星期,造台计算机".小G响应号召,花了三小时造了台普通计算姬.普通计算姬比普通计算机要厉害一些 .普通计算机能计算数列区间和,而普通计算姬能计算树中 ...

  9. ROM、SDRAM、RAM、DRAM、SRAM、FLASH区别

    body, table{font-family: 微软雅黑; font-size: 13.5pt} table{border-collapse: collapse; border: solid gra ...

  10. java struts2入门学习实例--用户注册和用户登录整合

    需求: 1.用户注册(user_register.jsp)-->注册成功(UserRegister.action)-->显示注册信息(register_success.jsp)2.用户登录 ...