Submission #792884

#	Time	Username	Problem	Language	Result	Execution time	Memory
792884		ymm	Chess Rush (CEOI20_chessrush)	C++17	28 / 100	2084 ms	8652 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) {
	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;
}

void calc_king(int n)
{
	static karr b;
	if (n <= 32) {
		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] = (b[i][0] + b[i][1]) % mod;
				Loop (j,1,m-1)
					king_table[i][j] = (b[i][j-1] + b[i][j] + b[i][j+1]) % mod;
				king_table[i][m-1] = (b[i][m-2] + b[i][m-1]) % mod;
			}
		}
		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] = (b[i][0] + b[i][1]) % mod;
			Loop (j,1,m-1)
				king_table[i][j] = (b[i][j-1] + b[i][j] + b[i][j+1]) % mod;
			king_table[i][m-1] = (b[i][m-2] + b[i][m-1]) % mod;
		}
	} 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]};
}
pii queen(int i, int j)
{
	// TODO
	return {0, 0};
}
pii bishop(int i, int j)
{
	// TODO
	return {0, 0};
}

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