Submission #792954

#	Time	Username	Problem	Language	Result	Execution time	Memory
792954		ymm	Chess Rush (CEOI20_chessrush)	C++17	28 / 100	2085 ms	8552 KiB

chessrush

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int mod = 1e9+7;
const int N = 1024;
ll fct[N], fcti[N];
int n, m;

ll pw(ll x,ll y){ll a=1;while(y){if(y&1)a=a*x%mod;x=x*x%mod;y/=2;}return a;}
ll C(int n, int r) {
	if (r == 0)
		return 1;
	if (r < 0 || n < r)
		return 0;
	ll ans = 1;
	Loop (i,n-r+1,n+1)
		ans = ans*i % mod;
	ans = ans * fcti[r]%mod;
	return ans;
}
void init() {
	fct[0] = fcti[0] = 1;
	Loop (i,1,N) {
		fct[i] = fct[i-1]*i % mod;
		fcti[i] = pw(fct[i], mod-2);
	}
}

typedef unsigned karr[N][N];
karr king_table;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
unsigned mul(unsigned *a, unsigned *b)
{
	//ll ans = 0;
	//Loop (i,0,N)
	//	ans = (ans + (ll)a[i] * b[i]) % mod;
	//return ans;
	typedef unsigned long long ull;
	ull ans[4] = {};
	for (int i = 0; i < N; i += 64) {
		for (int j = 0; j < 64; j += 4) {
			for (int k = 0; k < 4; ++k)
				ans[k] += (ull)a[i+j+k] * b[i+j+k];
		}
		Loop (k,0,4)
			ans[k] %= mod;
	}
	return (ans[0] + ans[1] + ans[2] + ans[3]) % mod;
}

#define MOD(x) ((x) >= mod? (x)-mod: (x))

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void calc_king(int n)
{
	static karr b;
	if (n <= 128) {
		Loop (i,0,m) Loop (j,0,m)
			king_table[i][j] = i == j;
		while (n--) {
			memcpy(b, king_table, sizeof(king_table));
			Loop (i,0,m) {
				king_table[i][0] = MOD(b[i][0] + b[i][1]);
				Loop (j,1,m-1)
					king_table[i][j] = MOD(MOD(b[i][j-1] + b[i][j]) + b[i][j+1]);
				king_table[i][m-1] = MOD(b[i][m-2] + b[i][m-1]);
			}
		}
		return;
	}
	calc_king(n/2);
	Loop (i,0,m) Loop (j,0,m) {
		if (i > j || i+j >= m)
			continue;
		b[i][j] = mul(king_table[i], king_table[j]);
	}
	Loop (i,0,m) Loop (j,0,m) {
		if (i <= j || i+j >= m)
			continue;
		b[i][j] = b[j][i];
	}
	Loop (i,0,m) Loop (j,0,m) {
		if (i+j < m)
			continue;
		b[i][j] = b[m-1-i][m-1-j];
	}
	if (n%2 == 1) {
		Loop (i,0,m) {
			king_table[i][0] = MOD(b[i][0] + b[i][1]);
			Loop (j,1,m-1)
				king_table[i][j] = MOD(MOD(b[i][j-1] + b[i][j]) + b[i][j+1]);
			king_table[i][m-1] = MOD(b[i][m-2] + b[i][m-1]);
		}
	} else {
		memcpy(king_table, b, sizeof(king_table));
	}
}

pii pawn(int i, int j)
{
	return i == j? pii{n-1, 1}: pii{0, 0};
}
pii rook(int i, int j)
{
	return i == j? pii{1, 1}: pii{2, 2};
}
pii king(int i, int j)
{
	return {n-1, king_table[i][j]};
}
ll Ct(int n, int r, int x) { 
	ll ans = 0;
	Loop (i,0,x)
		ans += C(n+r-2-i, r-i);
	ans %= mod;
	return ans;

}
pii bishop_left(int i, int j)
{
	ll pos = 0;
	int f = i;
	pos += f;
	ll x = (n-2-pos) / (m-1);
	pos += x * (m-1);
	if (x%2 == 0) {
		ll pos2 = n-1-pos;
		if (j >= pos2)
			return {x+2, Ct(x+1, (j-pos2)/2, f)};
		else
			return {x+3, Ct(x+2, (pos2-j)/2, f)};
	} else {
		ll pos2 = m-1-(n-1-pos);
		if (j <= pos2)
			return {x+2, Ct(x+1, (pos2-j)/2, f)};
		else
			return {x+3, Ct(x+2, (j-pos2)/2, f)};
	}
}
pii bishop_right(int i, int j)
{
	ll pos = 0;
	int f = m-1-i;
	pos += f;
	ll x = (n-2-pos) / (m-1);
	pos += x * (m-1);
	if (x%2 == 1) {
		ll pos2 = n-1-pos;
		if (j >= pos2)
			return {x+2, Ct(x+1, (j-pos2)/2, f)};
		else
			return {x+3, Ct(x+2, (pos2-j)/2, f)};
	} else {
		ll pos2 = m-1-(n-1-pos);
		if (j <= pos2)
			return {x+2, Ct(x+1, (pos2-j)/2, f)};
		else
			return {x+3, Ct(x+2, (j-pos2)/2, f)};
	}
}
pii bishop(int i, int j)
{
	if ((i+j+n)%2 == 0)
		return {0, 0};
	if (i == 0)
		return bishop_right(i, j);
	if (i == m-1)
		return bishop_left(i, j);
	auto [x1, y1] = bishop_left(i, j);
	auto [x2, y2] = bishop_right(i, j);
	//cerr << x1 << ' ' << y1 << "!!\n";
	//cerr << x2 << ' ' << y2 << "!!\n";
	if (x1 < x2)
		return {x1, y1};
	if (x1 > x2)
		return {x2, y2};
	return {x1, (y1 + y2) % mod};
}
pii queen(int i, int j)
{
	if (i == j || (n == m && ((i == 0 && j == m-1) || (i == m-1 && j == 0))))
		return {1, 1};
	int ans = 4;
	auto [x, y] = bishop(i, j);
	if (x == 2)
		ans += y;
	if (n == m && (j == m-1 || j == 0))
		++ans;
	return {2, ans};
}

map<char, pii (*)(int, int)> fn = {
	{'P', pawn},
	{'R', rook},
	{'K', king},
	{'Q', queen},
	{'B', bishop},
};

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> n >> m >> q;
	init();
	calc_king(n-1);
	while (q--) {
		char c;
		int i, j;
		cin >> c >> i >> j;
		--i; --j;
		auto [x, y] = fn[c](i, j);
		cout << x << ' ' << y << '\n';
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7