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; }