結果
問題 |
No.1810 RGB Biscuits
|
ユーザー |
![]() |
提出日時 | 2024-09-28 17:46:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 2,811 bytes |
コンパイル時間 | 1,959 ms |
コンパイル使用メモリ | 183,764 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-28 17:46:51 |
合計ジャッジ時間 | 3,267 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> #define rep(i,n) for(int i=0; i< (n); i++) using namespace std; typedef long long ll; typedef pair<int,int> P; const int mod = 1e+9 + 7; const int inf = (1<<30); const ll INF = (1ull<<62); class mint { long long x; public: mint(long long x=0) : x((x%mod+mod)%mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const { mint res(*this); return res+=a; } mint operator-(const mint& a) const { mint res(*this); return res-=a; } mint operator*(const mint& a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } }; struct matrix{ vector<vector<mint>> a; void set(vector<vector<mint>> b){ a.resize(3,vector<mint>(3)); rep(i,3)rep(j,3){ a[i][j] = b[i][j]; } } void setI(){ a.resize(3,vector<mint>(3)); rep(i,3) a[i][i] = 1; } void set0(){ a.resize(3,vector<mint>(3)); } matrix mult(matrix b){ matrix c; c.set0(); rep(i,3){ rep(j,3){ rep(k,3)c.a[i][j] += a[i][k]*b.a[k][j]; } } return c; } matrix pow(ll x){ matrix c,res; res.setI(); c = *this; for(int i = 0; i<61; i++){ if((x>>i)&1) res = res.mult(c); c = c.mult(c); } return res; } }; int main(){ int A,B; cin>>A>>B; matrix a,b; a.set(vector<vector<mint>>{{1,0,0}, {0,1,0}, {A,B,1}}); b.set(vector<vector<mint>>{{0,0,1}, {1,0,0}, {0,0,0}}); matrix c = b.mult(a); int n; cin>>n; rep(i,n){ ll t; cin>>t; matrix r = c.pow(t/2); if(t%2) r = a.mult(r); mint ans = 0; rep(i,3) rep(j,2) ans += r.a[i][j]; cout<<ans<<endl; } }