結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
 kaichou243
|
| 提出日時 | 2023-03-24 16:55:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 288 ms / 2,000 ms |
| コード長 | 31,208 bytes |
| コンパイル時間 | 5,655 ms |
| コンパイル使用メモリ | 374,904 KB |
| 最終ジャッジ日時 | 2025-02-11 16:48:27 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
#include<bits/stdc++.h>#include <immintrin.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define FOR(i,n) for(int i = 0; i < (n); i++)#define sz(c) ((int)(c).size())#define ten(x) ((int)1e##x)#define all(v) (v).begin(), (v).end()using namespace std;using ll=long long;using P = pair<ll,ll>;const long double PI=acos(-1);const ll INF=1e18;const int inf=1e9;template<int MOD> struct Fp{ll val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}static constexpr int getmod() { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {ll a = r.val, b = MOD, u = 1, v = 0;while (b) {ll t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}constexpr bool operator < (const Fp& r) const noexcept {return this->val < r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {Fp<MOD> res=1,r=a;while(n){if(n&1) res*=r;r*=r;n>>=1;}return res;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}ll get(){return val;}explicit operator bool()const{return val;}};template< uint32_t mod, bool fast = false >struct MontgomeryModInt {using mint = MontgomeryModInt;using i32 = int32_t;using i64 = int64_t;using u32 = uint32_t;using u64 = uint64_t;static constexpr u32 get_r() {u32 ret = mod;for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;return ret;}static constexpr u32 r = get_r();static constexpr u32 n2 = -u64(mod) % mod;static_assert(r * mod == 1, "invalid, r * mod != 1");static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");u32 a;MontgomeryModInt() : a{} {}MontgomeryModInt(const i64 &x): a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}static constexpr u32 reduce(const u64 &b) {return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);}constexpr mint& operator+=(const mint &p) {if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;return *this;}constexpr mint& operator-=(const mint &p) {if(i32(a -= p.a) < 0) a += 2 * mod;return *this;}constexpr mint& operator*=(const mint &p) {a = reduce(u64(a) * p.a);return *this;}constexpr mint& operator/=(const mint &p) {*this *= modinv(p);return *this;}constexpr mint operator-() const { return mint() - *this; }constexpr mint operator+(const mint &p) const { return mint(*this) += p; }constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }u32 get() const {u32 ret = reduce(a);return ret >= mod ? ret - mod : ret;}friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {MontgomeryModInt<mod> ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {u64 a = r.get(), b = mod, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return MontgomeryModInt<mod>(u);}friend ostream &operator<<(ostream &os, const mint &p) {return os << p.get();}friend istream &operator>>(istream &is, mint &a) {i64 t;is >> t;a = mint(t);return is;}static constexpr u32 getmod() { return mod; }};ll mod(ll a,ll MOD){if(a<0) a+=MOD;return a%MOD;}ll modpow(ll a,ll n,ll mod){ll res=1;a%=mod;while (n>0){if (n & 1) res*=a;a *= a;a%=mod;n >>= 1;res%=mod;}return res;}vector<P> prime_factorize(ll N) {vector<P> res;for (ll a = 2; a * a <= N; ++a) {if (N % a != 0) continue;ll ex = 0;while(N % a == 0){++ex;N /= a;}res.push_back({a, ex});}if (N != 1) res.push_back({N, 1});return res;}ll modinv(ll a, ll mod) {ll b = mod, u = 1, v = 0;while (b) {ll t = a/b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}ll extGcd(ll a, ll b, ll &p, ll &q) {if (b == 0) { p = 1; q = 0; return a; }ll d = extGcd(b, a%b, q, p);q -= a/b * p;return d;}P ChineseRem(const vector<ll> &b, const vector<ll> &m) {ll r = 0, M = 1;for (int i = 0; i < (int)b.size(); ++i) {ll p, q;ll d = extGcd(M, m[i], p, q);if ((b[i] - r) % d != 0) return make_pair(0, -1);ll tmp = (b[i] - r) / d * p % (m[i]/d);r += M * tmp;M *= m[i]/d;}return make_pair(mod(r, M), M);}//fast Input by yosupo#include <unistd.h>#include <algorithm>#include <array>#include <cassert>#include <cctype>#include <cstring>#include <sstream>#include <string>#include <type_traits>#include <vector>namespace fastio{/*quote from yosupo's submission in Library Checker*/int bsr(unsigned int n) {return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);}// @param n `1 <= n`// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsr(unsigned long n) {return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);}// @param n `1 <= n`// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsr(unsigned long long n) {return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);}// @param n `1 <= n`// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsr(unsigned __int128 n) {unsigned long long low = (unsigned long long)(n);unsigned long long high = (unsigned long long)(n >> 64);return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low);}namespace internal {template <class T>using is_signed_int128 =typename std::conditional<std::is_same<T, __int128_t>::value ||std::is_same<T, __int128>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::value ||std::is_same<T, unsigned __int128>::value,std::true_type,std::false_type>::type;template <class T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value,__uint128_t,unsigned __int128>;template <class T>using is_integral =typename std::conditional<std::is_integral<T>::value ||internal::is_signed_int128<T>::value ||internal::is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_signed_int = typename std::conditional<(is_integral<T>::value &&std::is_signed<T>::value) ||is_signed_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<(is_integral<T>::value &&std::is_unsigned<T>::value) ||is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value,std::make_unsigned<T>,std::common_type<T>>::type>::type;template <class T>using is_integral_t = std::enable_if_t<is_integral<T>::value>;template <class T>using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;template <class T>using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;template <class T> using to_unsigned_t = typename to_unsigned<T>::type;} // namespace internalstruct Scanner {public:Scanner(const Scanner&) = delete;Scanner& operator=(const Scanner&) = delete;Scanner(FILE* fp) : fd(fileno(fp)) {}void read() {}template <class H, class... T> void read(H& h, T&... t) {bool f = read_single(h);assert(f);read(t...);}int read_unsafe() { return 0; }template <class H, class... T> int read_unsafe(H& h, T&... t) {bool f = read_single(h);if (!f) return 0;return 1 + read_unsafe(t...);}int close() { return ::close(fd); }private:static constexpr int SIZE = 1 << 15;int fd = -1;std::array<char, SIZE + 1> line;int st = 0, ed = 0;bool eof = false;bool read_single(std::string& ref) {if (!skip_space()) return false;ref = "";while (true) {char c = top();if (c <= ' ') break;ref += c;st++;}return true;}bool read_single(double& ref) {std::string s;if (!read_single(s)) return false;ref = std::stod(s);return true;}template <class T,std::enable_if_t<std::is_same<T, char>::value>* = nullptr>bool read_single(T& ref) {if (!skip_space<50>()) return false;ref = top();st++;return true;}template <class T,internal::is_signed_int_t<T>* = nullptr,std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>bool read_single(T& sref) {using U = internal::to_unsigned_t<T>;if (!skip_space<50>()) return false;bool neg = false;if (line[st] == '-') {neg = true;st++;}U ref = 0;do {ref = 10 * ref + (line[st++] & 0x0f);} while (line[st] >= '0');sref = neg ? -ref : ref;return true;}template <class U,internal::is_unsigned_int_t<U>* = nullptr,std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>bool read_single(U& ref) {if (!skip_space<50>()) return false;ref = 0;do {ref = 10 * ref + (line[st++] & 0x0f);} while (line[st] >= '0');return true;}bool reread() {if (ed - st >= 50) return true;if (st > SIZE / 2) {std::memmove(line.data(), line.data() + st, ed - st);ed -= st;st = 0;}if (eof) return false;auto u = ::read(fd, line.data() + ed, SIZE - ed);if (u == 0) {eof = true;line[ed] = '\0';u = 1;}ed += int(u);line[ed] = char(127);return true;}char top() {if (st == ed) {bool f = reread();assert(f);}return line[st];}template <int TOKEN_LEN = 0>bool skip_space() {while (true) {while (line[st] <= ' ') st++;if (ed - st > TOKEN_LEN) return true;if (st > ed) st = ed;for (auto i = st; i < ed; i++) {if (line[i] <= ' ') return true;}if (!reread()) return false;}}};//fast Output by ei1333/*** @brief Printer(高速出力)*/struct Printer {public:explicit Printer(FILE *fp) : fp(fp) {}~Printer() { flush(); }template< bool f = false, typename T, typename... E >void write(const T &t, const E &... e) {if(f) write_single(' ');write_single(t);write< true >(e...);}template< typename... T >void writeln(const T &...t) {write(t...);write_single('\n');}void flush() {fwrite(line, 1, st - line, fp);st = line;}private:FILE *fp = nullptr;static constexpr size_t line_size = 1 << 16;static constexpr size_t int_digits = 20;char line[line_size + 1] = {};char small[32] = {};char *st = line;template< bool f = false >void write() {}void write_single(const char &t) {if(st + 1 >= line + line_size) flush();*st++ = t;}template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >void write_single(T s) {if(st + int_digits >= line + line_size) flush();if(s == 0) {write_single('0');return;}if(s < 0) {write_single('-');s = -s;}char *mp = small + sizeof(small);typename make_unsigned< T >::type y = s;size_t len = 0;while(y > 0) {*--mp = y % 10 + '0';y /= 10;++len;}memmove(st, mp, len);st += len;}void write_single(const string &s) {for(auto &c : s) write_single(c);}void write_single(const char *s) {while(*s != 0) write_single(*s++);}template< typename T >void write_single(const vector< T > &s) {for(size_t i = 0; i < s.size(); i++) {if(i) write_single(' ');write_single(s[i]);}}};}; //namespace fastiousing mint=MontgomeryModInt<998244353>;int main(){fastio::Scanner sc(stdin);fastio::Printer pr(stdout);#define in(...) sc.read(__VA_ARGS__)#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)#define out(...) pr.write(__VA_ARGS__)#define outln(...) pr.writeln(__VA_ARGS__)#define outspace(...) pr.write(__VA_ARGS__),pr.write(' ')#define rall(v) (v).rbegin(), (v).rend()#define fi first#define se second/*ここでは左上を(0,0)として考える以下のパターン①上下、左右 2^H+2^W②x+yが偶数に上下x+yが奇数に左右、その逆、同じ行、列には左右、上下はない。2*2^H*2^W③上左、右下はx+y mod gでそれぞれ決まる、2*2^g④上右、左下はx-y mod g 2*2^g1,3,4はいかなるgについても存在する2はgが偶数の時のみ(奇数の時はx+y≡2 mod gとx+y≡0 mod 2が同値でない)1,3,4で重複が8(4方向*2)1,2,3,4で重複が16(1,3,4の8+2*(2の縦横それぞれ1方向のケース(=4)))これ以外のケースを考える1,2,3,4を満たしていない数え上げたい対象は4*4グリッドの周期になる(証明は解説に任せる(え？))当然、ここまでくればグリッドを全探索すれば良い(このグリッドには2ヶ所同じ方向があって、探索するのは4^8通り)全体のグリッドがトーラスであることを考えると、ちゃんと4*4のグリッドでピッタリ敷き詰められる必要がありgが4の倍数の時しかこのケースは存在しないこのケースのうち1,2,3,4と被らないものは48通り存在する。(全探索)K>0の時すでに書き込まれた数によって固定されるものを考えれば良い、実装はとてつもなく大変コメント:割り当てる方向の個数が3つ以上の数え上げは、②を計算することにより残るものが定数個になるというの、とても難しかった、めっちゃadhocどうやって作問したんですか？*/auto calc=[](map<int,char> &mp){map<char,int> d;for(auto& [key,val]:mp) d[val]++;int ret=0;for(auto& [c,cnt]:d) if(cnt>0) ret++;return ret;};vector<char> gd={'L','R','U','D'};vector<vector<vector<char>>> solution;//渾身の8重ループfor(int i=0;i<4;i++){for(int j=0;j<4;j++){for(int k=0;k<4;k++){for(int l=0;l<4;l++){for(int m=0;m<4;m++){for(int n=0;n<4;n++){for(int o=0;o<4;o++){for(int p=0;p<4;p++){vector<vector<char>> candidate={{gd[i],gd[j],gd[m],gd[n]},{gd[k],gd[l],gd[o],gd[p]},{gd[m],gd[n],gd[i],gd[j]},{gd[o],gd[p],gd[k],gd[l]}};bool ok=true;map<char,int> dc,odd,even;FOR(I,4){map<char,int> dci,dcj;FOR(J,4){dc[candidate[I][J]]++;dci[candidate[I][J]]++;dcj[candidate[J][I]]++;if((I+J)%2==0){even[candidate[I][J]]++;}else{odd[candidate[I][J]]++;}if(candidate[I][J]=='L'){if(dci['R']>0) ok=false;}else if(candidate[I][J]=='R'){if(dci['L']>0) ok=false;}if(candidate[J][I]=='U'){if(dcj['D']>0) ok=false;}else if(candidate[J][I]=='D'){if(dcj['U']>0) ok=false;}}}if(dc.size()<3||!ok) continue;bool hasver_odd=false,hashor_odd=false,hasver_even=false,hashor_even=false;for(auto& [key,val]:odd){if(key=='L'||key=='R') hashor_odd=true;else hasver_odd=true;}for(auto& [key,val]:even){if(key=='L'||key=='R') hashor_even=true;else hasver_even=true;}if((hasver_odd&&hashor_odd)||(hasver_even&&hashor_even)){vector<vector<char>> b=candidate;FOR(T,16){vector<vector<char>> nb(4,vector<char>(4,'.'));FOR(I,4){FOR(J,4){if(b[I][J]=='L'){if(nb[I][(J+3)%4]!='.'){ok=false;break;}nb[I][(J+3)%4]=b[I][J];}else if(b[I][J]=='R'){if(nb[I][(J+1)%4]!='.'){ok=false;break;}nb[I][(J+1)%4]=b[I][J];}else if(b[I][J]=='U'){if(nb[(I+3)%4][J]!='.'){ok=false;break;}nb[(I+3)%4][J]=b[I][J];}else{if(nb[(I+1)%4][J]!='.'){ok=false;break;}nb[(I+1)%4][J]=b[I][J];}}}if(!ok) break;b=nb;}if(ok) solution.push_back(candidate);}}}}}}}}}INT(t);assert(1<=t&&t<=100);while(t--){LL(h,w,k);assert(1<=h&&h<=1000000000&&1<=w&&w<=1000000000&&0<=k&&k<=min(2000ll,h*w));ll g=gcd(h,w);mint ans=0;if(k==0){if(g%4==0){ans=modpow(mint(2),h)+modpow(mint(2),w)+modpow(mint(2),h+w+1)+modpow(mint(2),g)*4+32;}else if(g%4==2){ans=modpow(mint(2),h)+modpow(mint(2),w)+modpow(mint(2),h+w+1)+modpow(mint(2),g)*4-16;}else{ans=modpow(mint(2),h)+modpow(mint(2),w)+modpow(mint(2),g)*4-8;}outln(ans.get());continue;}swap(h,w);vector<ll> x(k),y(k);vector<char> d(k);bool hasver=false,hashor=false;FOR(i,k){in(y[i],x[i],d[i]);//y[i]=w-y[i]-1;x[i]=h-x[i]-1;assert(0<=x[i]&&x[i]<h&&0<=y[i]&&y[i]<w);assert(d[i]=='R'||d[i]=='L'||d[i]=='U'||d[i]=='D');if(d[i]=='L'||d[i]=='R') hashor=true;else hasver=true;}//case 1if(!hasver||!hashor){map<int,vector<char>> X,Y;FOR(i,k){X[x[i]].push_back(d[i]);Y[y[i]].push_back(d[i]);}bool ret0h=false,ret0w=false;ll h1=h,w1=w;for(auto& [key,val]:X){sort(all(val));val.erase(unique(all(val)),val.end());if(val.size()>1) ret0h=true;for(auto& element:val){if(element!='L'&&element!='R') ret0h=true;}if(ret0h) break;h1--;}for(auto& [key,val]:Y){sort(all(val));val.erase(unique(all(val)),val.end());if(val.size()>1) ret0w=true;for(auto& element:val){if(element!='U'&&element!='D') ret0w=true;}if(ret0w) break;w1--;}if(!ret0h) ans+=modpow(mint(2),h1);if(!ret0w) ans+=modpow(mint(2),w1);}//case 2if(g%2==0){bool oddver=false,oddhor=false,evenver=false,evenhor=false;FOR(i,k){if((x[i]+y[i])%2){if(d[i]=='L'||d[i]=='R') oddhor=true;else oddver=true;}else{if(d[i]=='L'||d[i]=='R') evenhor=true;else evenver=true;}}if(!(oddver&&oddhor)&&!(evenver&&evenhor)&&!(oddver&&evenver)&&!(oddhor&&evenhor)){if(evenver||oddhor){bool ret0=false;map<int,char> X,Y;FOR(i,k){if((x[i]+y[i])%2){if(X.find(x[i])==X.end()){X[x[i]]=d[i];}else if(X[x[i]]!=d[i]){ret0=true;}}else{if(Y.find(y[i])==Y.end()){Y[y[i]]=d[i];}else if(Y[y[i]]!=d[i]){ret0=true;}}}if(!ret0){ans+=modpow(mint(2),h+w-X.size()-Y.size())-(2-calc(X))*(2-calc(Y));}}if(evenhor||oddver){bool ret0=false;map<int,char> X,Y;FOR(i,k){if((x[i]+y[i])%2==0){if(X.find(x[i])==X.end()){X[x[i]]=d[i];}else if(X[x[i]]!=d[i]){ret0=true;}}else{if(Y.find(y[i])==Y.end()){Y[y[i]]=d[i];}else if(Y[y[i]]!=d[i]){ret0=true;}}}if(!ret0){ans+=modpow(mint(2),h+w-X.size()-Y.size())-(2-calc(X))*(2-calc(Y));}}}}//case 3{bool ret0=false;map<int,char> mp;map<char,int> dc;FOR(i,k){if(mp.find((x[i]+y[i])%g)==mp.end()){mp[(x[i]+y[i])%g]=d[i];}else if(mp[(x[i]+y[i])%g]!=d[i]){ret0=true;}dc[d[i]]++;}if(dc.size()>2) ret0=true;int dsiz=dc.size();if((dc['L']>0||dc['U']>0)&&dc['R']==0&&dc['D']==0&&!ret0){ans+=modpow(mint(2),g-mp.size())-2+dsiz;}else if((dc['R']>0||dc['D']>0)&&dc['L']==0&&dc['U']==0&&!ret0){ans+=modpow(mint(2),g-mp.size())-2+dsiz;}}//case 4{bool ret0=false;map<int,char> mp;map<char,int> dc;FOR(i,k){if(mp.find((x[i]+(g-1)*y[i])%g)==mp.end()){mp[(x[i]+(g-1)*y[i])%g]=d[i];}else if(mp[(x[i]+(g-1)*y[i])%g]!=d[i]){ret0=true;}dc[d[i]]++;}if(dc.size()>2) ret0=true;int dsiz=dc.size();if((dc['L']>0||dc['D']>0)&&dc['R']==0&&dc['U']==0&&!ret0){ans+=modpow(mint(2),g-mp.size())-2+dsiz;}else if((dc['R']>0||dc['U']>0)&&dc['L']==0&&dc['D']==0&&!ret0){ans+=modpow(mint(2),g-mp.size())-2+dsiz;}}//case muzuiif(g%4==0){vector<vector<char>> grid(4,vector<char>(4,'.'));bool ret0=false;FOR(i,k){if(grid[x[i]%4][y[i]%4]=='.'){grid[x[i]%4][y[i]%4]=d[i];}else if(grid[x[i]%4][y[i]%4]!=d[i]){ret0=true;}}FOR(i,4) FOR(j,2){if(grid[i][j]!='.'&&grid[(i+2)%4][(j+2)%4]!='.'){if(grid[i][j]!=grid[(i+2)%4][(j+2)%4]) ret0=true;}else if(grid[i][j]!='.'){grid[(i+2)%4][(j+2)%4]=grid[i][j];}else if(grid[(i+2)%4][(j+2)%4]!='.'){grid[i][j]=grid[(i+2)%4][(j+2)%4];}}if(!ret0){//すでに1,2,3,4との被りを省いた48通りのうちマッチするものを探し出す//このコードを書いてる人は今書いてる時点ですでに疲れており、48通りのグリッドを書き出したくない//書き出すグリッドの個数は6個に絞ることができる(トーラス上で8通りのずらす方法がそれぞれある)FOR(i,48){auto& s=solution[i];bool ok=true;FOR(x,4) FOR(y,4){if(grid[x][y]=='.'||grid[x][y]==s[x][y]) continue;ok=false;}if(ok) ans+=1;}}}outln(ans.get());}}