用户网站模板,青岛私人做网站,安阳区号是多少,产品网站怎么做超链接解析
非常妙的一个题#xff0c;感受到了斐波拉契优美的归纳性质。
首先#xff0c;不难发现只要两个1*1的位置固定#xff0c;中间的摆法就固定了#xff0c;而两边的方案都是经典的斐波拉契数列#xff08;设为 fif_ifi#xff09;。 那么枚举中间的间隔再枚举左边…解析
非常妙的一个题感受到了斐波拉契优美的归纳性质。
首先不难发现只要两个1*1的位置固定中间的摆法就固定了而两边的方案都是经典的斐波拉契数列设为 fif_ifi。 那么枚举中间的间隔再枚举左边的长度就有 ans2∑i3n∑j0n−ifjfn−i−jans2\sum_{i3}^n\sum_{j0}^{n-i}f_jf_{n-i-j}ans2i3∑nj0∑n−ifjfn−i−j 乘二是因为对于一种间隔中间的砖有两种摆法。 转换一下求和顺序 ans2∑i0n−3fi∑j0n−3−ifjans2\sum_{i0}^{n-3}f_i\sum_{j0}^{n-3-i}f_jans2i0∑n−3fij0∑n−3−ifj 然后有一个斐波拉契的经典结论然而我并不会 ∑i0nfifn2−1\sum_{i0}^nf_if_{n2}-1i0∑nfifn2−1 证明直接归纳即可。 所以原式就等于 2∑i0n−3fi(fn−1−i−1)2(∑i0n−3fifn−1−i−(fn−1−1))2(∑i0n−1fifn−1−i1−2fn−1−fn−2)2\sum_{i0}^{n-3}f_i(f_{n-1-i}-1)2(\sum_{i0}^{n-3}f_if_{n-1-i}-(f_{n-1}-1))2(\sum_{i0}^{n-1}f_if_{n-1-i}1-2f_{n-1}-f_{n-2})2i0∑n−3fi(fn−1−i−1)2(i0∑n−3fifn−1−i−(fn−1−1))2(i0∑n−1fifn−1−i1−2fn−1−fn−2) 设 sn∑i0nfifn−is_n\sum_{i0}^nf_if_{n-i}sn∑i0nfifn−i答案就是 2(s(n−1)1−2fn−1−fn−2)2(s(n-1)1-2f_{n-1}-f_{n-2})2(s(n−1)1−2fn−1−fn−2)。 再看看 sns_nsn 等于什么 sn∑i0nfifn−ifnfn−1∑i0n−2fifn−is_n\sum_{i0}^nf_if_{n-i}f_nf_{n-1}\sum_{i0}^{n-2}f_if_{n-i}sni0∑nfifn−ifnfn−1i0∑n−2fifn−i fnfn−1∑i0n−2fi(fn−i−1fn−i−2)fnsn−1sn−2f_nf_{n-1}\sum_{i0}^{n-2}f_i(f_{n-i-1}f_{n-i-2})f_ns_{n-1}s_{n-2}fnfn−1i0∑n−2fi(fn−i−1fn−i−2)fnsn−1sn−2 第二步可以拆 fn−if_{n-i}fn−i 是因为此时有 n−i2n-i2n−i2 这样我们就得到了 sss 的递推式也非常优美。 把 f,sf,sf,s 拼在一起构造出转移矩阵快速幂加速即可。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N4e5100;
const int mod1e97;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
int n,m;struct matrix{int x,y;ll a[5][5];matrix(int X,int Y){xX;yY;memset(a,0,sizeof(a));}
};
matrix operator * (const matrix u,const matrix v){matrix res(u.x,v.y);for(int k1;ku.y;k){for(int i1;iu.x;i){ll tmpu.a[i][k];for(int j1;jv.y;j){(res.a[i][j]tmp*v.a[k][j])%mod;}}}return res;
}
int trans[5][5]{{},{0,0,1,0,1},{0,1,1,0,1},{0,0,0,0,1},{0,0,0,1,1},
};
matrix I(4,4),o(4,4),ori(1,4);
matrix ksm(matrix x,int k){matrix resI;while(k){if(k1) resres*x;xx*x;k1;}return res;
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifint Tread();for(int i1;i4;i) I.a[i][i]1;for(int i1;i4;i){for(int j1;j4;j) o.a[i][j]trans[i][j];}ori.a[1][1]1;ori.a[1][2]1;ori.a[1][3]1;ori.a[1][4]2;while(T--){nread();if(n1) puts(0);else{matrix resori*ksm(o,n-2);//printf(%lld %lld %lld %lld\n,res.a[1][1],res.a[1][2],res.a[1][3],res.a[1][4]);printf(%lld\n,(res.a[1][4]1-(2*res.a[1][2]res.a[1][1])%modmod)*2%mod);}}return 0;
}
/*
1
5 0 0 5.001 5.002
*/
