結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
 noya2
|
| 提出日時 | 2023-02-24 00:28:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,196 bytes |
| コンパイル時間 | 2,902 ms |
| コンパイル使用メモリ | 233,988 KB |
| 最終ジャッジ日時 | 2025-02-10 20:10:13 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 WA * 11 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/modint>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
using namespace std;
using P = pair<int,int>;
using mint = atcoder::modint998244353;
void solve(){
int h, w, k; cin >> h >> w >> k;
int g = __gcd(h,w);
if (k == 0){
mint ans = mint(2).pow(h) + mint(2).pow(w) + mint(2).pow(g+2);
if (g % 2 == 1){
ans -= 8;
}
else {
ans += mint(2).pow(h+w+1);
if (g % 4 == 0){
ans += 32;
}
else {
ans -= 16;
}
}
cout << ans.val() << endl;
return ;
}
vector<int> xs(k), ys(k), ds(k);
rep(i,k){
cin >> xs[i] >> ys[i];
char c; cin >> c;
ds[i] = (c == 'U' ? 0 : c == 'L' ? 1 : c == 'D' ? 2 : 3);
}
auto Case1 = [&](){
vector<int> dcnt(4,0);
rep(i,k) dcnt[ds[i]]++;
int ver = dcnt[0] + dcnt[2], hor = dcnt[1] + dcnt[3];
if (ver > 0 && hor > 0) return mint(0);
if (ver > 0){
map<int,int> mx;
rep(i,k){
if (mx.find(xs[i]) == mx.end()){
mx[xs[i]] = ds[i];
}
else if (mx[xs[i]] != ds[i]){
return mint(0);
}
}
int siz = mx.size();
return mint(2).pow(h-siz);
}
if (hor > 0){
map<int,int> my;
rep(i,k){
if (my.find(ys[i]) == my.end()){
my[ys[i]] = ds[i];
}
else if (my[ys[i]] != ds[i]){
return mint(0);
}
}
int siz = my.size();
return mint(2).pow(w-siz);
}
return mint(0);
};
auto Case2 = [&](){
if (g % 2 == 1) return mint(0);
vector<int> dcnt0(4,0), dcnt1(4,0);
rep(i,k){
((xs[i]+ys[i])%2 == 0 ? dcnt0 : dcnt1)[ds[i]]++;
}
int ver0 = dcnt0[0] + dcnt0[2], hor0 = dcnt0[1] + dcnt0[3];
int ver1 = dcnt1[0] + dcnt1[2], hor1 = dcnt1[1] + dcnt1[3];
if (ver0 > 0 && hor0 > 0) return mint(0);
if (ver1 > 0 && hor1 > 0) return mint(0);
if (ver0 > 0 && ver1 > 0) return mint(0);
if (hor0 > 0 && hor1 > 0) return mint(0);
if (ver0 > 0){
map<int,int> mx, my;
rep(i,k){
if ((xs[i]+ys[i]) % 2 == 0){
if (mx.find(xs[i]) == mx.end()){
mx[xs[i]] = ds[i];
}
else if (mx[xs[i]] != ds[i]){
return mint(0);
}
}
else {
if (my.find(ys[i]) == my.end()){
my[ys[i]] = ds[i];
}
else if (my[ys[i]] != ds[i]){
return mint(0);
}
}
}
int sizx = mx.size(), sizy = my.size();
return mint(2).pow(h-sizx+w-sizy);
}
if (hor0 > 0){
map<int,int> mx, my;
rep(i,k){
if ((xs[i]+ys[i]) % 2 == 1){
if (mx.find(xs[i]) == mx.end()){
mx[xs[i]] = ds[i];
}
else if (mx[xs[i]] != ds[i]){
return mint(0);
}
}
else {
if (my.find(ys[i]) == my.end()){
my[ys[i]] = ds[i];
}
else if (my[ys[i]] != ds[i]){
return mint(0);
}
}
}
int sizx = mx.size(), sizy = my.size();
return mint(2).pow(h-sizx+w-sizy);
}
return mint(0);
};
mint ans = Case1() + Case2();
bool modgok = true;
map<P,int> mgok;
rep(i,k){
xs[i] %= g, ys[i] %= g;
if (mgok.find(P(xs[i],ys[i])) == mgok.end()){
mgok[P(xs[i],ys[i])] = ds[i];
}
else if (mgok[P(xs[i],ys[i])] != ds[i]){
modgok = false;
}
}
if (!modgok){
cout << ans.val() << endl;
return ;
}
auto mod = [&](int xy){
return (xy%g+g)%g;
};
auto Case3 = [&](){
vector<int> dcnt(4,0);
rep(i,k) dcnt[ds[i]]++;
int nonzero = 0, id1 = -1, id2 = -1;
rep(i,4){
if (dcnt[i] > 0){
nonzero++;
if (id1 == -1) id1 = i;
else if (id2 == -1) id2 = i;
}
}
if (nonzero >= 3) return mint(0);
if (id2 != -1){
if ((id1 % 2) == (id2 % 2)){
return mint(0);
}
}
if (id1 % 2 == 0){
map<int,int> xmy;
rep(i,k){
int ixmy = mod(xs[i]-ys[i]);
if (xmy.find(ixmy) == xmy.end()){
xmy[ixmy] = ds[i];
}
else if (xmy[ixmy] != ds[i]){
return mint(0);
}
}
int siz = xmy.size();
return mint(2).pow(g-siz) - 2 + nonzero;
}
else {
map<int,int> xpy;
rep(i,k){
int ixpy = mod(xs[i]+ys[i]);
if (xpy.find(ixpy) == xpy.end()){
xpy[ixpy] = ds[i];
}
else if (xpy[ixpy] != ds[i]){
return mint(0);
}
}
int siz = xpy.size();
return mint(2).pow(g-siz) - 2 + nonzero;
}
return mint(0);
};
auto Case4 = [&](){
vector<int> dcnt(4,0);
rep(i,k) dcnt[ds[i]]++;
int nonzero = 0, id1 = -1, id2 = -1;
rep(i,4){
if (dcnt[i] > 0){
nonzero++;
if (id1 == -1) id1 = i;
else if (id2 == -1) id2 = i;
}
}
if (nonzero >= 3) return mint(0);
if (id2 != -1){
if ((id1 % 2) == (id2 % 2)){
return mint(0);
}
}
if (id1 % 2 == 1){
map<int,int> xmy;
rep(i,k){
int ixmy = mod(xs[i]-ys[i]);
if (xmy.find(ixmy) == xmy.end()){
xmy[ixmy] = ds[i];
}
else if (xmy[ixmy] != ds[i]){
return mint(0);
}
}
int siz = xmy.size();
return mint(2).pow(g-siz) - 2 + nonzero;
}
else {
map<int,int> xpy;
rep(i,k){
int ixpy = mod(xs[i]+ys[i]);
if (xpy.find(ixpy) == xpy.end()){
xpy[ixpy] = ds[i];
}
else if (xpy[ixpy] != ds[i]){
return mint(0);
}
}
int siz = xpy.size();
return mint(2).pow(g-siz) - 2 + nonzero;
}
return mint(0);
};
ans += Case3() + Case4();
if (g % 4 != 0){
cout << ans.val() << endl;
return ;
}
auto Case5 = [&](){
vector<vector<int>> m4(4,vector<int>(4,-1));
rep(i,k){
xs[i] %= 4, ys[i] %= 4;
if (m4[xs[i]][ys[i]] == -1){
m4[xs[i]][ys[i]] = ds[i];
}
else if (m4[xs[i]][ys[i]] != ds[i]){
return mint(0);
}
}
vector<vector<int>> tmp1 =
{
{0, 3, 1, 3},
{1, 3, 1, 2},
{1, 3, 0, 3},
{1, 2, 1, 3}
};
vector<vector<int>> tmp2 =
{
{1, 0, 1, 3},
{1, 3, 2, 3},
{1, 3, 1, 0},
{2, 3, 1, 3}
};
vector<vector<int>> tmp3 =
{
{0, 0, 0, 3},
{1, 2, 2, 2},
{0, 3, 0, 0},
{2, 2, 1, 2}
};
vector<vector<int>> tmp4 =
{
{1, 0, 0, 0},
{2, 2, 2, 3},
{0, 0, 1, 0},
{2, 3, 2, 2}
};
vector<vector<int>> tmp5 =
{
{0, 0, 1, 3},
{1, 3, 2, 2},
{1, 3, 0, 0},
{2, 2, 1, 3}
};
vector<vector<int>> tmp6 =
{
{1, 0, 0, 3},
{1, 2, 2, 3},
{0, 3, 1, 0},
{2, 3, 1, 2}
};
vector<vector<vector<int>>> tmp = {tmp1,tmp2,tmp3,tmp4,tmp5,tmp6};
auto match = [&](vector<vector<int>> &test, int ex, int ey){
rep(x,4) rep(y,4){
if (m4[x][y] == -1 || m4[x][y] == test[(x+ex)%4][(y+ey)%4]){
continue;
}
return false;
}
return true;
};
mint res = 0;
rep(i,6) rep(ex,4) rep(ey,2) if (match(tmp[i],ex,ey)) res++;
return res;
};
ans += Case5();
cout << ans.val() << endl;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int t = 1; cin >> t;
while(t--) solve();
}