ADDED   SRM/565-U/1A.cpp
Index: SRM/565-U/1A.cpp
==================================================================
--- SRM/565-U/1A.cpp
+++ SRM/565-U/1A.cpp
@@ -0,0 +1,117 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class MonstersValley { public:
+	int minimumPrice(vector<long long> dread, vector <int> price)
+	{
+		const int N = dread.size();
+
+		map<int, LL> p2maxd;
+		p2maxd[0] = 0;
+
+		for(int i=0; i<N; ++i) {
+			map<int,LL> neo;
+			for(map<int,LL>::iterator it=p2maxd.begin(); it!=p2maxd.end(); ++it)
+			{
+				int p = it->first;
+				LL md = it->second;
+				if( md >= dread[i] )
+					neo[p] = max(neo[p], md);
+				p += price[i];
+				md += dread[i];
+				neo[p] = max(neo[p], md);
+			}
+			p2maxd.swap(neo);
+		}
+
+		return p2maxd.begin()->first;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, MonstersValley().minimumPrice(dread, price));}
+int main(){
+
+CASE(0)
+	long long dread_[] = {8, 5, 10};
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = {1, 1, 2};
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = 2; 
+END
+CASE(0)
+	long long dread_[] = {1, 1};
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = {1, 1};
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = 1; 
+END
+CASE(1)
+	long long dread_[] = {1, 2, 4, 1000000000};
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = {1, 1, 1, 2};
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = 5; 
+END
+CASE(2)
+	long long dread_[] = {200, 107, 105, 206, 307, 400};
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = {1, 2, 1, 1, 1, 2};
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = 2; 
+END
+CASE(3)
+	long long dread_[] = {5216, 12512, 613, 1256, 66, 17202, 30000, 23512, 2125, 33333};
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = {2, 2, 1, 1, 1, 1, 2, 1, 2, 1};
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = 5; 
+END
+/*
+CASE(4)
+	long long dread_[] = ;
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = ;
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = ; 
+END
+CASE(5)
+	long long dread_[] = ;
+	  vector<long long> dread(dread_, dread_+sizeof(dread_)/sizeof(*dread_)); 
+	int price_[] = ;
+	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/565-U/1B.cpp
Index: SRM/565-U/1B.cpp
==================================================================
--- SRM/565-U/1B.cpp
+++ SRM/565-U/1B.cpp
@@ -0,0 +1,186 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class TheDivisionGame { public:
+	long long countWinningIntervals(int L, int R)
+	{
+		// eratos ---------------------------------
+		vector<int> ps;
+		{
+			static const int N = 50000;
+			vector<bool> isp(N+1, true);
+			for(int p=2; p<=N; ++p)
+				if( isp[p] ) {
+					ps.push_back(p);
+					for(int q=p+p; q<=N; q+=p)
+						isp[q] = false;
+				}
+		}
+
+		// prime decomposition --------------------
+		vector< vector<int> > pd(R-L+1);
+		vector<int> rm(R-L+1);
+		for(int v=L; v<=R; ++v)
+			rm[v-L] = v;
+
+		for(int i=0; i<ps.size(); ++i)
+		{
+			int p = ps[i];
+			for(int q=(L+p-1)/p*p; q<=R; q+=p)
+			{
+				int& r = rm[q-L];
+				int qn = 0;
+				while(r%p==0) qn++, r/=p;
+				pd[q-L].push_back(qn);
+			}
+		}
+
+		for(int v=L; v<=R; ++v)
+			if(rm[v-L] > 1)
+				pd[v-L].push_back(1);
+
+		// grundy ------------------------------------
+		vector<int> nim;
+		for(int i=0; i<pd.size(); ++i) {
+			nim.push_back(nim_calc(pd[i]));
+		}
+
+		// xorsum ------------------------------------
+		vector<int> sum;
+		map<int, LL> hist;
+		sum.push_back(0);
+		hist[sum.back()] ++;
+		for(int i=0; i<nim.size(); ++i) {
+			sum.push_back(sum.back() ^ nim[i]);
+			hist[sum.back()] ++;
+		}
+
+		LL lose = 0;
+		for(map<int,LL>::iterator it=hist.begin(); it!=hist.end(); ++it)
+			lose += it->second * (it->second-1) / 2;
+		LL w = R-L+2;
+		LL total = w*(w-1)/2;
+		return total - lose;
+	}
+
+	int nim_calc(vector<int> sig)
+	{
+		if( sig.empty() )
+			return 0;
+		int v = sig[0];
+		for(int i=1; i<sig.size(); ++i)
+			v = merge(v, sig[i]);
+		return v;
+	}
+
+	map<pair<int,int>, int> memo;
+	int merge(int a, int b)
+	{
+		if(a>b) swap(a,b);
+		if(a==0)
+			return b;
+		pair<int,int> key(a,b);
+		if(memo.count(key))
+			return memo[key];
+
+		vector<bool> used;
+		for(int x=0; x<=a; ++x)
+		for(int y=0; y<=b; ++y)
+		if(x!=a || y!=b)
+		{
+			int k = merge(x, y);
+			if(used.size()<=k) used.resize(k+1);
+			used[k] = true;
+		}
+
+		used.push_back(false);
+		return memo[key] = find(used.begin(), used.end(), false) - used.begin();
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const long long& Expected, const long long& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, TheDivisionGame().countWinningIntervals(L, R));}
+int main(){
+CASE(0)
+	int L = 9; 
+	int R = 10; 
+	long long _ = 2LL; 
+END
+CASE(1)
+	int L = 2; 
+	int R = 5; 
+	long long _ = 9LL; 
+END
+CASE(2)
+	int L = 2; 
+	int R = 6; 
+	long long _ = 13LL; 
+END
+CASE(3)
+	int L = 2; 
+	int R = 100; 
+	long long _ = 4345LL; 
+END
+CASE(4)
+	int L = 12566125; 
+	int R = 12567777; 
+	long long _ = 1313432LL; 
+END
+CASE(5)
+	int L = 1000000000; 
+	int R = 1001000000; 
+	long long _ = -1LL; 
+END
+CASE(6)
+	int L = 2; 
+	int R = 2; 
+	long long _ = 0LL; 
+END
+CASE(6)
+	int L = 2; 
+	int R = 3; 
+	long long _ = 0LL; 
+END
+CASE(6)
+	int L = 2; 
+	int R = 4; 
+	long long _ = 3LL; 
+END
+CASE(6)
+	int L = 4; 
+	int R = 4; 
+	long long _ = 1LL; 
+END
+
+}
+// END CUT HERE

Index: lib/doc/nim.txt
==================================================================
--- lib/doc/nim.txt
+++ lib/doc/nim.txt
@@ -1,50 +1,93 @@
 // SRM338 Div1 LV3
 
-定理のステートメント
+-------------------------------------------------------------------------------------------
+対象となるゲーム
+  - 二人ゲーム
+  - 二人とも動かせる手の集合は同じ
+  - 動かせなくなった方が負け
+  - 無限ループしない
+
+nim
+  - n 個の石の山がある
+  - 一手で 1 ～ n 個取っていい
+  - 最後の石を取った方が勝ち（石がなくなって打つ手が無くなった方が負け）
+
+*n をサイズ n の山が1個だけの nim とする
+  - *0 は負け
+  - *n は勝ち n>=1
+
+-------------------------------------------------------------------------------------------
+ゲーム
+  - 状態 G から打てる手で遷移する先を G1, ..., Gk とする
+    G = {G1, ..., Gk} と書く
+
+ゲームの和
+  - G1 + G2 を、G1 と G2 の二つのゲームがあって、どちらかを選んで一手進められるゲームとする。
+    すなわち G1 + G2 = {(v,G2) | v∈G1} ∪ {(G1,u) | u∈G2} 
+
+等価
+  - 二つのゲームG, Fが等価なことを G ≡ F と書く
+    等価というのは勝ち負け一致よりもっと強い。二つのゲームの和 G+F が必敗になること。
+    たとえば *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
+    等価というのは可能な動きの構造がisomorphic/bisimilarというよりは弱い。
+    たとえば以下で示すように *1 + *3 ≡ *2 だが初手のパターン数など違う。
+
+-------------------------------------------------------------------------------------------
+定理：等価(和を取ると必敗) => 勝ち負け一致
+  - 必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を保てば勝てる。
+    ゆえに勝ち負けが一致しないなら和をとったゲームは必勝。
+      必敗 + 必敗 = 必敗
+      必勝 + 必敗 = 必勝
+
+    注意：
+      必勝 + 必勝 = 必敗
+    は成り立たない！ *2 + *1 は 初手で *1 + *1 に行けるのでこれは勝てる
+
+補題：G+G は必敗
+　- まねっこmoveをされると負けるしかない
+
+補題：A≡B ならば A+C≡B+C
+  - A+C+B+C = (A+B)+(C+C) = 必敗+必敗 = 必敗
+
+補題：A≡B ならば {A,G1,G2,...}≡{B,G1,G2,...}
+　- {A,G1,G2,...}+{B,G1,G2,...} は必敗。なぜならこちらがどう動かしても
+    A+B, G1+G1, G2+G2, ... のいずれかの必敗状態に遷移させられるから。
+
+-------------------------------------------------------------------------------------------
+定理【ゲームの和はxor】
+  - *n1 + *n2 = *(n1 xor n2)
+  - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2)
+
+  証明
+    - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。
 
-    対象となるゲーム
-      - 二人ゲーム
-      - 二人とも動かせる手の集合は同じ
-      - 動かせなくなった方が負け
-      - 無限ループしない
+
 
-    nim
-      - サイズ s1, s2, .., sk の山がある
-      - どれか一つ山を選んで 1 ～ 山サイズ の任意個取り除ける
-      - 最後の山を取った方が勝ち（山がなくなって打つ手が無くなった方が負け）
+-------------------------------------------------------------------------------------------
+定理【ゲームの状態遷移はmex】
+  - {*n1, ..., *nk} ≡ *mex(n1,...,nk)
+      where mex(S) = min(nat \setminus S)
 
-    *n をサイズ n の山が1個だけの nim とする
-      - *0 は負け
-      - *n は勝ち n>=1
-
-    ゲーム
-      - 状態 G から打てる手で遷移する先を G1, ..., Gk とする
-        G = {G1, ..., Gk} と書く
+  - より一般的に G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
+    帰納的に、全てのゲームはなんらかの *n と等価
 
-    等価
-      - 二つのゲームG, Fが等価なことを G ≡ F と書く
-        等価というのは勝ち負け一致よりもっと強い。二つのゲームの和を取ると必敗になること
-        *n と *n は同サイズの山2つのnimは必敗なので等価。同サイズでなければ必勝なので等価でない
+  証明
+    - {*n1, ..., *nk} は *mex(n1,...,nk) と等価。
+      つまり和を取ると必敗。
+      *mex(n1,...,nk) 側を動かした場合、相手は対応する ni に遷移する。
+      {*ni} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。
+      {*ni} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。
+      で両側等価を保ててしまう。
+
 
-    定理
-      - G1≡*n1, ..., Gk≡*nk ならば、G={G1, ..., Gk} ≡ *mex(n1,...,nk)
-        where mex(S) = min(nat \setminus S)
-        帰納的に、全てのゲームはなんらかの *n と等価
-
-    定理の証明
-      - {G1, ..., Gk} は *mex(n1,...,nk) と等価。
-        つまり和を取ると必敗。
-        *mex(n1,...,nk) 側を動かした場合、相手は対応する Gi に遷移する。
-        {G} 側を mex(n1,...,nk) より小さいゲームに動かした場合、mex側を対応する値に変える。
-        {G} 側を mex より大きいゲームに動かした場合、その大きいゲームをmexに下げる。
-        で両側等価を保ててしまう。
-
-    等価(和を取ると必敗) => 勝ち負け一致 の証明
-      - 偶奇を考えれば良い。必勝ゲーム+必敗ゲーム なら初手で必勝を必敗に変えて常にその状態を
-        保てば勝てる。ゆえに一致しないなら和をとったゲームは必勝。
+-------------------------------------------------------------------------------------------
+まとめ
 
-
-おまけ
-  @G を G のnim値とする。つまりG≡*@G
-  G = X + Y ならば @G = @X xor @Y
-  山が複数のnimの勝敗は全部xorとった1つ山のnimに等しいのと同じ原理。
+・一手動かした次の局面が *n1 または *n2 または ... なゲーム
+　　{*n1, ..., *nk} = *mex(n1, ..., nk)
+・ゲーム *n1 と *n2 とどちらかを選んで一手進められるゲーム
+　　*n1 + *n2 = *(n1 xor n2)
+・ゲーム *n1 と *n2 とどちらか一方または両方一気に進められるゲーム
+　　*n1 <+> *n2 = *(n1 + n2)     //単に１個の山なのとかわらない
+・両方一手ずつ進めるゲーム？
+　　*n1 X *n2 = ?