首页 > 代码库 > bzoj4002[JLOI2015]有意义的字符串

bzoj4002[JLOI2015]有意义的字符串

2024-08-13 13:26:55   222人阅读

bzoj4002[JLOI2015]有意义的字符串

题意：

给出b，d，n。求

技术分享

题解：

蒟蒻太弱只能引用神犇的题解

构造数列an=b∗an−1+d−b2/4*an−2 ，其中a0=2,a1=b，然后我们求出这个数列的通项公式，得到an=(b+d√2)n+(b−d√2)n 即(b+d√2)n=an−(b−d√2)n 。由于b%2=1,d%4=1，因此d−b2/4一定是个正整数，故我们可以利用矩阵乘法来求出这个数列的第n项。由数据得b−d√2∈(−1,0]，故后面那一项对答案有贡献当且仅当d≠b2且n为偶数。

 

 

代码：

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll unsigned long long 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define mod 7528443412579576937 7 using namespace std; 8  9 struct M{10     ll a[5][5];11     M(){inc(i,0,1)inc(j,0,1)a[i][j]=0;}12 };13 ll b,d,n; M st,ans;14 ll cheng(ll a,ll b){15     if(b==0)return 0; if(b==1)return a; ll c=cheng(a,b>>1)%mod;16     if(b&1)return ((c+c)%mod+a)%mod;else return (c+c)%mod;17 }18 M mul(M a,M b){19     M c; inc(i,0,1)inc(j,0,1)inc(k,0,1)20         c.a[i][j]=(c.a[i][j]+cheng(a.a[i][k],b.a[k][j]))%mod;21     return c;22 }23 M pow(M a,ll b){24     if(b==1)return a; M c=pow(a,b>>1); if(b&1)return mul(mul(c,c),a);else return mul(c,c);25 }26 int main(){27     scanf("%lld%lld%lld",&b,&d,&n);28     if(n==0){printf("1"); return 0;}29     st.a[0][0]=b%mod; st.a[0][1]=2;30     if(n==1)ans=st;else{31         ans.a[0][0]=b%mod; ans.a[0][1]=1; ans.a[1][0]=(d-b*b)/4%mod;32         ans=pow(ans,n-1); ans=mul(st,ans);33     }34     if(b*b!=d&&!(n&1))printf("%lld",(ans.a[0][0]+mod-1)%mod);else printf("%lld",ans.a[0][0]);35     return 0;36 }

 

20160710

bzoj4002[JLOI2015]有意义的字符串


联系
我们