Product of last k

mail@pastecode.io avatar
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;
}