ADDED   SRM/513-U/1A.cpp
Index: SRM/513-U/1A.cpp
==================================================================
--- SRM/513-U/1A.cpp
+++ SRM/513-U/1A.cpp
@@ -0,0 +1,145 @@
+#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>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+static const int MODVAL = 1000000009;
+
+class YetAnotherIncredibleMachine { public:
+	int countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls) 
+	{
+		LL total = 1;
+		for(int p=0; p<platformLength.size(); ++p)
+		{
+			vector< pair<int,int> > q;
+			int len = platformLength[p];
+			int pos = platformMount[p];
+			q.push_back( make_pair(pos-len, pos) );
+			for(int i=0; i<balls.size(); ++i)
+				avoid( balls[i], q, len );
+
+			int cnt = 0;
+			for(int i=0; i<q.size(); ++i)
+				cnt += q[i].second - q[i].first + 1;
+			total = total * cnt % MODVAL;
+		}
+		return int(total);
+	}
+
+	void avoid(int x, vector< pair<int,int> >& q, int len)
+	{
+		vector< pair<int,int> > q2;
+		for(int i=0; i<q.size(); ++i)
+			if( q[i].second+len < x || x < q[i].first )
+				q2.push_back( q[i] );
+			else {
+				int L = q[i].first;
+				int R = q[i].second;
+				if( L<=x-len-1 )
+					q2.push_back( make_pair(L, x-len-1) );
+				if( x+1<=R )
+					q2.push_back( make_pair(x+1, R) );
+			}
+		q.swap(q2);
+	}
+};
+
+// 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(_, YetAnotherIncredibleMachine().countWays(platformMount, platformLength, balls));}
+int main(){
+
+CASE(0)
+	int platformMount_[] = {7};
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = {10};
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = {3,4};
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = 3; 
+END
+CASE(1)
+	int platformMount_[] = {1,4};
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = {3,3};
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = {2,7};
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = 1; 
+END
+CASE(2)
+	int platformMount_[] = {4,4,4};
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = {10,9,8};
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = {1,100};
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = 27; 
+END
+CASE(3)
+	int platformMount_[] = {0};
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = {1};
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = {0};
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = 0; 
+END
+CASE(4)
+	int platformMount_[] = {100, -4215, 251};
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = {400, 10000, 2121};
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = {5000, 2270, 8512, 6122};
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = 250379170; 
+END
+/*
+CASE(5)
+	int platformMount_[] = ;
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = ;
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = ;
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = ; 
+END
+CASE(6)
+	int platformMount_[] = ;
+	  vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_)); 
+	int platformLength_[] = ;
+	  vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_)); 
+	int balls_[] = ;
+	  vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/513-U/1B.cpp
Index: SRM/513-U/1B.cpp
==================================================================
--- SRM/513-U/1B.cpp
+++ SRM/513-U/1B.cpp
@@ -0,0 +1,122 @@
+#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>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+template<typename T>
+struct DP2
+{
+	const int N1, N2;
+	vector<T> data;
+	DP2(int N1, int N2, const T& t = T())
+		: N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
+	T& operator()(int i1, int i2)
+		{ return data[ (i1*N2)+i2 ]; }
+	void swap(DP2& rhs)
+		{ data.swap(rhs.data); }
+};
+
+class PerfectMemory { public:
+	double getExpectation(int N, int M) 
+	{
+		const int C = N*M;
+		DP2<double> dp(C+1, C+1);
+		for(int u=0; u<=C; ++u)
+			for(int k=0; k<=C; ++k) if( (u+k)%2==0 && k+u<=C )
+			{
+				if( k > u )
+				{
+					dp(k,u) = 1 + dp(k-2,u);
+				}
+				else if( k == u )
+				{
+					if( k==0 && u==0 )
+						dp(k,u) = 0;
+					else
+						dp(k,u) = 1 + dp(k-1, u-1);
+				}
+				else // k < u
+				{
+					dp(k,u) = 1;
+
+					double pFirstIsKnown = double(k) / u;
+					double pSecondIsIt = double(1) / (u-1);
+					if(k)
+						dp(k,u) += pFirstIsKnown * dp(k-1, u-1);
+					double pSecondIsThat = double(k) / (u-1);
+					dp(k,u) += (1-pFirstIsKnown) * pSecondIsIt * dp(k, u-2);
+					dp(k,u) += (1-pFirstIsKnown) * (1-pSecondIsIt-pSecondIsThat) * dp(k+2, u-2);
+					dp(k,u) += (1-pFirstIsKnown) * pSecondIsThat * (1 + dp(k, u-2));
+				}
+//				cerr << k << " " << u << " " << dp(k,u) << endl;
+			}
+		return dp(0,C);
+	}
+};
+
+// 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 double& Expected, const double& Received) {
+ bool ok = (abs(Expected - Received) < 1e-9);
+ 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(_, PerfectMemory().getExpectation(N, M));}
+int main(){
+
+CASE(0)
+	int N = 1; 
+	int M = 2; 
+	double _ = 1.0; 
+END
+CASE(1)
+	int N = 2; 
+	int M = 2; 
+	double _ = 2.6666666666666665; 
+END
+CASE(2)
+	int N = 2; 
+	int M = 3; 
+	double _ = 4.333333333333334; 
+END
+CASE(3)
+	int N = 4; 
+	int M = 4; 
+	double _ = 12.392984792984793; 
+END
+/*
+CASE(4)
+	int N = 50; 
+	int M = 50; 
+	double _ = -1; 
+END
+CASE(5)
+	int N = 2; 
+	int M = 1; 
+	double _ = 1.0; 
+END
+*/
+}
+// END CUT HERE