結果
| 問題 |
No.2884 Pieces on Squares
|
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2024-09-08 14:30:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 13,842 bytes |
| コンパイル時間 | 3,213 ms |
| コンパイル使用メモリ | 232,044 KB |
| 最終ジャッジ日時 | 2025-02-24 05:40:49 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 -- * 3 |
| other | AC * 7 MLE * 3 -- * 35 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
//入力が必ずmod未満の時に使う.
struct mint{
long long v = 0;
mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;}
long long val(){return v;}
void modu(){v %= mod;}
mint repeat2mint(const long long a,long long b){
mint ret = 1,p = a;
while(b){
if(b&1) ret *= p;
p *= p; b >>= 1;
}
return ret;
};
mint operator+(const mint b){return mint(v)+=b;}
mint operator-(const mint b){return mint(v)-=b;}
mint operator*(const mint b){return mint(v)*=b;}
mint operator/(const mint b){return mint(v)/=b;}
mint operator+=(const mint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
mint operator-=(const mint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
mint operator*=(const mint b){v = v*b.v%mod; return *this;}
mint operator/=(mint b){
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
mint operator++(int){*this += 1; return *this;}
mint operator--(int){*this -= 1; return *this;}
bool operator==(const mint b){return v == b.v;}
bool operator!=(const mint b){return v != b.v;}
bool operator>(const mint b){return v > b.v;}
bool operator>=(const mint b){return v >= b.v;}
bool operator<(const mint b){return v < b.v;}
bool operator<=(const mint b){return v <= b.v;}
mint pow(const long long x){return repeat2mint(v,x);}
mint inv(){return mint(1)/v;}
};
namespace to_fold{ //纏めて折り畳むためのやつ 苦労したが結局ほぼACLの写経.
__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}
pair<long long,long long> invgcd(long long a,long long b){
//return {gcd(a,b),x} (xa≡g(mod b))
a = safemod(a,b);
if(a == 0) return {b,0};
long long x = 0,y = 1,memob = b;
while(a){
long long q = b/a;
b -= a*q;
swap(x,y); y -= q*x;
swap(a,b);
}
if(x < 0) x += memob/b;
return {b,x};
}
long long Garner(vector<long long> &A,vector<long long> &M){
__int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.
for(int i=1; i<A.size(); i++){
//assert(gcd(mulM,M.at(i-1)) == 1);
mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_t
long long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));
x += t*mulM;
}
return x%mod;
}
int countzero(unsigned long long x){
if(x == 0) return 64;
else return __popcount((x&-x)-1);
}
struct fftinfo{
vector<mint> root,iroot,rate2,irate2,rate3,irate3;
fftinfo(mint g){
int rank2 = countzero(mod-1);
root.resize(rank2+1),iroot = root;
rate2.resize(max(0,rank2-2+1)); irate2 = rate2;
rate3.resize(max(0,rank2-3+1)); irate3 = rate3;
root[rank2] = g.pow((mod-1)>>rank2);
iroot[rank2] = root[rank2].inv();
for(int i=rank2-1; i>=0; i--){
root[i] = root[i+1]*root[i+1];
iroot[i] = iroot[i+1]*iroot[i+1];
}
mint mul = 1,imul = 1;
for(int i=0; i<=rank2-2; i++){
rate2[i] = root[i+2]*mul;
irate2[i] = iroot[i+2]*imul;
mul *= iroot[i+2],imul *= root[i+2];
}
mul = 1,imul = 1;
for(int i=0; i<=rank2-3; i++){
rate3[i] = root[i+3]*mul;
irate3[i] = iroot[i+3]*imul;
mul *= iroot[i+3],imul *= root[i+3];
}
}
};
mint findroot(){
if(mod == 998244353) return mint(3);
else if(mod == 754974721) return mint(11);
else if(mod == 167772161) return mint(3);
else if(mod == 469762049) return mint(3);
long long p = mod-1;
vector<long long> P;
for(long long i=2; i*i<=p; i++){
if(p%i) continue;
while(p%i == 0) p /= i;
P.push_back(i);
}
if(p != 1) P.push_back(p);
p = mod-1;
random_device rnd; mt19937 mt(rnd());
while(true){
mint ret = mt()%mod;
if(ret == 1 || ret == 0) continue;
if(ret.pow(p) != 1) continue;
bool ok = true;
for(auto check : P) if(ret.pow(p/check) == 1){ok = false; break;}
if(ok) return ret;
} //O(√P)らしいです.
}
void NTT(vector<mint> &A,fftinfo &info){
int N = A.size(),ln = countzero(N);
int dep = 0;
while(dep < ln){
if(ln-dep == 1){
int p = 1<<(ln-dep-1);
mint rot = 1;
for(int o=0; o<(1<<dep); o++){
int offset = o<<(ln-dep);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
A.at(i+offset) = l+r; A.at(i+offset+p) = l-r;
}
if(o+1 != (1<<dep)) rot *= info.rate2[countzero(~(unsigned int)o)];
}
dep++;
}
else{
int p = 1<<(ln-dep-2);
mint rot = 1,imag = info.root[2];
for(int o=0; o<(1<<dep); o++){
mint rot2 = rot*rot,rot3 = rot2*rot;
int offset = o<<(ln-dep);
for(int i=0; i<p; i++){
auto mod2 = 1ULL*mod*mod;
auto a0 = 1ULL*A.at(i+offset).v;
auto a1 = 1ULL*A.at(i+offset+p).v*rot.v;
auto a2 = 1ULL*A.at(i+offset+p+p).v*rot2.v;
auto a3 = 1ULL*A.at(i+offset+p+p+p).v*rot3.v;
auto a1m2a3im = 1ULL*(a1+mod2-a3+mod)%mod*imag.v;
auto m2a2 = mod2-a2;
A.at(i+offset) = (long long)((a0+a2+a1+a3)%mod);
A.at(i+offset+p) = (long long)((a0+a2+(2*mod2-(a1+a3)))%mod);
A.at(i+offset+p+p) = (long long)((a0+m2a2+a1m2a3im)%mod);
A.at(i+offset+p+p+p) = (long long)((a0+m2a2+(mod2-a1m2a3im))%mod);
}
if(o+1 != (1<<dep)) rot *= info.rate3[countzero(~(unsigned int)o)];
}
dep += 2;
}
}
}
void INTT(vector<mint> &A,fftinfo &info){
int N = A.size(),ln = countzero(N);
int dep = ln;
while(dep){
if(dep == 1){
int p = 1<<(ln-dep);
mint irot = 1;
for(int o=0; o<(1<<(dep-1)); o++){
int offset = o<<(ln-dep+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p);
A.at(i+offset) = l+r;
A.at(i+offset+p) = (long long)((unsigned long long)((mod+l.v-r.v)*irot.v)%mod);
}
if(o+1 != (1<<(dep-1))) irot *= info.irate2[countzero(~(unsigned int)o)];
}
dep--;
}
else{
int p = 1<<(ln-dep);
mint irot = 1,iimag = info.iroot[2];
for(int o=0; o<(1<<(dep-2)); o++){
mint irot2 = irot*irot,irot3 = irot2*irot;
int offset = o<<(ln-dep+2);
for(int i=0; i<p; i++){
auto a0 = 1ULL*A.at(i+offset).v,a1 = 1ULL*A.at(i+offset+p).v;
auto a2 = 1ULL*A.at(i+offset+p+p).v,a3 = 1ULL*A.at(i+offset+p+p+p).v;
auto gotyagotya = 1ULL*((mod+a2-a3)*iimag.v%mod);
A.at(i+offset) = (long long)((a0+a1+a2+a3)%mod);
A.at(i+offset+p) = (long long)((a0+(mod-a1)+gotyagotya)*irot.v%mod);
A.at(i+offset+p+p) = (long long)((a0+a1+(mod-a2)+(mod-a3))*irot2.v%mod);
A.at(i+offset+p+p+p) = (long long)((a0+(mod-a1)+(mod-gotyagotya))*irot3.v%mod);
}
if(o+1 != (1<<(dep-2))) irot *= info.irate3[countzero(~(unsigned int)o)];
}
dep -= 2;
}
}
}
vector<mint> convolutionnaive(vector<mint> &A,vector<mint> &B){
vector<mint> ret(A.size()+B.size()-1);
for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
return ret;
}
vector<mint> convolution(vector<mint> &A,vector<mint> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
if(siza == 0 || sizb == 0) return {};
while(N <= sizc) N <<= 1;
vector<mint> ca = A,cb = B;
ca.resize(N),cb.resize(N);
if(min(siza,sizb) <= 40) return convolutionnaive(A,B);
assert((mod-1)%N == 0);
mint root = findroot();
fftinfo info(root);
NTT(ca,info); NTT(cb,info);
for(int i=0; i<N; i++) ca.at(i) *= cb.at(i);
INTT(ca,info); ca.resize(sizc);
mint divN = mint(N).inv();
for(int i=0; i<sizc; i++) ca.at(i) *= divN;
return ca;
}
vector<long long> convolution_ll(vector<long long> &A,vector<long long> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;
unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;
assert(sizc <= (1<<24));
mod = mod1;
vector<mint> a(siza),b(sizb);
for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;
vector<mint> C1 = convolution(a,b);
mod = mod2;
for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;
vector<mint> C2 = convolution(a,b);
mod = mod3;
for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;
vector<mint> C3 = convolution(a,b);
vector<long long> ret(sizc);
vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};
for(int i=0; i<sizc; i++){
unsigned long long x = 0;
x += (C1.at(i).v*i1)%mod1*m2m3;
x += (C2.at(i).v*i2)%mod2*m3m1;
x += (C3.at(i).v*i3)%mod3*m1m2;
long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;
if(diff < 0) diff += mod1;
x -= offset.at(diff%5);
ret.at(i) = x;
}
return ret;
}
vector<mint> convolution_llmod(vector<mint> &A,vector<mint> &B,long long memomod){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
assert(sizc <= (1<<24));
mod = mod1;
vector<mint> a(siza),b(sizb);
for(int i=0; i<siza; i++) a.at(i) = A.at(i).v%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i).v%mod;
vector<mint> C1 = convolution(a,b);
mod = mod2;
for(int i=0; i<siza; i++) a.at(i) = A.at(i).v%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i).v%mod;
vector<mint> C2 = convolution(a,b);
mod = mod3;
for(int i=0; i<siza; i++) a.at(i) = A.at(i).v%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i).v%mod;
vector<mint> C3 = convolution(a,b);
mod = memomod;
vector<mint> ret(sizc);
for(int i=0; i<sizc; i++){
vector<long long> A = {C1.at(i).v,C2.at(i).v,C3.at(i).v};
vector<long long> M = {mod1,mod2,mod3};
ret.at(i) = Garner(A,M);
}
return ret;
}
}
using namespace to_fold;
class UnionFind{
public:
vector<int> par,siz;
void make(int N){
par.resize(N,-1);
siz.resize(N,1);
}
int root(int x){
if(par.at(x) == -1) return x;
else return par.at(x) = root(par.at(x));
}
void unite(int u, int v){
u = root(u),v = root(v);
if(u == v) return;
if(siz.at(u) < siz.at(v)) swap(u,v);
par.at(v) = u;
siz.at(u) += siz.at(v);
}
bool issame(int u, int v){
if(root(u) == root(v)) return true;
else return false;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int H,W,N; cin >> H >> W >> N;
UnionFind uf; uf.make(H+W);
while(N--){
int a,b; cin >> a >> b;
a--; b--; b += H;
uf.unite(a,b);
}
int X = 0,Y = 0;
vector<pair<int,int>> need(H+W);
for(int i=0; i<H+W; i++){
if(i < H) need.at(uf.root(i)).first++;
else need.at(uf.root(i)).second++;
}
int left = 0;
vector<vector<vector<mint>>> Q((H+1)*(W+1)+1);
for(auto &[x,y] : need) if(x || y){
if(x == 1 && y == 0) X++;
else if(x == 0 && y == 1) Y++;
else{
left++;
vector<mint> now;
while(now.size() < x*(W+1)+y+1) now.push_back(0);
now.at(0) = 1,now.back() = 1;
Q.at(now.size()).push_back(now);
}
}
int pos = 0,pos2 = 0;
while(left > 1){
while(Q.at(pos).size() <= pos2) pos++,pos2 = 0;
auto &A = Q.at(pos).at(pos2++);
while(Q.at(pos).size() <= pos2) pos++,pos2 = 0;
auto &B = Q.at(pos).at(pos2++);
auto C = convolution(A,B);
for(auto &c : C) if(c != 0) c = 1;
A.clear(),B.clear();
Q.at(C.size()).push_back(C); left--;
}
while(Q.back().size() == 0) Q.pop_back();
auto &A = Q.back().back();
while(A.size() < (H+1)*(W+1)) A.push_back(0);
int answer = 0;
for(int i=0; i<=H; i++) for(int k=0; k<=W; k++){
int pos = i*(W+1)+k;
if(A.at(pos) == 0) continue;
answer = max(answer,i*W+k*H-2*i*k);
int nowy = Y;
for(int x=0; x<=X&&i+x<=H; x++){
if(nowy == -1) break;
for(int y=0; y<=Y&&k+y<=W; y++){
if((x || y) && A.at(pos+y) == 1){nowy = y-1; break;}
answer = max(answer,(i+x)*W+(k+y)*H-2*(i+x)*(k+y));
}
pos += W+1;
}
}
cout << answer << endl;
}