Product of last k
unknown
c_cpp
a year ago
2.3 kB
13
Indexable
Never
#include <bits/stdc++.h> using namespace std; class ProductOfKNumbers { public: long long mod; vector<long long> st; stack<long long> zero; long long idx; ProductOfKNumbers() { mod=1000000007; idx=0; } long long pwr(long long base,long long idx) { if(idx==0) return 1; if(idx%2) { long long small=pwr(base,idx-1)%mod; small=(small*base)%mod; return small; } else { long long small=pwr(base,idx/2)%mod; small=(small*small)%mod; return small; } } void add(int num) { if(num==0) { zero.push(idx++); num=1; long long last=(st.empty())?num:(st.back()*num)%mod; st.push_back(last); } else { long long last=(st.empty())?num:(st.back()*num)%mod; st.push_back(last); idx++; } } int getProduct(int k) { if(zero.empty()) { long long ign=idx-k-1; long long tot=st.back(); long long den=st[ign]; long long ans=tot; if(ign<0) return ans; ans=(ans*pwr(den,mod-2)%mod)%mod; ans=ans%mod; ans=(ans+mod)%mod; return ans; } else { long long ign=idx-k-1; if(zero.top()>ign) { return 0; } else { long long tot=st.back(); long long den=st[ign]; long long ans=tot; ans=(ans*pwr(den,mod-2)%mod)%mod; ans=ans%mod; ans=(ans+mod)%mod; return ans; } } } }; int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); int Q; cin >> Q; ProductOfKNumbers productOfKNumbers; while(Q--) { string op; cin >> op; if (op == "add") { int num; cin >> num; productOfKNumbers.add(num); } else { int k; cin >> k; cout << productOfKNumbers.getProduct(k) << "\n"; } } return 0; }