时间限制: 1000 ms 内存限制: 524288 KB
sol：搞了大概一个多小时什么结果都没，被迫去看题解，感觉自己菜到家了qaq
大家一起膜神仙
/* 原式 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*/#includeusing namespace std;typedef long long ll;inline ll read(){ ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){ if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')ll n,nn,Mod;ll ans[5][5],power[5][5],a[5][5],c[5][5];inline void Ad(ll &X,ll Y){ X+=Y; X-=(X>=Mod)?Mod:0; return;}int main(){ int i,j,k; nn=n=read(); n--; R(Mod); ans[1][2]=ans[1][3]=1; for(i=1;i<=4;i++) power[i][i]=1; a[1][1]=a[2][1]=a[2][2]=a[3][2]=a[3][3]=a[3][4]=a[4][2]=a[4][3]=1; while(n) { if(n&1) { memset(c,0,sizeof c); for(i=1;i<=4;i++) for(j=1;j<=4;j++) for(k=1;k<=4;k++) { Ad(c[i][j],power[i][k]*a[k][j]%Mod); } memmove(power,c,sizeof power); } memset(c,0,sizeof c); for(i=1;i<=4;i++) for(j=1;j<=4;j++) for(k=1;k<=4;k++) { Ad(c[i][j],a[i][k]*a[k][j]%Mod); } memmove(a,c,sizeof a); n>>=1; } memset(c,0,sizeof c); for(i=1;i<=1;i++) for(j=1;j<=4;j++) for(k=1;k<=4;k++) { Ad(c[i][j],ans[i][k]*power[k][j]%Mod); } memmove(ans,c,sizeof ans); Wl((ans[1][2]*nn%Mod-ans[1][1]+Mod)%Mod); return 0;}/*input5 5output1*/