ZJNU 1265 - 幸运的硬币——高级 (矩阵快速幂)
2021/4/27 18:25:22
本文主要是介绍ZJNU 1265 - 幸运的硬币——高级 (矩阵快速幂),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
ZJNU 1265 - 幸运的硬币——高级
题面
众所周知,一个硬币有两面,一面朝上,一面朝下。如果两个硬币同时朝上,或者同时朝下,我们说两个硬币的状态是相同的。如果现在有\(n\)个硬币排成一排,显然有\(2^n\)种不同的排法。如果存在超过两个连续硬币的状态相同,我们就说这个硬币序列是幸运的。那么这种幸运的硬币序列有多少种呢?(\(1\le n\le 10^9\))
思路
总方案数为\(2^n-\)不合法情况数
不合法情况即至多只有两个连续相同的硬币
先考虑此时相邻硬币状态互不相同,即\(0101\)交替或\(1010\)交替,有两种情况
然后从互不相同这种状态延伸至至多只有两个连续相同数的状态
可以看作选中这个\(01\)序列中的某一些数字,将其连写两遍,每选中一个数字则序列总长度会加\(1\)
例如对于长度为\(4\)的序列\(0101\),选中位置\(1\)与位置\(4\),则会变为\(001011\),序列长度变为\(6\),且此时至多只有两个连续相同数
那么明显的,对于所有初始长度为\(\lceil \frac n 2 \rceil \le length \le n\)的\(01\)序列或者\(10\)序列,均可以通过一定的变换使其变成长度为\(n\)的至多只有两个连续相同数字的序列
对于位置选取,可通过组合数选取
则总方案数为
\[2^n-2\times\sum_{i=\lceil\frac n 2\rceil}^{n}\C_i^{n-i} \]注意到题目中\(\max n=10^9\),直接求取组合数方案不可行
但通过打表或者杨辉三角逆推的方法可以发现,\(\sum_{i=\lceil\frac n 2\rceil}^{n}\C_i^{n-i}=Fibonacci[n+1]\)
故可以借助矩阵快速幂来求出斐波那契数列的值
//#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/hash_policy.hpp> #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=10007; mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} struct Fibonacci{ struct matrix{ ll n,m,i; ll data[2][2]; void init(){ for(i=0;i<n;i++) data[i][i]=1; } }a,A,ans; matrix multi(matrix &a,matrix &b){ ll i,j,k; matrix temp; temp.n=a.n; temp.m=b.m; for(i=0;i<temp.n;i++){ for(j=0;j<temp.m;j++) temp.data[i][j]=0; } for(i=0;i<a.n;i++){ for(k=0;k<a.m;k++){ if(a.data[i][k]>0){ for(j=0;j<b.m;j++) temp.data[i][j]=(temp.data[i][j]+(a.data[i][k]*b.data[k][j])%mod)%mod; } } } return temp; } matrix fast_mod(matrix &a,ll n){ matrix ans; ans.n=a.n; ans.m=a.m; memset(ans.data,0,sizeof(ans.data)); ans.init(); while(n>0){ if(n&1) ans=multi(ans,a); a=multi(a,a); n>>=1; } return ans; } ll fibo(ll n){ a.n=1; a.m=2; a.data[0][0]=1; a.data[0][1]=1; A.n=2; A.m=2; A.data[0][0]=0; A.data[0][1]=1; A.data[1][0]=1; A.data[1][1]=1; ans=fast_mod(A,n-1); ans=multi(a,ans); return ans.data[0][0]; } }f; void solve() { int n; cin>>n; cout<<(qpow(2,n)-2LL*f.fibo(n+1)%mod+mod)%mod<<'\n'; } int main() { closeSync; //multiCase { solve(); } return 0; }
这篇关于ZJNU 1265 - 幸运的硬币——高级 (矩阵快速幂)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)