結果

問題 No.1105 Many Triplets
ユーザー T1610
提出日時 2020-07-07 15:02:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,424 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 171,248 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-01 07:31:38
合計ジャッジ時間 2,373 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}
template <typename T, typename U> T pow_fast(T x, U n) {
T ret = (T)1;
while(n) {
if(n & (U)1) ret *= x;
x *= x;
n >>= 1;
}
return ret;
}
template <typename ModType, ModType MOD> struct ModInt {
ModType val;
ModInt() : val(0) {}
ModInt(ModType x) : val(x % MOD) {
if(val < 0) val += MOD;
};
operator ModType() const { return val; }
ModInt &operator+=(const ModInt &m) {
val += m.val;
if(val >= MOD) val -= MOD;
return *this;
}
ModInt &operator-=(const ModInt &m) {
val -= m.val;
if(val < 0) val += MOD;
return *this;
}
ModInt &operator*=(const ModInt &m) {
(val *= m.val) %= MOD;
return *this;
}
ModInt &operator/=(const ModInt &m) {
*this *= m.inverse();
return *this;
}
ModInt operator+(const ModInt &m) const { return ModInt(*this) += m; }
ModInt operator-(const ModInt &m) const { return ModInt(*this) -= m; }
ModInt operator*(const ModInt &m) const { return ModInt(*this) *= m; }
ModInt operator/(const ModInt &m) const { return ModInt(*this) /= m; }
ModInt inverse() const { return pow_fast(*this, MOD - 2); }
ModInt pow(ModType n) const {return pow_fast(*this, n); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &rhs) {
os << rhs.val;
return os;
}
friend std::istream &operator>>(std::istream &is, ModInt &rhs) {
ModType value;
is >> value;
rhs = ModInt(value);
return is;
}
};
template <class T, int SZ>
struct Mat {
array<array<T, SZ>, SZ> d;
const int n;
Mat() : n(SZ) {
array<T, SZ> tmp;
d.fill(tmp);
}
Mat operator * (const Mat& mt) const {
Mat ret;
rep(i, SZ) rep(j, SZ) {
rep(k, SZ) {
ret.d[i][j] += (d[i][k] * mt.d[k][j]);
}
}
return ret;
}
Mat& operator *= (const Mat& mt) {
*this = *this * mt;
return *this;
}
Mat& operator = (const Mat& mt) {
d = mt.d;
return *this;
}
Mat(Mat&&)=default;
array<T, SZ>& operator [](const int n) {
return d[n];
}
Mat pow(ll n) {
Mat<T, SZ> ret;
rep(i, SZ) ret.d[i][i] = 1LL;
while(n > 0) {
if(n&1LL) ret = ret * (*this);
*this = (*this)*(*this);
n >>= 1;
}
return ret;
}
};
int main(){
ll n;
int a, b, c;
cin >> n >> a>> b >> c;
using mint = ModInt<ll, MOD>;
Mat<mint, 3> m;
m[0][0] = 1; m[0][1] = -1;
m[1][1] = 1; m[1][2] = -1;
m[2][2] = 1; m[2][0] = -1;
Mat<mint, 3> x;
x[0][0] = a; x[1][0] = b; x[2][0] = c;
auto y = m.pow(n-1) * x;
cout << y[0][0] << " " << y[1][0] << " " << y[2][0] << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0