2c9a31df16 2015-06-20 kinaba: #include <iostream> 2c9a31df16 2015-06-20 kinaba: #include <sstream> 2c9a31df16 2015-06-20 kinaba: #include <iomanip> 2c9a31df16 2015-06-20 kinaba: #include <vector> 2c9a31df16 2015-06-20 kinaba: #include <string> 2c9a31df16 2015-06-20 kinaba: #include <map> 2c9a31df16 2015-06-20 kinaba: #include <set> 2c9a31df16 2015-06-20 kinaba: #include <algorithm> 2c9a31df16 2015-06-20 kinaba: #include <numeric> 2c9a31df16 2015-06-20 kinaba: #include <iterator> 2c9a31df16 2015-06-20 kinaba: #include <functional> 2c9a31df16 2015-06-20 kinaba: #include <complex> 2c9a31df16 2015-06-20 kinaba: #include <queue> 2c9a31df16 2015-06-20 kinaba: #include <stack> 2c9a31df16 2015-06-20 kinaba: #include <cmath> 2c9a31df16 2015-06-20 kinaba: #include <cassert> 2c9a31df16 2015-06-20 kinaba: #include <tuple> 2c9a31df16 2015-06-20 kinaba: using namespace std; 2c9a31df16 2015-06-20 kinaba: typedef long long LL; 2c9a31df16 2015-06-20 kinaba: typedef complex<double> CMP; 2c9a31df16 2015-06-20 kinaba: 2c9a31df16 2015-06-20 kinaba: static unsigned MODVAL; 2c9a31df16 2015-06-20 kinaba: struct mint 2c9a31df16 2015-06-20 kinaba: { 2c9a31df16 2015-06-20 kinaba: unsigned val; 2c9a31df16 2015-06-20 kinaba: mint():val(0){} 2c9a31df16 2015-06-20 kinaba: mint(int x):val(x%MODVAL) {} 2c9a31df16 2015-06-20 kinaba: mint(unsigned x):val(x%MODVAL) {} 2c9a31df16 2015-06-20 kinaba: mint(LL x):val(x%MODVAL) {} 2c9a31df16 2015-06-20 kinaba: }; 2c9a31df16 2015-06-20 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 2c9a31df16 2015-06-20 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 2c9a31df16 2015-06-20 kinaba: mint operator+(mint x, mint y) { return x+=y; } 2c9a31df16 2015-06-20 kinaba: mint operator*(mint x, mint y) { return x*=y; } 2c9a31df16 2015-06-20 kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } 2c9a31df16 2015-06-20 kinaba: 2c9a31df16 2015-06-20 kinaba: class ColorfulLineGraphs { public: 2c9a31df16 2015-06-20 kinaba: int countWays(long long N, long long K, int M) 2c9a31df16 2015-06-20 kinaba: { 2c9a31df16 2015-06-20 kinaba: MODVAL = M; 2c9a31df16 2015-06-20 kinaba: --K; 2c9a31df16 2015-06-20 kinaba: 2c9a31df16 2015-06-20 kinaba: // The problem reduces to 2c9a31df16 2015-06-20 kinaba: // (K+1)(2K+1)(3K+1) ... (NK+1) 2c9a31df16 2015-06-20 kinaba: // and note that 2c9a31df16 2015-06-20 kinaba: // (MK+1) == 1 mod M 2c9a31df16 2015-06-20 kinaba: mint v_rem = 1; 2c9a31df16 2015-06-20 kinaba: for(LL n=N/M*M; n<=N; ++n) 2c9a31df16 2015-06-20 kinaba: v_rem *= mint(n)*K + 1; 2c9a31df16 2015-06-20 kinaba: 2c9a31df16 2015-06-20 kinaba: mint v = 1; 2c9a31df16 2015-06-20 kinaba: for(int n=1; n<M; ++n) 2c9a31df16 2015-06-20 kinaba: v *= mint(n)*K + 1; 2c9a31df16 2015-06-20 kinaba: return (v_rem * POW(v,N/M)).val; 2c9a31df16 2015-06-20 kinaba: } 2c9a31df16 2015-06-20 kinaba: }; 2c9a31df16 2015-06-20 kinaba: 2c9a31df16 2015-06-20 kinaba: // BEGIN CUT HERE 2c9a31df16 2015-06-20 kinaba: #include <ctime> 2c9a31df16 2015-06-20 kinaba: double start_time; string timer() 2c9a31df16 2015-06-20 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 2c9a31df16 2015-06-20 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 2c9a31df16 2015-06-20 kinaba: { os << "{ "; 2c9a31df16 2015-06-20 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 2c9a31df16 2015-06-20 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 2c9a31df16 2015-06-20 kinaba: void verify_case(const int& Expected, const int& Received) { 2c9a31df16 2015-06-20 kinaba: bool ok = (Expected == Received); 2c9a31df16 2015-06-20 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 2c9a31df16 2015-06-20 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 2c9a31df16 2015-06-20 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 2c9a31df16 2015-06-20 kinaba: #define END verify_case(_, ColorfulLineGraphs().countWays(N, K, M));} 2c9a31df16 2015-06-20 kinaba: int main(){ 2c9a31df16 2015-06-20 kinaba: 2c9a31df16 2015-06-20 kinaba: CASE(0) 2c9a31df16 2015-06-20 kinaba: long long N = 3LL; 2c9a31df16 2015-06-20 kinaba: long long K = 2LL; 2c9a31df16 2015-06-20 kinaba: int M = 100000; 2c9a31df16 2015-06-20 kinaba: int _ = 24; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: CASE(1) 2c9a31df16 2015-06-20 kinaba: long long N = 15LL; 2c9a31df16 2015-06-20 kinaba: long long K = 3LL; 2c9a31df16 2015-06-20 kinaba: int M = 1000000; 2c9a31df16 2015-06-20 kinaba: int _ = 510625; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: CASE(2) 2c9a31df16 2015-06-20 kinaba: long long N = 100000LL; 2c9a31df16 2015-06-20 kinaba: long long K = 100000LL; 2c9a31df16 2015-06-20 kinaba: int M = 999999; 2c9a31df16 2015-06-20 kinaba: int _ = 185185; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: CASE(3) 2c9a31df16 2015-06-20 kinaba: long long N = 1000000000000LL; 2c9a31df16 2015-06-20 kinaba: long long K = 6LL; 2c9a31df16 2015-06-20 kinaba: int M = 1000000; 2c9a31df16 2015-06-20 kinaba: int _ = 109376; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: CASE(4) 2c9a31df16 2015-06-20 kinaba: long long N = 5000LL; 2c9a31df16 2015-06-20 kinaba: long long K = 1000000000000LL; 2c9a31df16 2015-06-20 kinaba: int M = 314159; 2c9a31df16 2015-06-20 kinaba: int _ = 202996; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: /* 2c9a31df16 2015-06-20 kinaba: CASE(5) 2c9a31df16 2015-06-20 kinaba: long long N = LL; 2c9a31df16 2015-06-20 kinaba: long long K = LL; 2c9a31df16 2015-06-20 kinaba: int M = ; 2c9a31df16 2015-06-20 kinaba: int _ = ; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: CASE(6) 2c9a31df16 2015-06-20 kinaba: long long N = LL; 2c9a31df16 2015-06-20 kinaba: long long K = LL; 2c9a31df16 2015-06-20 kinaba: int M = ; 2c9a31df16 2015-06-20 kinaba: int _ = ; 2c9a31df16 2015-06-20 kinaba: END 2c9a31df16 2015-06-20 kinaba: */ 2c9a31df16 2015-06-20 kinaba: } 2c9a31df16 2015-06-20 kinaba: // END CUT HERE