$$f_{i}=f_{i-1}+a_{i}^2$$
\n$$a_{i}^2=(xa_{i-1}+ya_{i-2})^2=(x^2a_{i-1}^2+2xya_{i-1}a_{i-2}+y^
\n2a_{i-2}^2)$$
\n$$a_{i}a_{i-1}=(xa_{i-1}+ya_{i-2})a_{i-1}=xa_{i-1}^2+ya_{i-1}a_{i-2}$$
\n\u6545\u800c\u6211\u4eec\u5c31\u53ef\u4ee5\u7528\u77e9\u9635\u52a0\u901f\u9012\u63a8\u6765\u6c42\u8fd9\u4e2a\u51fd\u6570\u7684\u503c\u3002
\n\u6211\u4eec\u5f04\u51fa\u4e00\u4e2a\u5982\u4e0b\u7684\u57fa\u672c\u77e9\u9635\uff1a
\n$$ \\left[\\begin{matrix}a_{1}^2&a_{2}^2&a_{1}a_{2}&f_{2}\\end{matrix}\\right]$$
\n\u6211\u4eec\u4e0d\u59a8\u5c06\u5b83\u770b\u4f5c\u4e00\u4e2a\u56db\u9879\u5f0f\uff0c\u5219\u5176\u4e2d\u6bcf\u4e00\u9879\u7684\u7b54\u6848\u90fd\u53ef\u4ee5\u4ece\u4e0a\u8ff0\u516c\u5f0f\u63a8\u5f97\u3002\u6545\u800c\u53ef\u4ee5\u5f97\u5230\u8fd9\u6837\u4e00\u4e2a\u77e9\u9635\uff1a
\n$$ \\left[\\begin{matrix}0&y^2&0&y^2\\\\1&x^2&x&x^2\\\\0&2xy&y&2xy\\\\0&0&0&1\\end{matrix}\\right]$$
\n\u62ff\u6765\u77e9\u9635\u5feb\u901f\u5e42\u4e00\u4e0b\u5373\u53ef\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n\n\ntypedef long long ll;\nconst ll MOD=1000000007;\n\nstruct Mat{\n\tll a[4][4];\n\tinline void init(){\n\t\tfor(int i=0;i<4;++i){\n\t\t\tfor(int j=0;j<4;++j){\n\t\t\t\ta[i][j]=0;\n\t\t\t}\n\t\t}\n\t}\n\tinline Mat operator*(const Mat &B)const{\n\t\tMat C;\n\t\tC.init();\n\t\tfor(int i=0;i<4;++i){\n\t\t\tfor(int j=0;j<4;++j){\n\t\t\t\tfor(int k=0;k<4;++k){\n\t\t\t\t\tC.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%MOD;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn C;\n\t}\n};\nll a1,a2,n,x,y;\nvoid init(){\n\tscanf(\"%lld%lld%lld%lld%lld\",&n,&a1,&a2,&x,&y);\n\tif(n==1){\n\t\tprintf(\"%lld\\n\",a1*a1%MOD);\n\t\treturn;\n\t}\n\tif(n==2){\n\t\tprintf(\"%lld\\n\",(a2*a2+a1*a1)%MOD);\n\t}\n\tMat BS,T;\n\tBS.init(),T.init();\n\tBS.a[0][0]=a1*a1%MOD,BS.a[0][1]=a2*a2%MOD,BS.a[0][2]=a1*a2%MOD,BS.a[0][3]=(BS.a[0][0]+BS.a[0][1])%MOD;\n\tT.a[0][0]=0,T.a[0][1]=y*y%MOD,T.a[0][2]=0,T.a[0][3]=y*y%MOD;\n\tT.a[1][0]=1,T.a[1][1]=x*x%MOD,T.a[1][2]=x,T.a[1][3]=x*x%MOD;\n\tT.a[2][0]=0,T.a[2][1]=2*x*y%MOD,T.a[2][2]=y,T.a[2][3]=2*x*y%MOD;\n\tT.a[3][0]=0,T.a[3][1]=0,T.a[3][2]=0,T.a[3][3]=1;\n\tn-=2;\n\twhile(n){\n\t\tif(n&1){\n\t\t\tBS=BS*T;\n\t\t}\n\t\tT=T*T;\n\t\tn>>=1;\n\t}\n\tprintf(\"%lld\\n\",BS.a[0][3]);\n}\n\nint main(){\n\tint T;\n\tscanf(\"%d\",&T);\n\twhile(T--){\n\t\tinit();\n\t}\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"$$f_{i}=f_{i-1}+a_{i}^2$$ $$a_{i}^2=(xa_{i-1}+ya_{i-2}) … <\/p>\n