結果

問題 No.1704 Many Bus Stops (easy)
ユーザー noya2
提出日時 2021-10-08 22:53:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 7,739 bytes
コンパイル時間 6,147 ms
コンパイル使用メモリ 274,716 KB
最終ジャッジ日時 2025-01-24 23:07:23
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
/*
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using bint = mp::cpp_int;
*/
#include <atcoder/all>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define repp(i,n,m) for (int i = m; i < int(n); ++i)
#define repb(i,n) for (int i = int(n)-1; i >= 0; --i)
#define fi first
#define se second
#define endl "\n"
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<long double, long double>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
const int INF = 1001001007;
const long long mod1 = 1000000007LL;
const long long mod2 = 998244353LL;
const ll inf = 2e18;
const ld pi = 3.14159265358979323;
const ld eps = 1e-7;
template<class T>istream &operator>>(istream &is,vector<T> &v){for(auto &e:v)is>>e;return is;}
template<class T>ostream &operator<<(ostream &os,const vector<T> &v){if(v.size()==0){os<<endl;}else{rep(i,v.size())os<<v[i]<<(i+1==v.size()?"\n":" "
    );}return os;}
template<class T>istream &operator>>(istream &is,vector<vector<T>> &v){for(auto &e:v)is>>e;return is;}
template<class T>ostream &operator<<(ostream &os,const vector<vector<T>> &v){if(v.size()==0){os<<endl;}else{for(auto &e:v)os<<e;}return os;}
template<typename T>bool range(T a,T b,T x){return (a<=x&&x<b);}
template<typename T>bool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));}
template<typename T>void rev(vector<T> &v){reverse(v.begin(),v.end());}
template<typename T>void sor(vector<T> &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);}
template<typename T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<typename T>void eru(vector<T> &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());}
template<typename T>T cel(T a,T b){if(a%b==0)return a/b;return a/b +1;}
template<typename T,typename U>void out2(T a,U b){cout<<a<<" "<<b<<endl;}
template<typename T>void mout(T a){cout<<a.val()<<endl;}
void yes(){cout << "Yes" << endl;}
void no (){cout << "No" << endl;}
void yn (bool t){if(t)yes();else no();}
void dame(bool t){if(t){cout << -1 << endl;exit(0);}}
void dout(ld h=-1.23456789){cout<<setprecision(20);if(abs(h+1.23456789)>eps)cout<<h<<endl;}
void deb(ll h = INF-1) {cout << (h == INF-1 ? "!?" : to_string(h)) << endl;}
void revs(string &s) {reverse(s.begin(),s.end());}
vector<int> dx = {0,1,0,-1};
vector<int> dy = {1,0,-1,0};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string num = "0123456789";
ll gcds(ll a, ll b){
a = abs(a); b = abs(b);
if (b == 0) return a;
ll c = a % b;
while (c != 0){
a = b;
b = c;
c = a % b;
}
return b;
}
ll tentou(vector<ll> ar){
int n = ar.size();
set<ll> st;
rep(i,n) st.insert(ar[i]);
map<ll,int> mp;
int ind = 0;
for (ll x : st){
mp[x] = ind;
ind++;
}
fenwick_tree<ll> fw(ind);
ll ans = 0;
rep(i,n){
int a = mp[ar[i]];
ans += i - fw.sum(0,a+1);
fw.add(a,1);
}
return ans;
}
/*
alias g++='g++ -I/mnt/c/Users/Owner/Desktop/ac-library'
*/
struct vs{
vector<int> to;
};
template<typename T> struct Matrix{
int rows;
int cols;
vector<vector<T>> m;
Matrix (int h = 0, int w = 0, T init = T(0)) : m(h,vector<T>(w,init)), rows(h), cols(w){}
Matrix (vector<vector<T>> _init) : m(_init), rows(_init.size()), cols(_init.at(0).size()){}
vector<T> operator[](const int i) const {return m[i];}
vector<T>& operator[](const int i) {return m[i];}
Matrix &operator+= (const Matrix &r){
assert(this->rows == r.rows && this->cols == r.cols);
for (int i = 0; i < r.rows; ++i){
for (int j = 0; j < r.cols; ++j){
m[i][j] += r.m[i][j];
}
}
return *this;
}
Matrix &operator-= (const Matrix &r){
assert(this->rows == r.rows && this->cols == r.cols);
for (int i = 0; i < r.rows; ++i){
for (int j = 0; j < r.cols; ++j){
m[i][j] -= r.m[i][j];
}
}
return *this;
}
Matrix &operator*= (const Matrix &r){
assert(this->cols == r.rows);
Matrix res(rows, r.cols);
for (int i = 0; i < rows; ++i){
for (int j = 0; j < r.cols; ++j){
for (int k = 0; k < r.rows; ++k){
res[i][j] += m[i][k] * r.m[k][j];
}
}
}
return *this = res;
}
Matrix operator+ (const Matrix &r) const {return Matrix(*this) += r;}
Matrix operator- (const Matrix &r) const {return Matrix(*this) -= r;}
Matrix operator* (const Matrix &r) const {return Matrix(*this) *= r;}
bool operator== (const Matrix &r){
if (rows != r.rows || cols != r.cols) return false;
for (int i = 0; i < r.rows; ++i){
for (int j = 0; j < r.cols; ++j){
if (m[i][j] != r.m[i][j]) return false;
}
}
return true;
}
Matrix& operator+=(const T &r){
for (int i = 0; i < rows; ++i){
for (int j = 0; j < cols; ++j){
m[i][j] += r;
}
}
return *this;
}
Matrix& operator-=(const T &r){
for (int i = 0; i < rows; ++i){
for (int j = 0; j < cols; ++j){
m[i][j] -= r;
}
}
return *this;
}
Matrix& operator*=(const T &r){
for (int i = 0; i < rows; ++i){
for (int j = 0; j < cols; ++j){
m[i][j] *= r;
}
}
return *this;
}
Matrix& operator/=(const T &r){
for (int i = 0; i < rows; ++i){
for (int j = 0; j < cols; ++j){
m[i][j] /= r;
}
}
return *this;
}
Matrix operator+ (const T &r) const {return Matrix(*this) += r;}
Matrix operator- (const T &r) const {return Matrix(*this) -= r;}
Matrix operator* (const T &r) const {return Matrix(*this) *= r;}
Matrix operator/ (const T &r) const {return Matrix(*this) /= r;}
Matrix e(){
assert(this->rows == this->cols);
Matrix res(this->rows, this->rows);
for (int i = 0; i < rows; ++i) res[i][i] = 1;
return res;
}
Matrix matpow(ll n){
assert(this->rows == this->cols);
if (n == 0) return e();
Matrix f = matpow(n / 2);
Matrix ans = f * f;
if (n % 2 == 1) ans *= *this;
return ans;
}
// for T = int, long long, double, long double
void show(){
for (int i = 0; i < rows; ++i){
for (int j = 0; j < cols; ++j){
cout << m[i][j] << (j+1 == this->cols ? "\n" : " ");
}
}
}
};
int main(){
using mint = modint1000000007;
mint a = mint(2) / mint(9);
mint b = - mint(1) / mint(9);
mint c = a;
mint d = mint(2) / mint(3);
vector<vector<mint>> rec = {
{0, 0, 0, a},
{1, 0, 0, b},
{0, 1, 0, c},
{0, 0, 1, d}
};
Matrix<mint> p(rec);
mint a0 = 1;
mint a1 = a0 / 3;
mint a2 = a1 / 3;
mint a3 = a2 / 3;
vector<vector<mint>> _ini = {{a0, a1, a2, a3}};
Matrix<mint> ini(_ini);
int t; cin >> t;
rep(i,t){
ll n; cin >> n;
Matrix<mint> f = ini * p.matpow(n);
mout(f[0][0]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0