ACM-ICPC 2018 焦作赛区网络预赛 L 题 Poor God Water

God Water likes to eat meat, fish and chocolate very much, but unfortunately, the doctor tells him that some sequence of eating will make them poisonous.

Every hour, God Water will eat one kind of food among meat, fish and chocolate. If there are

Now, you are the doctor. Can you find out how many different kinds of diet that can make God Water happy and safe during

Input

The fist line puts an integer

Each of the next $10^{10}1≤N≤1010)$

Output

For each test case, output a single line containing the answer.

样例输入

样例输出

20
46
435170

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

题解：递推

// a[i]=2*a[i-1]-a[i-2]+3*a[i-3]+2*a[i-4] (i>2)然后矩阵快速幂

当然也可以用dls的BM求

参考代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define rep(i,a,n) for (int i=a;i<n;i++)
  4 #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5 #define pb push_back
  6 #define mp make_pair
  7 #define all(x) (x).begin(),(x).end()
  8 #define fi first
  9 #define se second
 10 #define SZ(x) ((int)(x).size())
 11 typedef vector<int> VI;
 12 typedef long long ll;
 13 typedef pair<int,int> PII;
 14 const ll mod=1000000007;
 15 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
 16 ll _,n;
 17 namespace linear_seq{
 18     const int N=10010;
 19     ll res[N],base[N],_c[N],_md[N];
 20 
 21     vector<ll> Md;
 22     void mul(ll *a,ll *b,int k) 
 23     {
 24         rep(i,0,k+k) _c[i]=0;
 25         rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
 26         for (int i=k+k-1;i>=k;i--) if (_c[i])
 27             rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
 28         rep(i,0,k) a[i]=_c[i];
 29     }
 30     int solve(ll n,VI a,VI b) 
 31     {
 32         ll ans=0,pnt=0;
 33         int k=SZ(a);
 34         assert(SZ(a)==SZ(b));
 35         rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
 36         Md.clear();
 37         rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
 38         rep(i,0,k) res[i]=base[i]=0;
 39         res[0]=1;
 40         while ((1ll<<pnt)<=n) pnt++;
 41         for (int p=pnt;p>=0;p--) 
 42         {
 43             mul(res,res,k);
 44             if ((n>>p)&1) 
 45             {
 46                 for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
 47                 rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
 48             }
 49         }
 50         rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
 51         if (ans<0) ans+=mod;
 52         return ans;
 53     }
 54     VI BM(VI s) {
 55         VI C(1,1),B(1,1);
 56         int L=0,m=1,b=1;
 57         rep(n,0,SZ(s)) {
 58             ll d=0;
 59             rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
 60             if (d==0) ++m;
 61             else if (2*L<=n) {
 62                 VI T=C;
 63                 ll c=mod-d*powmod(b,mod-2)%mod;
 64                 while (SZ(C)<SZ(B)+m) C.pb(0);
 65                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
 66                 L=n+1-L; B=T; b=d; m=1;
 67             } else {
 68                 ll c=mod-d*powmod(b,mod-2)%mod;
 69                 while (SZ(C)<SZ(B)+m) C.pb(0);
 70                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
 71                 ++m;
 72             }
 73         }
 74         return C;
 75     }
 76     int gao(VI a,ll n){
 77         VI c=BM(a);
 78         c.erase(c.begin());
 79         rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
 80         return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
 81     }
 82 };
 83 int T;
 84 int main() 
 85 {
 86 　　scanf("%d",&T);
 87     while(T--) 
 88 　　{
 89     scanf("%lld",&n);
 90         vector<int>v;
 91         v.push_back(3);
 92         v.push_back(9);
 93         v.push_back(20);
 94         v.push_back(46);
 95         v.push_back(106);
 96         v.push_back(244);
 97         v.push_back(560);
 98     v.push_back(1286); 
 99     v.push_back(2956);
100     v.push_back(6794); 
101         printf("%lld
",linear_seq::gao(v,n-1)%mod);
102     }
103     return 0;
104 }

View Code