結果
問題 | No.2668 Trees on Graph Paper |
ユーザー | みここ |
提出日時 | 2024-03-08 22:57:14 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 754 ms / 3,000 ms |
コード長 | 3,296 bytes |
コンパイル時間 | 830 ms |
コンパイル使用メモリ | 70,164 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 20:26:52 |
合計ジャッジ時間 | 9,064 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream>using namespace std;struct DynamicModint{using mint = DynamicModint;public:int val;DynamicModint() : val(0) {}DynamicModint(long long v){if (std::abs(v) >= mod()){v %= mod();}if (v < 0){v += mod();}val = v;}static void set_mod(int m){MOD = m;}mint &operator++(){val++;if (val == mod()){val = 0;}return *this;}mint &operator--(){if (val == 0){val = mod();}val--;return *this;}mint &operator+=(const mint &x){val += x.val;if (val >= mod()){val -= mod();}return *this;}mint &operator-=(const mint &x){val -= x.val;if (val < 0){val += mod();}return *this;}mint &operator*=(const mint &x){val = (int)((long long)val * x.val % mod());return *this;}mint &operator/=(const mint &x){*this *= x.inv();return *this;}mint operator-(){return mint() - *this;}mint pow(long long n) const{mint x = 1, r = *this;while (n){if (n & 1){x *= r;}r *= r;n >>= 1;}return x;}mint inv() const{return pow(mod() - 2);}friend mint operator+(const mint &x, const mint &y){return mint(x) += y;}friend mint operator-(const mint &x, const mint &y){return mint(x) -= y;}friend mint operator*(const mint &x, const mint &y){return mint(x) *= y;}friend mint operator/(const mint &x, const mint &y){return mint(x) /= y;}friend bool operator==(const mint &x, const mint &y){return x.val == y.val;}friend bool operator!=(const mint &x, const mint &y){return x.val != y.val;}friend std::ostream &operator<<(std::ostream &os, const mint &x){return os << x.val;}friend std::istream &operator>>(std::istream &is, mint &x){long long v;is >> v;x = mint(v);return is;}private:static int MOD;static int mod(){return MOD;}};int DynamicModint::MOD = 998244353;using mint = DynamicModint;int main(){int n, m;cin >> n >> m;DynamicModint::set_mod(m);mint dp[8];dp[4] = 1;mint ans = 1;for (int j = 2; j <= n * 2 - 1; j++){mint d[8];d[1] = dp[1] + dp[2] + dp[3];d[2] = dp[1] * (j - 2) + dp[4] + dp[5];d[3] = dp[2] + dp[3] + dp[6] + dp[7];d[4] = dp[1] * (j - 2) * (j - 1);d[5] = dp[2] * (j - 1) + dp[3] * (j - 1);d[6] = dp[4] + dp[5];d[7] = dp[6] + dp[7];swap(dp, d);if (j % 2){ans *= dp[1];}}for (int i = 1; i <= n * 2 - 1; i++){ans *= i;}cout << ans << endl;}