[bzoj5131][矩阵乘法][exgcd]可做题2

传送门

题解

随便推柿子
然后ex..
upd:
还是挂一点题解吧..
你把第一第二个数对后面每个数的贡献推出来
发现对于第n个数
第一个数对他的贡献有$f(n-2)$个
第二个数对他的贡献有$f(n-1)$个
其中 f f <script type="math/tex" id="MathJax-Element-30">f</script>是斐波那契数列
然后就随便搞了..

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
LL g,L,R,pos,mod,cal;
struct matrix
{LL m[4][4];matrix(){memset(m,0,sizeof(m));}
}st,tmp;
inline void ad(LL &x,LL y){
   x=(x+y)%mod;}
inline matrix mul(matrix u,matrix v,int n,int m,int p)
{matrix ret;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=1;k<=p;k++)ad(ret.m[i][k],u.m[i][j]*v.m[j][k]);return ret;
}
inline matrix pow_mod(matrix u,LL b,int ln)
{matrix ans;for(int i=1;i<=ln;i++)ans.m[i][i]=1;while(b){if(b&1)ans=mul(ans,u,ln,ln,ln);u=mul(u,u,ln,ln,ln);b>>=1;}return ans;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{if(a==0){x=0;y=1;return b;}else{LL tx,ty;LL d=exgcd(b%a,a,tx,ty);x=ty-(b/a)*tx;y=tx;return d;}
}
int main()
{
//  freopen("a.in","r",stdin);int T;scanf("%d",&T);while(T--){scanf("%lld%lld%lld%lld%lld%lld",&g,&L,&R,&pos,&mod,&cal);g%=mod;LL u1,u2;if(pos<=2){if(pos==1){if(g==cal)printf("%lld\n",R-L+1);else puts("0");continue;}else{if(cal>=L&&cal<=R)printf("%lld\n",R-cal+1);else puts("0");continue;}}else{st.m[1][1]=1;st.m[2][1]=1;st.m[3][1]=2;tmp.m[1][1]=0;tmp.m[1][2]=1;tmp.m[1][3]=0;tmp.m[2][1]=0;tmp.m[2][2]=0;tmp.m[2][3]=1;tmp.m[3][1]=0;tmp.m[3][2]=1;tmp.m[3][3]=1;tmp=pow_mod(tmp,pos-3,3);st=mul(tmp,st,3,3,1);u1=st.m[1][1];u2=st.m[2][1];}LL K=cal-(u1*g%mod);while(K<0)K+=mod;if(K>mod)K-=mod;LL A=u2,B=mod,x,y;LL d=exgcd(A,B,x,y);if(K%d){puts("0");continue;}x=(x*(K/d)%(B/d)+(B/d))%(B/d);if(x>R){puts("0");continue;}if(x<L){LL dis=L-x;if(dis%(B/d))x+=(B/d)*(dis/(B/d)+1);else x+=(B/d)*(dis/(B/d));if(x<L||x>R){puts("0");continue;}}LL ad=(R-x)/(B/d);printf("%lld\n",ad+1);}return 0;
}