cc4202a4a6 2015-08-22 kinaba: #include <iostream> cc4202a4a6 2015-08-22 kinaba: #include <sstream> cc4202a4a6 2015-08-22 kinaba: #include <iomanip> cc4202a4a6 2015-08-22 kinaba: #include <vector> cc4202a4a6 2015-08-22 kinaba: #include <string> cc4202a4a6 2015-08-22 kinaba: #include <map> cc4202a4a6 2015-08-22 kinaba: #include <set> cc4202a4a6 2015-08-22 kinaba: #include <algorithm> cc4202a4a6 2015-08-22 kinaba: #include <numeric> cc4202a4a6 2015-08-22 kinaba: #include <iterator> cc4202a4a6 2015-08-22 kinaba: #include <functional> cc4202a4a6 2015-08-22 kinaba: #include <complex> cc4202a4a6 2015-08-22 kinaba: #include <queue> cc4202a4a6 2015-08-22 kinaba: #include <stack> cc4202a4a6 2015-08-22 kinaba: #include <cmath> cc4202a4a6 2015-08-22 kinaba: #include <cassert> cc4202a4a6 2015-08-22 kinaba: #include <tuple> cc4202a4a6 2015-08-22 kinaba: using namespace std; cc4202a4a6 2015-08-22 kinaba: typedef long long LL; cc4202a4a6 2015-08-22 kinaba: typedef complex<double> CMP; cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: static const unsigned MODVAL = 1000000007; cc4202a4a6 2015-08-22 kinaba: struct mint cc4202a4a6 2015-08-22 kinaba: { cc4202a4a6 2015-08-22 kinaba: unsigned val; cc4202a4a6 2015-08-22 kinaba: mint():val(0){} cc4202a4a6 2015-08-22 kinaba: mint(int x):val(x%MODVAL) {} cc4202a4a6 2015-08-22 kinaba: mint(unsigned x):val(x%MODVAL) {} cc4202a4a6 2015-08-22 kinaba: mint(LL x):val(x%MODVAL) {} cc4202a4a6 2015-08-22 kinaba: }; cc4202a4a6 2015-08-22 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } cc4202a4a6 2015-08-22 kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } cc4202a4a6 2015-08-22 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } cc4202a4a6 2015-08-22 kinaba: mint operator+(mint x, mint y) { return x+=y; } cc4202a4a6 2015-08-22 kinaba: mint operator-(mint x, mint y) { return x-=y; } cc4202a4a6 2015-08-22 kinaba: mint operator*(mint x, mint y) { return x*=y; } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } cc4202a4a6 2015-08-22 kinaba: mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } cc4202a4a6 2015-08-22 kinaba: mint operator/(mint x, mint y) { return x/=y; } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: vector<mint> FAC_(1,1); cc4202a4a6 2015-08-22 kinaba: mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.size()) ); return FAC_[n]; } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: // nCk :: O(log MODVAL) time, O(n) space. cc4202a4a6 2015-08-22 kinaba: mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: // nCk :: O(1) time, O(n^2) space. cc4202a4a6 2015-08-22 kinaba: vector< vector<mint> > CP_; cc4202a4a6 2015-08-22 kinaba: mint C(int n, int k) { cc4202a4a6 2015-08-22 kinaba: while( CP_.size() <= n ) { cc4202a4a6 2015-08-22 kinaba: int nn = CP_.size(); cc4202a4a6 2015-08-22 kinaba: CP_.push_back(vector<mint>(nn+1,1)); cc4202a4a6 2015-08-22 kinaba: for(int kk=1; kk<nn; ++kk) cc4202a4a6 2015-08-22 kinaba: CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: return k<0 || n<k ? 0 : CP_[n][k]; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: class ChangingChange { public: cc4202a4a6 2015-08-22 kinaba: vector <int> countWays(vector <int> ways, vector <int> valueRemoved, vector <int> numRemoved) cc4202a4a6 2015-08-22 kinaba: { cc4202a4a6 2015-08-22 kinaba: const int D = ways.size()-1; cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: vector<mint> coins(1, 0); cc4202a4a6 2015-08-22 kinaba: for(int v=1; v<=D; ++v) cc4202a4a6 2015-08-22 kinaba: coins.push_back(ways[v] - eval(coins,v)); cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: vector<int> ans; cc4202a4a6 2015-08-22 kinaba: for(int q=0; q<valueRemoved.size(); ++q) { cc4202a4a6 2015-08-22 kinaba: const int v=valueRemoved[q], n=numRemoved[q]; cc4202a4a6 2015-08-22 kinaba: coins[v] -= n; // or += MODVAL-n, meaning mult (1+x^v)^(MODVAL-n) cc4202a4a6 2015-08-22 kinaba: // then if cur is known and (1+x^v)^(MODVAL-n) is known, cc4202a4a6 2015-08-22 kinaba: // O(D) to calc eval(coins,D) cc4202a4a6 2015-08-22 kinaba: ans.push_back(eval(coins,D).val); cc4202a4a6 2015-08-22 kinaba: coins[v] += n; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: return ans; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: // Calc \Pi_v (1 + x^v)^c[v] 's coeefficient at x^D cc4202a4a6 2015-08-22 kinaba: // c[v] may be very large cc4202a4a6 2015-08-22 kinaba: // D <= 2000 cc4202a4a6 2015-08-22 kinaba: // v <= 2000 cc4202a4a6 2015-08-22 kinaba: mint eval(const vector<mint>& c, int D) cc4202a4a6 2015-08-22 kinaba: { cc4202a4a6 2015-08-22 kinaba: vector<mint> cur(D+1, 0); cc4202a4a6 2015-08-22 kinaba: cur[0] = 1; cc4202a4a6 2015-08-22 kinaba: for(int v=1; v<c.size(); ++v) { cc4202a4a6 2015-08-22 kinaba: cur = polymul(cur, polypow(v, c[v].val, D), D); cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: return D<cur.size() ? cur[D] : 0; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: vector<mint> polymul(const vector<mint>& a, const vector<mint>& b, int D) cc4202a4a6 2015-08-22 kinaba: { cc4202a4a6 2015-08-22 kinaba: int maxD = max<int>(D, (a.size()-1)*(b.size()-1)); cc4202a4a6 2015-08-22 kinaba: vector<mint> c(maxD+1); cc4202a4a6 2015-08-22 kinaba: for(int i=0; i<a.size(); ++i) cc4202a4a6 2015-08-22 kinaba: for(int k=0; k<b.size(); ++k) cc4202a4a6 2015-08-22 kinaba: if(i+k<=maxD) cc4202a4a6 2015-08-22 kinaba: c[i+k] += a[i]*b[k]; cc4202a4a6 2015-08-22 kinaba: return c; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: vector<mint> polypow(int V, int K, int D) cc4202a4a6 2015-08-22 kinaba: { cc4202a4a6 2015-08-22 kinaba: vector<mint> poly; cc4202a4a6 2015-08-22 kinaba: // (1+x^V)^K upto x^D cc4202a4a6 2015-08-22 kinaba: mint Ckd = 1; cc4202a4a6 2015-08-22 kinaba: for(int d=0; d<=K; ++d) { cc4202a4a6 2015-08-22 kinaba: LL dd = LL(d)*V; cc4202a4a6 2015-08-22 kinaba: if(dd > D) cc4202a4a6 2015-08-22 kinaba: break; cc4202a4a6 2015-08-22 kinaba: poly.resize(int(dd)+1); cc4202a4a6 2015-08-22 kinaba: poly[int(dd)] = Ckd; cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: Ckd *= (K-d); cc4202a4a6 2015-08-22 kinaba: Ckd /= (d+1); cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: return poly; cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: }; cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: // BEGIN CUT HERE cc4202a4a6 2015-08-22 kinaba: #include <ctime> cc4202a4a6 2015-08-22 kinaba: double start_time; string timer() cc4202a4a6 2015-08-22 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } cc4202a4a6 2015-08-22 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) cc4202a4a6 2015-08-22 kinaba: { os << "{ "; cc4202a4a6 2015-08-22 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) cc4202a4a6 2015-08-22 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } cc4202a4a6 2015-08-22 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { cc4202a4a6 2015-08-22 kinaba: bool ok = (Expected == Received); cc4202a4a6 2015-08-22 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cc4202a4a6 2015-08-22 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } cc4202a4a6 2015-08-22 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); cc4202a4a6 2015-08-22 kinaba: #define END verify_case(_, ChangingChange().countWays(ways, valueRemoved, numRemoved));} cc4202a4a6 2015-08-22 kinaba: int main(){ cc4202a4a6 2015-08-22 kinaba: cc4202a4a6 2015-08-22 kinaba: CASE(0) cc4202a4a6 2015-08-22 kinaba: int ways_[] = {1, 4, 6}; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = {1, 1, 1}; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = {1, 2, 3}; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = {3, 1, 0 }; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: CASE(1) cc4202a4a6 2015-08-22 kinaba: int ways_[] = {1, 2, 1, 0, 0, 0, 0, 0, 7}; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = {8, 8, 1, 1}; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = {1, 7, 1, 2}; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = {6, 0, 7, 7 }; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: CASE(2) cc4202a4a6 2015-08-22 kinaba: int ways_[] = {1, 2, 3, 6, 9, 14}; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = {1, 1, 1, 1, 1, 2, 2, 2, 2, 2}; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = {9, 10, 11, 12, 13, 6, 8, 8, 10, 12 }; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: CASE(3) cc4202a4a6 2015-08-22 kinaba: int ways_[] = {1, 0}; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = {1, 1}; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = {1, 1000000}; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = {1000000006, 999000007 }; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: CASE(4) cc4202a4a6 2015-08-22 kinaba: int ways_[] = {1, 2, 3, 6, 9, 14}; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = {1, 3, 5}; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = {1000000, 4, 2}; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = {34955525, 2, 12 }; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: /* cc4202a4a6 2015-08-22 kinaba: CASE(5) cc4202a4a6 2015-08-22 kinaba: int ways_[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: CASE(6) cc4202a4a6 2015-08-22 kinaba: int ways_[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> ways(ways_, ways_+sizeof(ways_)/sizeof(*ways_)); cc4202a4a6 2015-08-22 kinaba: int valueRemoved_[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> valueRemoved(valueRemoved_, valueRemoved_+sizeof(valueRemoved_)/sizeof(*valueRemoved_)); cc4202a4a6 2015-08-22 kinaba: int numRemoved_[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> numRemoved(numRemoved_, numRemoved_+sizeof(numRemoved_)/sizeof(*numRemoved_)); cc4202a4a6 2015-08-22 kinaba: int __[] = ; cc4202a4a6 2015-08-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); cc4202a4a6 2015-08-22 kinaba: END cc4202a4a6 2015-08-22 kinaba: */ cc4202a4a6 2015-08-22 kinaba: } cc4202a4a6 2015-08-22 kinaba: // END CUT HERE