「BZOJ4002」[JLOI2015] 有意义的字符串
Description
B 君有两个好朋友，他们叫宁宁和冉冉。
有一天，冉冉遇到了一个有趣的题目：输入 b;d;n，求((b+sqrt(D)/2)^N的整数部分，请输出结果 Mod 7528443412579576937 之后的结果吧。
Input
一行三个整数 b;d;n
Output
一行一个数表示模 7528443412579576937 之后的结果。
Sample Input
1 5 9
Sample Output
76
HINT
0 <b^2 < d< (b +1)2 < 10^18。
题解
http://blog.csdn.net/popoqqq/article/details/45148309
为什么我不知道高中课本有特征方程。。
\(a_{n+2}=p*a_{n+1}+q*a_n\)
的特征方程 \(x^2=px+q\)
得出方程的两个根x1,x2
如果两根不等
\(a_n=Ax_1^n+Bx_2^n\)
n=0,1带入求出通项
知道这个以后通项倒回去就简单了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll unsigned long long #define mod 7528443412579576937UL using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll b,d,n,A,B; ll mul(ll a,ll b) { ll ans=0;a%=mod; for(ll i=b;i;i>>=1,a=(a+a)%mod) if(i&1)ans=(ans+a)%mod; return ans; } struct M{ ll a[2][2]; M(){ memset(a,0,sizeof(a)); } friend M operator*(M a,M b){ M ans; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) (ans.a[i][j]+=mul(a.a[i][k],b.a[k][j]))%=mod; return ans; } friend M operator^(M a,ll b){ M ans; ans.a[0][0]=ans.a[1][1]=1; for(ll i=b;i;i>>=1,a=a*a) if(i&1)ans=ans*a; return ans; } }a,ans; int main() { b=read();d=read();n=read(); A=b;B=(d-b*b)/4; a.a[0][1]=1;a.a[1][0]=B;a.a[1][1]=A; ans.a[0][0]=2;ans.a[1][0]=b; int F=0; if(b*b!=d&&n%2==0)F=1; printf("%lld\n",(((a^n)*ans).a[0][0]-F+mod)%mod); return 0; } |
计数器 9854421
OI 课件=>
OI 课件=>
考的时候跪烂了矩阵还是挂掉了……