結果
| 問題 | No.1411 Hundreds of Conditions Sequences |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2020-12-02 15:35:10 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 615 ms / 2,000 ms |
| コード長 | 23,637 bytes |
| コンパイル時間 | 2,762 ms |
| コンパイル使用メモリ | 208,928 KB |
| 実行使用メモリ | 98,216 KB |
| 最終ジャッジ日時 | 2024-09-22 11:17:26 |
| 合計ジャッジ時間 | 34,279 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 157 ms
81,336 KB |
| testcase_01 | AC | 158 ms
81,408 KB |
| testcase_02 | AC | 156 ms
81,340 KB |
| testcase_03 | AC | 163 ms
81,204 KB |
| testcase_04 | AC | 160 ms
81,396 KB |
| testcase_05 | AC | 167 ms
81,360 KB |
| testcase_06 | AC | 159 ms
81,352 KB |
| testcase_07 | AC | 158 ms
81,356 KB |
| testcase_08 | AC | 160 ms
81,340 KB |
| testcase_09 | AC | 160 ms
81,340 KB |
| testcase_10 | AC | 162 ms
81,376 KB |
| testcase_11 | AC | 162 ms
81,408 KB |
| testcase_12 | AC | 504 ms
86,400 KB |
| testcase_13 | AC | 418 ms
85,532 KB |
| testcase_14 | AC | 294 ms
83,860 KB |
| testcase_15 | AC | 414 ms
85,368 KB |
| testcase_16 | AC | 173 ms
81,908 KB |
| testcase_17 | AC | 404 ms
85,240 KB |
| testcase_18 | AC | 500 ms
86,468 KB |
| testcase_19 | AC | 536 ms
86,724 KB |
| testcase_20 | AC | 290 ms
83,868 KB |
| testcase_21 | AC | 556 ms
87,040 KB |
| testcase_22 | AC | 306 ms
84,076 KB |
| testcase_23 | AC | 504 ms
86,440 KB |
| testcase_24 | AC | 158 ms
81,372 KB |
| testcase_25 | AC | 496 ms
86,436 KB |
| testcase_26 | AC | 401 ms
85,244 KB |
| testcase_27 | AC | 295 ms
83,892 KB |
| testcase_28 | AC | 438 ms
85,784 KB |
| testcase_29 | AC | 192 ms
82,260 KB |
| testcase_30 | AC | 363 ms
84,884 KB |
| testcase_31 | AC | 354 ms
84,652 KB |
| testcase_32 | AC | 551 ms
87,084 KB |
| testcase_33 | AC | 560 ms
87,096 KB |
| testcase_34 | AC | 552 ms
87,024 KB |
| testcase_35 | AC | 558 ms
87,068 KB |
| testcase_36 | AC | 556 ms
87,096 KB |
| testcase_37 | AC | 557 ms
87,000 KB |
| testcase_38 | AC | 557 ms
87,088 KB |
| testcase_39 | AC | 563 ms
87,040 KB |
| testcase_40 | AC | 564 ms
86,964 KB |
| testcase_41 | AC | 556 ms
86,960 KB |
| testcase_42 | AC | 560 ms
87,020 KB |
| testcase_43 | AC | 564 ms
87,048 KB |
| testcase_44 | AC | 558 ms
87,060 KB |
| testcase_45 | AC | 555 ms
87,000 KB |
| testcase_46 | AC | 551 ms
86,988 KB |
| testcase_47 | AC | 552 ms
87,052 KB |
| testcase_48 | AC | 562 ms
86,932 KB |
| testcase_49 | AC | 560 ms
87,036 KB |
| testcase_50 | AC | 558 ms
87,036 KB |
| testcase_51 | AC | 552 ms
87,040 KB |
| testcase_52 | AC | 562 ms
87,144 KB |
| testcase_53 | AC | 567 ms
87,180 KB |
| testcase_54 | AC | 561 ms
87,324 KB |
| testcase_55 | AC | 566 ms
87,260 KB |
| testcase_56 | AC | 565 ms
87,196 KB |
| testcase_57 | AC | 574 ms
87,196 KB |
| testcase_58 | AC | 567 ms
87,252 KB |
| testcase_59 | AC | 575 ms
87,212 KB |
| testcase_60 | AC | 567 ms
87,228 KB |
| testcase_61 | AC | 565 ms
87,308 KB |
| testcase_62 | AC | 388 ms
82,800 KB |
| testcase_63 | AC | 615 ms
98,216 KB |
ソースコード
////////////////////////////////////////////////////////////////////////////////
// Give me AC!!! //
////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using ll = long long;
using ld = long double;
using graph = vector<vector<int>>;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define PQ priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define S second //pairの二つ目の要素
#define coutY cout<<"YES"<<endl
#define couty cout<<"Yes"<<endl
#define coutN cout<<"NO"<<endl
#define coutn cout<<"No"<<endl
#define coutdouble(a,b) cout << fixed << setprecision(a) << double(b) ;
#define vi(a,b) vector<int> a(b)
#define vl(a,b) vector<ll> a(b)
#define vs(a,b) vector<string> a(b)
#define vll(a,b,c) vector<vector<ll>> a(b, vector<ll>(c));
#define intque(a) queue<int> a;
#define llque(a) queue<ll> a;
#define intque2(a) priority_queue<int, vector<int>, greater<int>> a;
#define llque2(a) priority_queue<ll, vector<ll>, greater<ll>> a;
#define pushback(a,b) a.push_back(b)
#define mapii(M1) map<int, int> M1;
#define cou(v,x) count(v.begin(), v.end(), x)
#define mapll(M1) map<ll,ll> M1;
#define mapls(M1) map<ll, string> M1;
#define mapsl(M1) map<string, ll> M1;
#define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a
#define sor(a) sort(a.begin(), a.end())
#define rever(a) reverse(a.begin(),a.end())
#define rep(i,a) for(ll i=0;i<a;i++)
#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]
#define vcout(n) for(ll i=0;i<ll(n.size());i++) cout<<n[i]
#define vcin2(n) rep(i,ll(n.size())) rep(j,ll(n.at(0).size())) cin>>n[i][j]
//const ll mod = 998244353;
//const ll MOD = 998244353;
const ll MOD = 1000000007;
const ll mod = 1000000007;
constexpr ll MAX = 5000000;
//const ll _max = 9223372036854775807;
const ll _max = 1223372036854775807;
const ll INF = 2000000000000000000;
static const long double pi = 3.141592653589793;
const int MAX_COL=350;
const int MAX_ROW=350;
ll fac[MAX],finv[MAX],inv[MAX];
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int modPow(long long a, long long n, long long p) {
if (a == 0 && n == 0) return 0;
if (n == 0) return 1; // 0乗にも対応する場合
if (n == 1) return a % p;
if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
long long t = modPow(a, n / 2, p);
return (t * t) % p;
}
ll clocks(ll a,ll b,ll c){
return a*3600+b*60+c;
}
ll divup(ll b,ll d){
if(b%d==0){
return b/d;
}
else{
return b/d+1;
}
}
struct edge {
int to; // 辺の行き先
int weight; // 辺の重み
edge(int t, int w) : to(t), weight(w) { }
};
using Graphw = vector<vector<edge>>;
ll zero(ll a){
return max(ll(0),a);
}
template< typename T >
struct FormalPowerSeries : vector< T > {
using vector< T >::vector;
using P = FormalPowerSeries;
using MULT = function< P(P, P) >;
static MULT &get_mult() {
static MULT mult = nullptr;
return mult;
}
static void set_fft(MULT f) {
get_mult() = f;
}
void shrink() {
while(this->size() && this->back() == T(0)) this->pop_back();
}
P operator+(const P &r) const { return P(*this) += r; }
P operator+(const T &v) const { return P(*this) += v; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator-(const T &v) const { return P(*this) -= v; }
P operator*(const P &r) const { return P(*this) *= r; }
P operator*(const T &v) const { return P(*this) *= v; }
P operator/(const P &r) const { return P(*this) /= r; }
P operator%(const P &r) const { return P(*this) %= r; }
P &operator+=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];
return *this;
}
P &operator+=(const T &r) {
if(this->empty()) this->resize(1);
(*this)[0] += r;
return *this;
}
P &operator-=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];
shrink();
return *this;
}
P &operator-=(const T &r) {
if(this->empty()) this->resize(1);
(*this)[0] -= r;
shrink();
return *this;
}
P &operator*=(const T &v) {
const int n = (int) this->size();
for(int k = 0; k < n; k++) (*this)[k] *= v;
return *this;
}
P &operator*=(const P &r) {
if(this->empty() || r.empty()) {
this->clear();
return *this;
}
assert(get_mult() != nullptr);
return *this = get_mult()(*this, r);
}
P &operator%=(const P &r) {
return *this -= *this / r * r;
}
P operator-() const {
P ret(this->size());
for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
P &operator/=(const P &r) {
if(this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);
}
P pre(int sz) const {
return P(begin(*this), begin(*this) + min((int) this->size(), sz));
}
P operator>>(int sz) const {
if(this->size() <= sz) return {};
P ret(*this);
ret.erase(ret.begin(), ret.begin() + sz);
return ret;
}
P operator<<(int sz) const {
P ret(*this);
ret.insert(ret.begin(), sz, T(0));
return ret;
}
P rev(int deg = -1) const {
P ret(*this);
if(deg != -1) ret.resize(deg, T(0));
reverse(begin(ret), end(ret));
return ret;
}
P diff() const {
const int n = (int) this->size();
P ret(max(0, n - 1));
for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);
return ret;
}
P integral() const {
const int n = (int) this->size();
P ret(n + 1);
ret[0] = T(0);
for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);
return ret;
}
// F(0) must not be 0
P inv(int deg = -1) const {
assert(((*this)[0]) != T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
P ret({T(1) / (*this)[0]});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
}
return ret.pre(deg);
}
// F(0) must be 1
P log(int deg = -1) const {
assert((*this)[0] == 1);
const int n = (int) this->size();
if(deg == -1) deg = n;
return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
}
P sqrt(int deg = -1) const {
const int n = (int) this->size();
if(deg == -1) deg = n;
if((*this)[0] == T(0)) {
for(int i = 1; i < n; i++) {
if((*this)[i] != T(0)) {
if(i & 1) return {};
if(deg - i / 2 <= 0) break;
auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2);
if(ret.size() < deg) ret.resize(deg, T(0));
return ret;
}
}
return P(deg, 0);
}
P ret({T(1)});
T inv2 = T(1) / T(2);
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
}
return ret.pre(deg);
}
// F(0) must be 0
P exp(int deg = -1) const {
assert((*this)[0] == T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
P ret({T(1)});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);
}
return ret.pre(deg);
}
P pow(int64_t k, int deg = -1) const {
const int n = (int) this->size();
if(deg == -1) deg = n;
for(int i = 0; i < n; i++) {
if((*this)[i] != T(0)) {
T rev = T(1) / (*this)[i];
P C(*this * rev);
P D(n - i);
for(int j = i; j < n; j++) D[j - i] = C[j];
D = (D.log() * k).exp() * (*this)[i].pow(k);
P E(deg);
if(i * k > deg) return E;
auto S = i * k;
for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];
return E;
}
}
return *this;
}
T eval(T x) const {
T r = 0, w = 1;
for(auto &v : *this) {
r += w * v;
w *= x;
}
return r;
}
};
//aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数
ll expless(ll a,ll b){
ll k=0;
ll o=1;
while(a>=o){
k++;
o=o*b;
}
return k;
}
//aをb進法で表す
//b進法のaを10進法に直す
ll tenbase(ll a,ll b){
ll c=expless(a,10);
ll ans=0;
ll k=1;
for(int i=0;i<c;i++){
ans+=(a%10)*k;
k=k*b;
a=a/10;
}
return ans;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
//aがbで何回割り切るか
ll exp(ll a,ll b){
ll ans=0;
while(a%b==0){
a=a/b;
ans++;
}
return ans;
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int X[6]={1,1,0,-1,-1,0};
const int Y[6]={0,1,1,0,-1,-1};
template<typename T>
vector<T> smallest_prime_factors(T n) {
vector<T> spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (T i = 2; i * i <= n; i++) {
// 素数だったら
if (spf[i] == i) {
for (T j = i * i; j <= n; j += i) {
// iを持つ整数かつまだ素数が決まっていないなら
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
vector<pair<ll,ll>> factolization(ll x, vector<ll> &spf) {
vector<pair<ll,ll>> ret;
ll p;
ll z;
while (x != 1) {
p=(spf[x]);
z=0;
while(x%p==0){
z++;
x /= p;
}
ret.push_back({p, z});
}
return ret;
}
vector<bool> is;
vector<long long int> prime_(ll n){
is.resize(n+1, true);
is[0] = false;
is[1] = false;
vector<long long int> primes;
for (int i=2; i<=n; i++) {
if (is[i] == true){
primes.push_back(i);
for (int j=i*2; j<=n; j+=i){
is[j] = false;
}
}
}
return primes;
}
vector<ll> dijkstra(ll f,ll n,vector<vector<vector<ll>>>& edge){
//最短経路としてどの頂点が確定済みかをチェックする配列
vector<ll> confirm(n,false);
//それぞれの頂点への最短距離を保存する配列
//始点は0,始点以外はINFで最短距離を初期化する
vector<ll> mincost(n,INF);mincost[f]=0;
//確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queue
PQ mincand;mincand.push({mincost[f],f});
//mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示す
while(!mincand.empty()){
//最短距離でたどり着くと思われる頂点を取り出す
vector<ll> next=mincand.top();mincand.pop();
//すでにその頂点への最短距離が確定済みの場合は飛ばす
if(confirm[next[1]]) continue;
//確定済みではない場合は確定済みにする
confirm[next[1]]=true;
//その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数
vector<vector<ll>>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない)
if(confirm[v[i][0]]) continue; //(✳︎1)
//辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす)
if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2)
//更新
mincost[v[i][0]]=next[0]+v[i][1];
//更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入
mincand.push({mincost[v[i][0]],v[i][0]});
}
}
return mincost;
}
ll so(ll a){
ll ans=0;
if(a==0){
return 0;
}
while(a%2==0){
a/=2;
ans++;
}
return ans;
}
ll HOM(ll n,ll r){
return COM(n+r-1,r);
}
ll binary(ll bina){
ll ans = 0;
for (ll i = 0; bina>0 ; i++)
{
ans = ans+(bina%2)*pow(10,i);
bina = bina/2;
}
return ans;
}
vector<long long> enum_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
// 重複しないならば i の相方である N/i も push
if (N/i != i) res.push_back(N/i);
}
}
// 小さい順に並び替える
sort(res.begin(), res.end());
return res;
}
vector<ll> zaatu(vector<ll> a,ll n){
map<ll,ll> mp;
for (int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]] = 0;
}
// 小さい値から順に番号を付けていく
ll num = 0;
for (auto x : mp) {
mp[x.first] = num;
num++;
}
vector<ll> ans;
for(int i=0;i<n;i++){
ans.push_back(mp[a[i]]);
}
return ans;
}
ll vectorcheck(vector<ll> t,ll key){
auto iter = lower_bound(ALL(t), key);
auto iter2 = upper_bound(ALL(t), key);
if((iter-t.begin())!=(iter2-t.begin())){
return 1;
}
else{
return 0;
}
}
template<class Monoid>
struct SegmentTree {
using T = typename Monoid::value_type;
std::vector<T> tree;
SegmentTree() = default;
explicit SegmentTree(ll n)
:tree(n << 1, Monoid::identity()) {};
template<class InputIterator>
SegmentTree(InputIterator first, InputIterator last) {
tree.assign(distance(first, last) << 1, Monoid::identity());
ll i;
i = size();
for (InputIterator itr = first; itr != last; itr++) {
tree[i++] = *itr;
}
for (i = size() - 1; i > 0; i--) {
tree[i] = Monoid::operation(tree[(i << 1)], tree[(i << 1) | 1]);
}
};
inline ll size() {
return tree.size() >> 1;
};
inline T operator[] (ll k) {
return tree[k + size()];
};
void add(ll k, const T dat) {
k += size();
tree[k] += dat;
while(k > 1) {
k >>= 1;
tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]);
}
};
void update(ll k, const T dat) {
k += size();
tree[k] = dat;
while(k > 1) {
k >>= 1;
tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]);
}
};
T fold(ll l, ll r) {
l += size(); //points leaf
r += size();
T lv = Monoid::identity();
T rv = Monoid::identity();
while (l < r) {
if (l & 1) lv = Monoid::operation(lv, tree[l++]);
if (r & 1) rv = Monoid::operation(tree[--r], rv);
l >>= 1;
r >>= 1;
}
return Monoid::operation(lv, rv);
};
template<class F>
inline ll sub_tree_search(ll i, T sum, F f) {
while (i < size()) {
T x = Monoid::operation(sum, tree[i << 1]);
if (f(x)) {
i = i << 1;
}
else {
sum = x;
i = (i << 1) | 1;
}
}
return i - size();
}
template<class F>
ll search(ll l, F f) {
l += size();
ll r = size() * 2; //r = n;
ll tmpr = r;
ll shift = 0;
T sum = Monoid::identity();
while (l < r) {
if (l & 1) {
if (f(Monoid::operation(sum, tree[l]))) {
return sub_tree_search(l, sum, f);
}
sum = Monoid::operation(sum, tree[l]);
l++;
}
l >>= 1;
r >>= 1;
shift++;
}
while (shift > 0) {
shift--;
r = tmpr >> shift;
if (r & 1) {
r--;
if (f(Monoid::operation(sum, tree[r]))) {
return sub_tree_search(r, sum, f);
}
sum = Monoid::operation(sum, tree[r]);
}
}
return -1;
};
};
using namespace std;
using llong = long long;
struct Monoid {
using value_type = ll;
inline static ll identity() {
return 1;
};
inline static ll operation(ll a, ll b) {
return a+b;
};
};
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;
}
};
int ctoi(const char c){
switch(c){
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default : return -1;
}
}
ll ord(ll a,ll b){
ll ans=0;
while(a%b==0){
ans++;
a/=b;
}
return ans;
}
ll atll(ll a,ll b){
b++;
ll c=expless(a,10);
ll d=c-b;
ll f=1;
for(int i=0;i<d;i++){
f=f*10;
}
a=(a/f);
return a%10;
}
class UnionFind {
public:
vector <ll> par; // 各元の親を表す配列
vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
// Constructor
UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
// Member Function
// Find
ll root(ll x) { // 根の検索
while (par[x] != x) {
x = par[x] = par[par[x]]; // x の親の親を x の親とする
}
return x;
}
// Union(Unite, Merge)
bool merge(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
// merge technique（データ構造をマージするテク．小を大にくっつける）
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
return true;
}
bool issame(ll x, ll y) { // 連結判定
return root(x) == root(y);
}
ll size(ll x) { // 素集合のサイズ
return siz[root(x)];
}
};
struct BitMatrix {
int H, W;
bitset<MAX_COL> val[MAX_ROW];
BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};
int GaussJordan(BitMatrix &A, bool is_extended = false) {
int rank = 0;
for (int col = 0; col < A.W; ++col) {
if (is_extended && col == A.W - 1) break;
int pivot = -1;
for (int row = rank; row < A.H; ++row) {
if (A[row][col]) {
pivot = row;
break;
}
}
if (pivot == -1) continue;
swap(A[pivot], A[rank]);
for (int row = 0; row < A.H; ++row) {
if (row != rank && A[row][col]) A[row] ^= A[rank];
}
++rank;
}
return rank;
}
int pos(const char c){
if('a' <= c && c <= 'z') return (c-'a');
return -1;
}
ll x[4]={1,0,-1,0};
ll y[4]={0,1,0,-1};
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(30);
auto spf = smallest_prime_factors(10000100ll);
ll n;
cin>>n;
assert(3<=n&&n<=100000);
vector<ll> k(n);
vcin(k);
for(int i=0;i<n;i++){
assert(1<=k.at(i)&&k.at(i)<=10000000);
}
map<ll,ll> l1;
map<ll,ll> l2;
map<ll,ll> pmax;
vector<ll> prime;
ll t=1;
for(int i=0;i<n;i++){
auto result = factolization(k.at(i),spf);
for(int j=0;j<int(result.size());j++){
if(l1[result.at(j).first]==0){
prime.push_back(result.at(j).first);
l1[result.at(j).first]=result.at(j).second;
pmax[result.at(j).first]=i;
}
else if(l2[result.at(j).first]==0){
if(l1[result.at(j).first]>result.at(j).second){
l2[result.at(j).first]=result.at(j).second;
}
else{
l2[result.at(j).first]=l1[result.at(j).first];
l1[result.at(j).first]=result.at(j).second;
pmax[result.at(j).first]=i;
}
}
else{
if(l1[result.at(j).first]<=result.at(j).second){
l2[result.at(j).first]=l1[result.at(j).first];
l1[result.at(j).first]=result.at(j).second;
pmax[result.at(j).first]=i;
}
else if(l2[result.at(j).first]<=result.at(j).second){
l2[result.at(j).first]=result.at(j).second;
}
}
}
}
ll x=1;
for(int i=0;i<int(prime.size());i++){
x*=modPow(prime.at(i),l1[prime.at(i)],mod);
x%=mod;
}
vector<ll> lc(n,x);
for(int i=0;i<int(prime.size());i++){
ll p=modPow(prime.at(i),l1[prime.at(i)]-l2[prime.at(i)],mod);
p=modPow(p,mod-2,mod);
lc.at(pmax[prime.at(i)])*=p;
lc.at(pmax[prime.at(i)])%=mod;
}
ll ans=1;
for(int i=0;i<n;i++){
ans*=k.at(i);
ans%=mod;
}
for(int i=0;i<n;i++){
ll tmp=modPow(k.at(i),mod-2,mod);
tmp*=ans;
tmp%=mod;
tmp-=lc.at(i);
tmp%=mod;
tmp+=mod;
tmp%=mod;
cout<<tmp<<endl;
}
}