#962546 (C++17) No.2683 Two Sheets

提出ソース
結果

問題	No.2683 Two Sheets
ユーザー	👑 Nachia
提出日時	2024-03-20 21:53:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	13,868 bytes
コンパイル時間	1,321 ms
コンパイル使用メモリ	106,652 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-09-30 07:40:49
合計ジャッジ時間	1,806 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <array>
#include <cmath>
#include <atcoder/modint>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(i64 i=0; i<(i64)(n); i++)
#define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--)
const i64 INF = 1001001001001001001;
const char* yn(bool x){ return x ? "Yes" : "No"; }
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;
using Modint = atcoder::static_modint<998244353>;
//#include "nachia/vec.hpp"
using namespace std;

using Int = __int128_t;

// tool assist : https://sigma.yosupo.jp/
// f(H,A)=$(y=0..H)$(a=0..H-A)$(b=0..H-A)[a<=y][y<=a+A-1][b<=y][y<=b+A-1]1
// g(H,A)=$(y=0..H)$(a=0..H-A)[a<=y][y<=a+A-1]1


Int f(Int H, Int A) {
Int sum = Int(0);
if (-1*A+H >= 0) {
  if (H+-1*A >= 0) {
    if (Int(-1)+A >= 0) {
      if (A+Int(-1) >= 0) {
        if (H >= 0) {
          sum += (Int(1));
        }
      }
    }
    if (H >= 0) {
      if (H >= 0) {
        if (H >= 0) {
          if (-1*H+Int(-1)+A >= 0) {
            if (-1*H+Int(-1)+A >= 0) {
              sum += (1*H);
            }
          }
        }
      }
    }
    if (Int(-1)+A >= 0) {
      if (A+Int(-1) >= 0) {
        if (A+Int(-1) >= 0) {
          if (H+-1*A >= 0) {
            sum += (1*A+Int(-1));
          }
        }
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (H+-1*A >= 0) {
    if (Int(-1)+H >= 0) {
      if (Int(-1)+A >= 0) {
        if (H >= 0) {
          if (-1*A >= 0) {
            sum += (1*A);
          }
        }
      }
    }
    if (Int(-1)+-1*A+H >= 0) {
      if (Int(-1)+H >= 0) {
        if (H+Int(-1) >= 0) {
          if (A+Int(-1)+-1*H >= 0) {
            sum += ((1*H+2*H*A+-1*H*H+-2*A) / 2);
          }
        }
      }
    }
  }
}
if (-1*A+H >= 0) {
  if (H+-1*A >= 0) {
    if (H+Int(-1) >= 0) {
      if (A+Int(-1) >= 0) {
        if (H >= 0) {
          if (A+-1*H >= 0) {
            sum += (-1*A+1*H);
          }
        }
      }
    }
    if (A+Int(-1) >= 0) {
      if (-1*H+2*A+Int(-1) >= 0) {
        if (A >= 0) {
          if (-1*A+Int(-1)+H >= 0) {
            if (H+-1*A+Int(-1) >= 0) {
              sum += (2*H*A+-1*A*A+-1*A+-1*H*H+1*H);
            }
          }
        }
      }
    }
    if (Int(-1)+-1*H+2*A >= 0) {
      if (Int(-1)+A >= 0) {
        if (Int(-1)+A >= 0) {
          if (H+-1*A >= 0) {
            if (-1*A+H >= 0) {
              sum += (1*H*A+-1*H+1*A+-1*A*A);
            }
          }
        }
      }
    }
    if (A+Int(-1) >= 0) {
      if (H+Int(-1) >= 0) {
        if (H+Int(-1) >= 0) {
          if (A+-1*H+Int(-1) >= 0) {
            sum += (-1*H+1*A+1*H*H+-1*H*A);
          }
        }
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (H+-1*A >= 0) {
    if (H >= 0) {
      if (H >= 0) {
        if (H >= 0) {
          if (Int(-1)+-1*A >= 0) {
            if (Int(-1)+A+-1*H >= 0) {
              sum += ((1*H+1*H*H) / 2);
            }
          }
        }
      }
    }
    if (Int(-1)+A >= 0) {
      if (Int(-1)+A >= 0) {
        if (Int(-1)+A >= 0) {
          if (-2*A+H >= 0) {
            if (-1*A+H >= 0) {
              sum += ((-1*A+1*A*A) / 2);
            }
          }
        }
      }
    }
    if (-1*A+Int(-1)+H >= 0) {
      if (Int(-1)+-1*A+H >= 0) {
        if (-1*A+Int(-1)+H >= 0) {
          if (Int(-1)+2*A+-1*H >= 0) {
            if (A >= 0) {
              sum += ((-1*H+1*A*A+1*A+-2*H*A+1*H*H) / 2);
            }
          }
        }
      }
    }
  }
}
if (-1*A+H >= 0) {
  if (Int(-1)+A >= 0) {
    if (Int(-1)+A >= 0) {
      if (Int(-1)+H >= 0) {
        if (H >= 0) {
          if (-1*A >= 0) {
            sum += (1*A);
          }
        }
      }
    }
    if (H+Int(-1) >= 0) {
      if (Int(-1)+-1*A+H >= 0) {
        if (Int(-1)+H >= 0) {
          if (-1*H+A >= 0) {
            sum += ((-2*A+-1*H*H+2*H*A+1*H) / 2);
          }
        }
      }
    }
  }
}
if (Int(-1)+A >= 0) {
  if (Int(-1)+A >= 0) {
    if (H+Int(-1) >= 0) {
      if (H+Int(-1) >= 0) {
        if (H >= 0) {
          if (-1*A >= 0) {
            if (-1*A >= 0) {
              sum += (1*A*A);
            }
          }
        }
      }
    }
    if (H+-1*A+Int(-1) >= 0) {
      if (Int(-1)+-1*A+H >= 0) {
        if (-1*A+H >= 0) {
          if (Int(-1)+A >= 0) {
            sum += ((3*A*A+-2*A*A*A+-1*A) / 6);
          }
        }
      }
    }
    if (H+Int(-1)+-1*A >= 0) {
      if (H+-1*A+Int(-1) >= 0) {
        if (Int(-1)+H >= 0) {
          sum += ((-6*H*H*A+6*H*A*A+-6*A*A+1*H+6*H*A+-3*H*H+2*H*H*H) / 6);
        }
      }
    }
  }
}
if (-1*A+H >= 0) {
  if (Int(-1)+A >= 0) {
    if (H+Int(-1) >= 0) {
      if (Int(-1)+H >= 0) {
        if (H >= 0) {
          if (A+-1*H >= 0) {
            if (-1*A >= 0) {
              sum += (1*H*A+-1*A*A);
            }
          }
        }
      }
    }
    if (H+-1*A+Int(-1) >= 0) {
      if (Int(-1)+H+-1*A >= 0) {
        if (H+-1*A >= 0) {
          if (-1*H+2*A >= 0) {
            if (Int(-1)+A >= 0) {
              sum += ((1*H*A+1*A*A*A+-1*H*A*A+-1*A*A) / 2);
            }
          }
        }
      }
    }
    if (A+Int(-1) >= 0) {
      if (A+Int(-1) >= 0) {
        if (A >= 0) {
          if (-2*A+Int(-1)+H >= 0) {
            if (Int(-1)+H+-1*A >= 0) {
              sum += ((4*H*A+-3*A*A*A+-1*H*H+1*H*H*H+-5*H*H*A+-3*A*A+7*H*A*A) / 2);
            }
          }
        }
      }
    }
    if (Int(-1)+A >= 0) {
      if (H+-1*A+Int(-1) >= 0) {
        if (H+Int(-1) >= 0) {
          sum += ((-1*H*H*H+-3*H*A+1*H*H+3*H*H*A+-2*H*A*A+2*A*A) / 2);
        }
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (Int(-1)+A >= 0) {
    if (H+-2*A+Int(-1) >= 0) {
      if (-1*A+Int(-1)+H >= 0) {
        if (H+-1*A >= 0) {
          if (A >= 0) {
            if (Int(-1)+A >= 0) {
              sum += ((-1*A*A*A+1*A) / 6);
            }
          }
        }
      }
    }
    if (H+Int(-1) >= 0) {
      if (-1*A+Int(-1)+H >= 0) {
        if (H+Int(-1) >= 0) {
          if (-1*A >= 0) {
            sum += ((3*H*H*A+-2*H*H*H+-3*H*A+3*H*H+-1*H) / 6);
          }
        }
      }
    }
    if (H+-1*A+Int(-1) >= 0) {
      if (Int(-1)+H+-2*A >= 0) {
        if (-1*A+H+Int(-1) >= 0) {
          if (A+Int(-1) >= 0) {
            if (A >= 0) {
              sum += ((6*A*A+-2*H*H*H+1*A+-12*H*A*A+3*H*H+9*H*H*A+-1*H+5*A*A*A+-9*H*A) / 6);
            }
          }
        }
      }
    }
  }
}
if (H+-1*A >= 0) {
  if (-1*A+H >= 0) {
    if (A+Int(-1) >= 0) {
      if (H+Int(-1) >= 0) {
        if (H >= 0) {
          if (A+-1*H >= 0) {
            sum += (1*H+-1*A);
          }
        }
      }
    }
    if (Int(-1)+2*A+-1*H >= 0) {
      if (Int(-1)+A >= 0) {
        if (A >= 0) {
          if (-1*A+H >= 0) {
            if (-1*A+H+Int(-1) >= 0) {
              sum += (2*H*A+-1*A*A+-1*A+-1*H*H+1*H);
            }
          }
        }
      }
    }
    if (Int(-1)+H >= 0) {
      if (Int(-1)+A >= 0) {
        if (Int(-1)+H >= 0) {
          if (A+-1*H >= 0) {
            sum += (-1*H+-1*H*A+1*A+1*H*H);
          }
        }
      }
    }
    if (A+Int(-1) >= 0) {
      if (-1*H+Int(-1)+2*A >= 0) {
        if (Int(-1)+A >= 0) {
          if (Int(-1)+H+-1*A >= 0) {
            if (-1*A+H >= 0) {
              sum += (1*A+-1*H+1*H*A+-1*A*A);
            }
          }
        }
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (-1*A+H >= 0) {
    if (Int(-1)+H >= 0) {
      if (Int(-1)+H >= 0) {
        if (H >= 0) {
          if (-1*A >= 0) {
            if (A+-1*H >= 0) {
              sum += (1*H*A+-1*A*A);
            }
          }
        }
      }
    }
    if (A+Int(-1) >= 0) {
      if (Int(-1)+A >= 0) {
        if (A >= 0) {
          if (H+-2*A >= 0) {
            if (-1*A+Int(-1)+H >= 0) {
              sum += ((-3*A*A*A+-5*H*H*A+-1*H*H+4*H*A+7*H*A*A+1*H*H*H+-3*A*A) / 2);
            }
          }
        }
      }
    }
    if (H+-1*A+Int(-1) >= 0) {
      if (H+Int(-1)+-1*A >= 0) {
        if (H+-1*A >= 0) {
          if (Int(-1)+2*A+-1*H >= 0) {
            if (Int(-1)+A >= 0) {
              sum += ((1*A*A*A+-1*A*A+1*H*A+-1*H*A*A) / 2);
            }
          }
        }
      }
    }
    if (-1*A+Int(-1)+H >= 0) {
      if (A+Int(-1) >= 0) {
        if (Int(-1)+H >= 0) {
          sum += ((2*A*A+-1*H*H*H+3*H*H*A+-3*H*A+-2*H*A*A+1*H*H) / 2);
        }
      }
    }
  }
}
if (-1*A+H >= 0) {
  if (-1*A+H >= 0) {
    if (Int(-1)+H >= 0) {
      if (Int(-1)+H >= 0) {
        if (H >= 0) {
          if (A+-1*H >= 0) {
            if (-1*H+A >= 0) {
              sum += (1*H*H+1*A*A+-2*H*A);
            }
          }
        }
      }
    }
    if (Int(-1)+A >= 0) {
      if (A+Int(-1) >= 0) {
        if (A >= 0) {
          if (-1*A+Int(-1)+H >= 0) {
            sum += (1*A*A*A+-1*H*H*H+1*A*A+3*H*H*A+1*H*H+-3*H*A*A+-2*H*A);
          }
        }
      }
    }
    if (Int(-1)+A >= 0) {
      if (Int(-1)+A >= 0) {
        if (Int(-1)+H >= 0) {
          sum += (-1*H*H+-1*A*A+-2*H*H*A+1*H*A*A+2*H*A+1*H*H*H);
        }
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (-1*A+H >= 0) {
    if (H+Int(-1) >= 0) {
      if (A+Int(-1) >= 0) {
        if (H+Int(-1) >= 0) {
          if (-1*A >= 0) {
            sum += ((-1*H*H+1*H*H*H+1*H*A+-1*H*H*A) / 2);
          }
        }
      }
    }
  }
}
if (-1*A+H >= 0) {
  if (Int(-1)+A >= 0) {
    if (H >= 0) {
      if (H >= 0) {
        if (H >= 0) {
          if (Int(-1)+-1*H+A >= 0) {
            if (Int(-1)+-1*A >= 0) {
              sum += ((1*H*H+1*H) / 2);
            }
          }
        }
      }
    }
    if (H+-1*A+Int(-1) >= 0) {
      if (-1*A+H+Int(-1) >= 0) {
        if (-1*A+H+Int(-1) >= 0) {
          if (-1*H+2*A >= 0) {
            if (A >= 0) {
              sum += ((-1*H+1*A+1*A*A+1*H*H+-2*H*A) / 2);
            }
          }
        }
      }
    }
    if (Int(-1)+A >= 0) {
      if (A+Int(-1) >= 0) {
        if (Int(-1)+A >= 0) {
          if (-2*A+H+Int(-1) >= 0) {
            if (H+-1*A >= 0) {
              sum += ((-1*A+1*A*A) / 2);
            }
          }
        }
      }
    }
  }
}
if (Int(-1)+A >= 0) {
  if (Int(-1)+A >= 0) {
    if (Int(-1)+H+-1*A >= 0) {
      if (-2*A+H+Int(-1) >= 0) {
        if (-1*A+H >= 0) {
          if (A+Int(-1) >= 0) {
            if (A+Int(-1) >= 0) {
              sum += ((1*A+-1*A*A*A) / 6);
            }
          }
        }
      }
    }
    if (H+Int(-1)+-2*A >= 0) {
      if (-1*A+Int(-1)+H >= 0) {
        if (Int(-1)+-1*A+H >= 0) {
          if (A >= 0) {
            if (A >= 0) {
              sum += ((3*H*H+-1*H+-2*H*H*H+-9*H*A+6*A*A+-12*H*A*A+9*H*H*A+1*A+5*A*A*A) / 6);
            }
          }
        }
      }
    }
    if (Int(-1)+H+-1*A >= 0) {
      if (Int(-1)+H >= 0) {
        if (Int(-1)+H >= 0) {
          if (-1*A+Int(-1) >= 0) {
            sum += ((-2*H*H*H+-1*H+-3*H*A+3*H*H+3*H*H*A) / 6);
          }
        }
      }
    }
  }
}
if (H+-1*A >= 0) {
  if (Int(-1)+A >= 0) {
    if (A+Int(-1) >= 0) {
      if (H+Int(-1) >= 0) {
        if (Int(-1)+H >= 0) {
          if (Int(-1)+-1*A >= 0) {
            sum += ((1*H*H*H+-1*H*H+-1*H*H*A+1*H*A) / 2);
          }
        }
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (Int(-1)+A >= 0) {
    if (H >= 0) {
      if (H >= 0) {
        if (H >= 0) {
          if (Int(-1)+-1*A >= 0) {
            if (-1*A+Int(-1) >= 0) {
              sum += ((3*H*H+1*H+2*H*H*H) / 6);
            }
          }
        }
      }
    }
    if (-1*A+Int(-1)+H >= 0) {
      if (H+Int(-1)+-1*A >= 0) {
        if (Int(-1)+H+-1*A >= 0) {
          if (A >= 0) {
            sum += ((6*H*A*A+-2*A*A*A+-3*A*A+6*H*A+-1*A+-6*H*H*A+-3*H*H+2*H*H*H+1*H) / 6);
          }
        }
      }
    }
  }
}
return sum;

}

Int g(Int H, Int A) {
Int sum = Int(0);
if (-1*A+H >= 0) {
  if (A+Int(-1) >= 0) {
    if (H >= 0) {
      sum += (Int(1));
    }
  }
  if (H >= 0) {
    if (H >= 0) {
      if (Int(-1)+A+-1*H >= 0) {
        sum += (1*H);
      }
    }
  }
  if (A+Int(-1) >= 0) {
    if (Int(-1)+A >= 0) {
      if (H+-1*A >= 0) {
        sum += (Int(-1)+1*A);
      }
    }
  }
}
if (A+Int(-1) >= 0) {
  if (Int(-1)+H >= 0) {
    if (H >= 0) {
      if (-1*A >= 0) {
        sum += (1*A);
      }
    }
  }
  if (H+Int(-1)+-1*A >= 0) {
    if (-1*A+H >= 0) {
      if (A+Int(-1) >= 0) {
        sum += ((-1*A*A+1*A) / 2);
      }
    }
  }
  if (-1*A+Int(-1)+H >= 0) {
    if (Int(-1)+H >= 0) {
      sum += ((2*H*A+-2*A+1*H+-1*H*H) / 2);
    }
  }
}
if (H+-1*A >= 0) {
  if (H+Int(-1) >= 0) {
    if (H >= 0) {
      if (A+-1*H >= 0) {
        sum += (-1*A+1*H);
      }
    }
  }
  if (A+Int(-1) >= 0) {
    if (A >= 0) {
      if (Int(-1)+H+-1*A >= 0) {
        sum += (-1*A*A+-1*H*H+2*H*A+1*H+-1*A);
      }
    }
  }
  if (A+Int(-1) >= 0) {
    if (H+Int(-1) >= 0) {
      sum += (1*A+-1*H*A+1*H*H+-1*H);
    }
  }
}
if (A+Int(-1) >= 0) {
  if (H >= 0) {
    if (H >= 0) {
      if (-1*A+Int(-1) >= 0) {
        sum += ((1*H+1*H*H) / 2);
      }
    }
  }
  if (-1*A+Int(-1)+H >= 0) {
    if (H+Int(-1)+-1*A >= 0) {
      if (A >= 0) {
        sum += ((1*A*A+-2*H*A+1*A+-1*H+1*H*H) / 2);
      }
    }
  }
}
return sum;

}

void testcase(){
    i64 H, W, A, B; cin >> H >> W >> A >> B;
    auto c1 = Modint(i64(g(H,A) % 998244353)) * Modint(i64(g(W,B) % 998244353));
    auto c2 = Modint(i64(f(H,A) % 998244353)) * Modint(i64(f(W,B) % 998244353));
    Modint q = Modint(H-A+1) * Modint(W-B+1); q = q.inv();
    Modint ans = c1 * q * 2 - c2 * q * q;
    cout << ans.val() << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef NACHIA
    int T; cin >> T; for(int t=0; t<T; T!=++t?(cout<<'\n'),0:0)
    #endif
    testcase();
    return 0;
}
yukicoder

結果

テストケース

ソースコード
