// BEGIN CUT HERE
#include "stdafx.h"
// END CUT HERE
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
using namespace std;
typedef long long ll;
static const double EPS = 1e-9;
int ROUND(double x) { return (int)(x+0.5); }
bool ISINT(double x) { return fabs(ROUND(x)-x)<EPS; }
bool ISEQUAL(double x,double y) { return fabs(x-y)<EPS; }
#define PI (3.14159265358979323846)
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
double SQSUM(double x,double y) { return x*x+y*y; }
#define SZ(a) ((int)a.size())
class DonutsOnTheGrid {
public:
long long calc(int H, int W, int seed, int threshold) {
long long result = 0;
vector <string> field;
int a = seed;
for(int y=0;y<H;y++)
{
string tmp;
for(int x=0;x<W;x++)
{
a = (a * 25173 + 13849) % 65536;
if(a>=threshold)
{
tmp += ".";
}
else
{
tmp += "O";
}
}
field.push_back(tmp);
}
vector <vector <int> > tate_len(H, vector<int>(W,0));
for(int y=0;y<H;y++)
{
for(int x=0;x<W;x++)
{
if(field[y][x]=='O')
{
if(y>=1)
{
tate_len[y][x] = tate_len[y-1][x] + 1;
}
else
{
tate_len[y][x] = 1;
}
}
}
}
for(int y1=0;y1<H-2;y1++)
{
for(int y2=y1+2;y2<H;y2++)
{
int cnt = -1;
bool horyu = false;
for(int x=0;x<W;x++)
{
if(field[y1][x]=='.'||field[y2][x]=='.')
{
cnt = -1;
horyu = false;
}
else if(y2-y1+1<=tate_len[y2][x])
{
if(horyu)
{
cnt++;
horyu = false;
}
if(x>=1 && y2-y1+1<=tate_len[y2][x-1])
{
horyu = true;
}
else
{
cnt++;
}
result += cnt;
}
}
}
}
#if 0 // 残念な回答
vector <vector <int> > tate_len(H, vector<int>(W,0));
vector <vector <int> > yoko_len(H, vector<int>(W,0));
for(int y=0;y<H;y++)
{
for(int x=0;x<W;x++)
{
if(field[y][x]=='O')
{
if(y>=1)
{
tate_len[y][x] = tate_len[y-1][x] + 1;
}
else
{
tate_len[y][x] = 1;
}
if(x>=1)
{
yoko_len[y][x] = yoko_len[y][x-1] + 1;
}
else
{
yoko_len[y][x] = 1;
}
}
}
}
// 長方形の数。右下の頂点の位置でかぞえる
vector <vector <ll> > num_rect(H, vector<ll>(W,0));
for(int y=0;y<H;y++)
{
for(int x=0;x<W;x++)
{
// 下の辺と右の辺の長さがどちらも3以上
if(yoko_len[y][x]>=3 && tate_len[y][x]>=3)
{
if(yoko_len[y-tate_len[y][x]+1][x]>=3 &&
tate_len[y][x-yoko_len[y][x]+1]>=3)
{
num_rect[y][x] = 1;
result += num_rect[y][x];
}
}
}
}
#endif
return result;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { int Arg0 = 5; int Arg1 = 5; int Arg2 = 222; int Arg3 = 55555; long long Arg4 = 4LL; verify_case(0, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); }
void test_case_1() { int Arg0 = 5; int Arg1 = 6; int Arg2 = 121; int Arg3 = 58000; long long Arg4 = 3LL; verify_case(1, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); }
void test_case_2() { int Arg0 = 4; int Arg1 = 5; int Arg2 = 6; int Arg3 = 50000; long long Arg4 = 1LL; verify_case(2, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); }
void test_case_3() { int Arg0 = 4; int Arg1 = 4; int Arg2 = 1; int Arg3 = 65536; long long Arg4 = 9LL; verify_case(3, Arg4, calc(Arg0, Arg1, Arg2, Arg3)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main() {
DonutsOnTheGrid* ___test = new DonutsOnTheGrid();
___test->run_test(-1);
delete ___test;
}
// END CUT HERE