CoderForces-Round60D(1117) Magic Gems

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define Mod 1000000007
 5 const double PI = acos(-1.0);
 6 const double eps = 1e-6;
 7 const int INF = 0x3f3f3f3f;
 8 const int N = 100 + 5;
 9 struct Matrix {
10   ll n , m;
11   ll grid[N][N];
12   Matrix () { n = m = 0; memset(grid , 0 , sizeof(grid)); }
13 };
14 
15 Matrix mul(Matrix a,Matrix b) 
16 {
17     Matrix c;
18     c.n = a.n;c.m = b.m;
19     for(ll i=1;i<=c.n;++i)
20         for(ll j=1;j<=c.m;++j) 
21         {
22             ll cnt = 0;
23             for(ll k=1;k<=a.m;++k) 
24             {
25                 c.grid[i][j] = (c.grid[i][j] + a.grid[i][k] * b.grid[k][j]);
26                 cnt++;
27                 if(cnt % 8 == 0) c.grid[i][j] %= Mod;
28             }
29           c.grid[i][j] %= Mod;
30         }
31   return c;
32 }
33 Matrix QuickMul(Matrix a ,ll k) 
34 {
35     if(k == 1) return a;
36     Matrix mid = QuickMul(a ,(k >> 1));
37     if(k & 1) return mul(mul(mid , mid),a);
38     else return mul(mid , mid);
39 }
40 ll n , m;
41 int main() 
42 {
43     cin >> n >> m;
44     if(n < m) {return puts("1") , 0;}
45     if(n == m) return puts("2") , 0;
46     Matrix basic; basic.n = m; basic.m = 1;
47     for(ll i=1;i<=m;++i) basic.grid[i][1] = (i == m) ? 2 : 1;//{1,1,1...1,m}T
48     Matrix base; base.n = base.m = m;
49     
50     for(ll i = 1; i <= m - 1; i++) base.grid[i][i + 1] = 1;
51     base.grid[m][1] = base.grid[m][m] = 1;
52     
53     Matrix ans = mul(QuickMul(base , n - m) , basic);
54     cout << ans.grid[m][1] << endl;
55     return 0;
56 }

 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,m,dp[321];
17 namespace linear_seq {
18     const int N=10010;
19     ll res[N],base[N],_c[N],_md[N];
20     vector<ll> Md;
21     void mul(ll *a,ll *b,int k)
22     {
23         rep(i,0,k+k) _c[i]=0;
24         rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]= (_c[i+j]+a[i]*b[j])%mod;
25         for (int i=k+k-1;i>=k;i--)  if (_c[i])
26             rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
27         rep(i,0,k) a[i]=_c[i];
28     }
29     int solve(ll n,VI a,VI b)
30     {
31         ll ans=0,pnt=0;
32         int k=SZ(a);
33         assert(SZ(a)==SZ(b));
34         rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
35         Md.clear();
36         rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
37         rep(i,0,k) res[i]=base[i]=0;
38         res[0]=1;
39         while ((1ll<<pnt)<=n) pnt++;
40         for (int p=pnt;p>=0;p--)
41         {
42             mul(res,res,k);
43             if ((n>>p)&1)
44             {
45                 for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
46                 rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
47             }
48         }
49         rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
50         if (ans<0) ans+=mod;
51         return ans;
52     }
53     VI BM(VI s) {
54         VI C(1,1),B(1,1);
55         int L=0,m=1,b=1;
56         rep(n,0,SZ(s)) {
57             ll d=0;
58             rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
59             if (d==0) ++m;
60             else if (2*L<=n) {
61                 VI T=C;
62                 ll c=mod-d*powmod(b,mod-2)%mod;
63                 while (SZ(C)<SZ(B)+m) C.pb(0);
64                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
65                 L=n+1-L; B=T; b=d; m=1;
66             } else {
67                 ll c=mod-d*powmod(b,mod-2)%mod;
68                 while (SZ(C)<SZ(B)+m) C.pb(0);
69                 rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
70                 ++m;
71             }
72         }
73         return C;
74     }
75     int gao(VI a,ll n) {
76         VI c=BM(a);
77         c.erase(c.begin());
78         rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
79         return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
80     }
81 };
82 int main()
83 {
84     scanf("%lld%lld",&n,&m);
85     vector<int> v;
86     for(int i=1;i<m;++i) v.push_back(1);
87     for(ll i=1;i<=m;++i) dp[i]=i+1,v.push_back(dp[i]);
88     for(int i=m+1;i<=10;++i) dp[i]=dp[i-1]+dp[i-m],v.push_back(dp[i]);
89 
90     printf("%lld\n",linear_seq::gao(v,n-1)%mod);
91     return 0;
92 }