結果
| 問題 | No.1929 Exponential Sequence |
| ユーザー |
 noya2
|
| 提出日時 | 2022-05-06 22:06:45 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 153 ms / 2,000 ms |
| コード長 | 20,250 bytes |
| コンパイル時間 | 5,082 ms |
| コンパイル使用メモリ | 284,872 KB |
| 実行使用メモリ | 35,004 KB |
| 最終ジャッジ日時 | 2024-09-14 03:52:44 |
| 合計ジャッジ時間 | 6,913 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge6 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 150 ms
35,004 KB |
| testcase_04 | AC | 2 ms
6,944 KB |
| testcase_05 | AC | 2 ms
6,940 KB |
| testcase_06 | AC | 2 ms
6,940 KB |
| testcase_07 | AC | 2 ms
6,940 KB |
| testcase_08 | AC | 2 ms
6,940 KB |
| testcase_09 | AC | 2 ms
6,944 KB |
| testcase_10 | AC | 2 ms
6,940 KB |
| testcase_11 | AC | 2 ms
6,940 KB |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | AC | 2 ms
6,940 KB |
| testcase_14 | AC | 2 ms
6,940 KB |
| testcase_15 | AC | 2 ms
6,940 KB |
| testcase_16 | AC | 2 ms
6,940 KB |
| testcase_17 | AC | 2 ms
6,940 KB |
| testcase_18 | AC | 2 ms
6,944 KB |
| testcase_19 | AC | 2 ms
6,940 KB |
| testcase_20 | AC | 2 ms
6,940 KB |
| testcase_21 | AC | 149 ms
33,796 KB |
| testcase_22 | AC | 97 ms
21,908 KB |
| testcase_23 | AC | 148 ms
33,408 KB |
| testcase_24 | AC | 66 ms
18,972 KB |
| testcase_25 | AC | 144 ms
33,696 KB |
| testcase_26 | AC | 153 ms
34,184 KB |
| testcase_27 | AC | 2 ms
6,944 KB |
ソースコード
#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>
#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 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 pdd = pair<long double, long double>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using ppi = pair<P,int>;
using pip = pair<int,P>;
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;
const char _ = ' ';
template<typename T>void o(T a);
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){rep(i,v.size())os<<v[i]<<(i+1==v.size()?"":" ");}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){for(auto &e:v)o(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());}
void revs(string &s) {reverse(s.begin(),s.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;}
void o(){cout<<"!?"<<endl;}
template<typename T>void o(T a){cout<<a<<endl;}
template<typename T,typename U>void o2(T a,U b){cout<<a<<_<<b<<endl;}
template<typename T,typename U>void o2(pair<T,U> a){o2(a.first,a.second);}
template<typename T,typename U,typename V>void o3(T a,U b,V c){cout<<a<<_<<b<<_<<c<<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();}
template<typename T>void dame(bool t, T s){if(!t){cout << s << endl;exit(0);}}
void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);}
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 gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mpow(ll x,ll n,ll m){if(n==0)return 1LL;x%=m;ll a=mpow(x,n/2,m);a=a*a%m;return (n&1)?a*x%m:a;}
template<typename T> ll tentou(vector<T> ar){
int n = ar.size();
set<T> st;
rep(i,n) st.insert(ar[i]);
map<T,int> mp;
int ind = 0;
for (T 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;
}
struct edge{
int from, to;
long long cost;
edge(int _from = -1, int _to = -1, long long _cost = 1LL) : from(_from), to(_to), cost(_cost) {}
};
struct vertex{
vector<edge> adj;
};
struct Graph{
int n;
vector<vertex> vs;
void add_edge(int from, int to, long long cost = 1LL){
assert(0 <= from && from < n);
assert(0 <= to && to < n);
vs[from].adj.emplace_back(edge(from,to,cost));
}
void add_dual_edge(int from, int to, long long cost = 1LL){
assert(0 <= from && from < n);
assert(0 <= to && to < n);
vs[from].adj.emplace_back(edge(from,to,cost));
vs[to].adj.emplace_back(edge(to,from,cost));
}
Graph(int _n) : n(_n) , vs(n) {}
vector<long long> dijkstra(int s){
using pli = pair<long long, int>;
priority_queue<pli, vector<pli>, greater<pli>> pque;
vector<long long> dist(n,inf);
dist[s] = 0LL;
pque.push(pli(0,s));
while (!pque.empty()){
pli p = pque.top(); pque.pop();
if (dist[p.second] < p.first) continue;
for (edge x : vs[p.second].adj){
if (dist[x.to] > p.first + x.cost){
dist[x.to] = p.first + x.cost;
pque.push(pli(dist[x.to],x.to));
}
}
}
return dist;
}
vector<long long> bfs01(int s){
deque<int> que;
vector<long long> dist(n,inf);
dist[s] = 0LL;
que.push_front(s);
while (!que.empty()){
int p = que.front(); que.pop_front();
for (edge x : vs[p].adj){
if (dist[x.to] > dist[p] + x.cost){
dist[x.to] = dist[p] + x.cost;
if (x.cost == 0LL) que.push_front(x.to);
else que.push_back(x.to);
}
}
}
return dist;
}
vector<int> dfs(int s){
vector<int> ans;
vector<int> vis(n,0);
_dfs(s,ans,vis);
return ans;
}
private:
void _dfs(int s, vector<int> &ans, vector<int> &vis){
vis[s]++;
for (edge x : vs[s].adj){
if (vis[x.to] == 0){
_dfs(x.to,ans,vis);
}
}
ans.emplace_back(s);
}
};
struct Tree{
Tree(int _n, int _root = 0) : n(_n), root(_root) {
assert(0 <= root && root < n);
initialize();
}
void add_edge(int from, int to, long long cost = 1LL){
assert(0 <= from && from < n);
assert(0 <= to && to < n);
vs[from].adj.emplace_back(edge(from,to,cost));
}
void add_dual_edge(int from, int to, long long cost = 1LL){
assert(0 <= from && from < n);
assert(0 <= to && to < n);
vs[from].adj.emplace_back(edge(from,to,cost));
vs[to].adj.emplace_back(edge(to,from,cost));
}
int size(){return n;}
int parent(int v){
assert(0 <= v && v < n);
if (is_done_par_rdist_init == false) par_rdist_init();
return par[v];
}
int depth(int v){
assert(0 <= v && v < n);
if (dep[v] != -1) return dep[v];
if (v == root) return dep[v] = 0;
return dep[v] = depth(parent(v)) + 1;
}
int subtree_size(int v){
assert(0 <= v && v < n);
if (sub[v] != 0) return sub[v];
sub[v] = 1;
for (edge x : vs[v].adj){
if (x.to != parent(v)) sub[v] += subtree_size(x.to);
}
return sub[v];
}
int lca(int u, int v){
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (is_done_lca_init == false) lca_init();
if (depth(u) > depth(v)) swap(u,v);
for (int i = 0; i < 30; i++) if ((depth(v) - depth(u)) >> i & 1) v = par2[i][v];
if (u == v) return u;
for (int k = 29; k >= 0; k--){
if (par2[k][u] != par2[k][v]) {
u = par2[k][u];
v = par2[k][v];
}
}
return par2[0][u];
}
long long dist(int u, int v){
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (is_done_par_rdist_init == false) par_rdist_init();
return rdist[u] + rdist[v] - rdist[lca(u,v)] * 2LL;
}
vector<int> path(int f, int t){
assert(0 <= f && f < n);
assert(0 <= t && t < n);
int v = lca(f,t);
vector<int> fp = {f};
vector<int> tp = {t};
int fn = f, tn = t;
while (fn != v){
fn = parent(fn);
fp.emplace_back(fn);
}
while (tn != v){
tn = parent(tn);
tp.emplace_back(tn);
}
for (int i = int(tp.size()) - 2; i >= 0; i--){
fp.emplace_back(tp[i]);
}
return fp;
}
vector<long long> alldists(int v){
assert(0 <= v && v < n);
if (v == 0) return rdist;
vector<long long> dists(n,1e18);
vector<int> vis(n,0);
dists[v] = 0LL;
queue<int> que;
que.push(v);
while (!que.empty()){
int p = que.front(); que.pop();
vis[p]++;
for (edge x : vs[p].adj){
if (vis[x.to] == 0){
dists[x.to] = dists[p] + x.cost;
que.push(x.to);
}
}
}
return dists;
}
vector<int> dfs(int v){
assert(0 <= v && v < n);
vector<int> ans;
vector<int> vis(n,0);
_dfs(v,vis,ans);
return ans;
}
vector<vertex> vs;
private:
int n;
int root;
bool is_done_lca_init;
bool is_done_par_rdist_init;
vector<int> par;
vector<int> dep;
vector<int> sub;
vector<long long> rdist;
vector<vector<int>> par2;
void initialize(){
is_done_lca_init = false;
is_done_par_rdist_init = false;
vs.resize(n);
dep.resize(n,-1);
sub.resize(n,0);
}
void lca_init(){
par2.resize(30,vector<int>(n,-1));
for (int i = 0; i < n; i++) par2[0][i] = parent(i);
for (int i = 0; i < 29 ; i++) {
for (int j = 0; j < n; j++) {
if (par2[i][j] < 0) par2[i+1][j] = -1;
else par2[i+1][j] = par2[i][par2[i][j]];
}
}
is_done_lca_init = true;
}
void par_rdist_init(){
par.resize(n,-2);
rdist.resize(n,-1);
par[root] = -1;
rdist[root] = 0;
queue<int> que;
que.push(root);
while (!que.empty()){
int p = que.front(); que.pop();
for (edge x : vs[p].adj){
if (par[x.to] == -2){
par[x.to] = p;
rdist[x.to] = rdist[p] + x.cost;
que.push(x.to);
}
}
}
is_done_par_rdist_init = true;
}
void _dfs(int v, vector<int> &vis, vector<int> &ans){
vis[v]++;
for (edge x : vs[v].adj){
if (vis[x.to] == 0) _dfs(x.to,vis,ans);
}
ans.emplace_back(v);
}
};
template<typename T> struct doubling{
vector<T> vec;
doubling (vector<T> _vec) : vec(_vec) {}
map<T,ll> mp;
ll length_of_loop = -1;
ll top_of_loop = -1;
void init(){
ll ind = 0;
for (T x : vec){
if (mp.find(x) == mp.end()) mp[x] = ind, ind++;
else {
length_of_loop = ind - mp[x];
top_of_loop = mp[x];
break;
}
}
}
ll len(){
if (length_of_loop == -1) init();
return length_of_loop;
}
ll top(){
if (top_of_loop == -1) init();
return top_of_loop;
}
T get(ll n){
assert(0 <= n);
if (n < top()) return vec[n];
ll d = n - top();
return vec[top() + (d % len())];
}
};
struct Mo{
vector<int> left, right, order, v;
int width, nl, nr, ptr;
Mo (int n = 0) : width(sqrt(n)), nl(0), nr(0), ptr(0), left(0), right(0), v(n,-1) {}
void insert(int l, int r){ // [l,r)
left.emplace_back(l);
right.emplace_back(r);
}
void build(){ // sort all query
order.resize(left.size());
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](int a, int b){
if(left[a] / width != left[b] / width) return left[a] < left[b];
return right[a] < right[b];
});
}
int process(){ // do 1 query
if (ptr == int(order.size())) return -1;
const int id = order[ptr];
while (nl > left[id]) distribute(--nl);
while (nl < left[id]) distribute(nl++);
while (nr > right[id]) distribute(--nr);
while (nr < right[id]) distribute(nr++);
return order[ptr++];
}
inline void distribute(int idx){ // x x x (nl) o o o (nr) x x ...
v[idx] *= -1;
if (v[idx] == 1) add(idx);
else del(idx);
}
void add(int idx);
void del(int idx);
};
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" : " ");
}
}
}
};
template<class S, S op(S l, S r), S e()> struct Rui{
/*
- op(e,x) = op(x,e) = x
- op(l,opinv(l,lr)) = lr
*/
int n;
vector<S> vec, lrui, rrui;
Rui (vector<S> _vec) : n(int(_vec.size())), vec(_vec) {
lrui.resize(n+1), rrui.resize(n+1);
lrui[0] = rrui[n] = e();
for (int i = 0; i < n; i++) lrui[i+1] = op(lrui[i],vec[i]);
for (int i = n; i > 0; i--) rrui[i-1] = op(rrui[i],vec[i-1]);
}
template<S opinv(S l, S lr)> S prod(int l, int r = -1){ // [l,r)
if (r == -1) return vec[l];
return opinv(lrui[l],lrui[r]);
}
S nprod(int l, int r = -1){ // [0,l) * [r,n)
if (r == -1) r = l+1;
return op(lrui[l],rrui[r]);
}
};
struct MINT998244353{
using mint = modint998244353;
vector<mint> kaijo, kainv;
int N;
MINT998244353 (int lim = 200000) : N(lim), kaijo(lim+1,1), kainv(lim+1,1) {
rep(i,N) kaijo[i+1] = kaijo[i] * (i+1);
rep(i,N) kainv[i+1] = kainv[i] / (i+1);
}
mint factrial(int x){return kaijo[x];}
mint inv_factorial(int x){return kainv[x];}
mint ncr(int n, int r){return kaijo[n] * kainv[r] * kainv[n-r];}
template<typename T> vector<mint> beki(T r, int n = -1){
if (n == -1) n = N;
vector<mint> res(n+1,1);
rep(i,n) res[i+1] = res[i] * mint(r);
return res;
}
vector<mint> vec_inv(vector<mint> &a){
vector<mint> res(a.size());
rep(i,int(a.size())) res[i] = a[i].inv();
return res;
}
};
struct MINT1000000007{
using mint = modint1000000007;
vector<mint> kaijo, kainv;
int N;
MINT1000000007 (int lim = 200000) : N(lim), kaijo(lim+1,1), kainv(lim+1,1) {
rep(i,N) kaijo[i+1] = kaijo[i] * (i+1);
rep(i,N) kainv[i+1] = kainv[i] / (i+1);
}
mint factrial(int x){return kaijo[x];}
mint inv_factorial(int x){return kainv[x];}
mint ncr(int n, int r){
if (n < r) return mint(0);
return kaijo[n] * kainv[r] * kainv[n-r];
}
template<typename T> vector<mint> beki(T r, int n = -1){
if (n == -1) n = N;
vector<mint> res(n+1,1);
rep(i,n) res[i+1] = res[i] * mint(r);
return res;
}
vector<mint> vec_inv(vector<mint> &a){
vector<mint> res(a.size());
rep(i,int(a.size())) res[i] = a[i].inv();
return res;
}
};
/*
int op(int a, int b){return a + b;}
int e(){return 0;}
int opinv(int a, int ab){return ab - a;}
*/
template<typename T> void vmint(vector<T> &v){
int n = v.size();
if (n == 0) {
cout << endl;
return ;
}
rep(i,n) cout << v[i].val() << (i < n-1 ? " " : "\n");
}
template<typename T> void vvmint(vector<vector<T>> &v){
int n = v.size();
if (n == 0) {
cout << endl;
return ;
}
rep(i,n) vmint(v[i]);
}
void solve(){
int n; cin >> n;
ll s; cin >> s;
vector<ll> a(n); cin >> a;
if (n == 1){
ll ans = 0;
ll ima = a[0];
while (ima <= s) ans++, ima *= a[0];
o(ans);
return ;
}
vector<ll> le, ri;
int h = n/2;
queue<pil> que;
que.push(pil(0,0));
while (!que.empty()){
pil p = que.front(); que.pop();
if (p.first == h){
le.emplace_back(p.second);
}
else {
ll pl = a[p.first];
while (p.second + pl <= s){
que.push(pil(p.first+1,p.second+pl));
pl *= a[p.first];
}
}
}
que.push(pil(h,0));
while (!que.empty()){
pil p = que.front(); que.pop();
if (p.first == n){
ri.emplace_back(p.second);
}
else {
ll pl = a[p.first];
while (p.second + pl <= s){
que.push(pil(p.first+1,p.second+pl));
pl *= a[p.first];
}
}
}
if (ri.empty() || le.empty()){
o(0);
return ;
}
sor(le), sor(ri);
ll ans = 0;
for (ll x : le){
ans += ll(upper_bound(ri.begin(),ri.end(),s-x) - ri.begin());
}
o(ans);
}
int main(){
fast_io();
int t = 1; //cin >> t;
while (t--) solve();
}