test/CF856-D.test.cpp

• View this file on GitHub
• Last update: 2023-03-05 22:25:53+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://codeforces.com/contest/1794/submission/196139941

Depends on

• mod combinations (組み合わせの数 mod) (src/math/mod-combinations.hpp)
• modint (src/math/modint.hpp)
• primeSieve (エラトステネスの篩） (src/math/primeSieve.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/math/primeSieve.hpp"
#include "../src/math/modint.hpp"
#include "../src/math/mod-combinations.hpp"

#include <iostream>
#include <vector>
#include <utility>
#include <map>

const long long mod = 998244353;
const int sup = 1000100;
using mint = zawa::modint<mod>;

int main() {
	// int n; std::cin >> n;
	// std::vector A(2 * n, 0);
	// for (auto& a : A) std::cin >> a;
	// std::map<int, int> mp;
	// for (auto& a : A) mp[a]++;
	// std::vector P(0, std::pair(0, 0));
	// for (const auto& [x, c] : mp) P.emplace_back(x, c);
	// std::vector S(P.size() + 1, 0);
	// for (int i = 0 ; i < (int)P.size() ; i++) S[i + 1] = S[i] + P[i].second;
	// zawa::primeSieve siv(sup);
	// zawa::mod_combinations<mod> mc(sup);
	// std::vector dp(n + 1, mint());
	// dp[0] = mint(1);
	// for (int i = 0 ; i < (int)P.size() ; i++) {
	// 	std::vector nxt(n + 1, mint());
	// 	for (int j = 0 ; j <= n and S[i] - j >= 0 ; j++) {
	// 		nxt[j] += dp[j] * mc.H(S[i] - j + 1, P[i].second);
	// 		if (siv[P[i].first] and j + 1 <= n) {
	// 			nxt[j + 1] += dp[j] * mc.H(S[i] - j + 1, P[i].second - 1);
	// 		}
	// 	}
	// 	dp = std::move(nxt);
	// }
	// std::cout << dp.back().val() << std::endl;

	std::cout << "Hello World" << std::endl;
}

/*
 * Codeforces Round 856(Div. 2) - D Counting Factorizations
 * https://codeforces.com/contest/1794/submission/196139941
 */

#line 1 "test/CF856-D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/math/primeSieve.hpp"

#include <vector>

namespace zawa {

class primeSieve {
private:
	std::vector<bool> sieve;

public:
	primeSieve() {}
	primeSieve(std::size_t n) : sieve(n + 1, true) {
		if (n >= 0) {
			sieve[0] = false;
		}
		if (n >= 1) {
			sieve[1] = false;
		}
		for (std::size_t i = 2 ; i <= n ; i++) {
			if (sieve[i]) {
				for (std::size_t j = i * 2 ; j <= n ; j += i) {
					sieve[j] = false;
				}
			}
		}
	}

	inline bool operator[](std::size_t i) const {
		return sieve[i];
	}

	inline std::size_t size() const {
		return sieve.size();
	}
};

}// namespace zawa
#line 1 "src/math/modint.hpp"
namespace zawa {

    template<long long mod>
    class modint {
    private:
        long long x;

    public:
        modint() : x(0) {}
        
        modint(long long x) : x((x % mod + mod) % mod) {}

        modint& operator+=(modint p) {
            x += p.x;
            if (x >= mod) x -= mod;
            return *this;
        }

        modint& operator-=(modint p) {
            x += mod - p.x;
            if (x >= mod) x -= mod;
            return *this;
        }

        modint& operator*=(modint p) {
            x = (1LL * x * p.x % mod);
            return *this;
        }

        modint& operator/=(modint p) {
            *this *= p.inv();
            return *this;
        }

        modint operator-() const {
            return modint(-x);
        }

        modint operator+(const modint& p) const {
            return modint(*this) += p;
        }

        modint operator-(const modint& p) const {
            return modint(*this) -= p;
        }

        modint operator*(const modint& p) const {
            return modint(*this) *= p;
        }

        modint operator/(const modint& p) const {
            return modint(*this) /= p;
        }

        long long val() {
            return x;
        }

        modint pow(long long p) {
            modint res(1), val(x);
            while(p) {
                if (p & 1) res *= val;
                val *= val;
                p >>= 1;
            }
            return res;
        }

        modint inv() {
            return pow(mod - 2);
        }
    };

}// namespace zawa
#line 2 "src/math/mod-combinations.hpp"

#line 4 "src/math/mod-combinations.hpp"

namespace zawa {

template <long long mod>
class mod_combinations {
private:
    std::vector<long long> facs, inv_facs;

public:
    mod_combinations(std::size_t n) : facs(2 * n + 1, 1LL), inv_facs(2 * n + 1) {
        for (std::size_t i = 0 ; i + 1 < facs.size() ; i++) {
            facs[i + 1] = facs[i] * (i + 1);
            facs[i + 1] %= mod;
        }
        long long base = facs.back();
        long long inv = 1LL;
        long long p = mod - 2;
        while (p > 0) {
            if (p & 1) {
                inv *= base;
                inv %= mod;
            }
            base = (base * base) % mod;
            p >>= 1;
        }
        inv_facs.back() = inv;
        for (int i = (int)facs.size() - 1 ; i - 1 >= 0 ; i--) {
            inv_facs[i - 1] = inv_facs[i] * i;
            inv_facs[i - 1] %= mod;
        }
    }

    long long P(std::size_t n, std::size_t r) {
        if (r > n) {
            return 0LL;
        }
        return (facs[n] * inv_facs[(n - r)]) % mod;
    }

    long long C(std::size_t n, std::size_t r) {
        if (r > n) {
            return 0LL;
        }
        return (P(n, r) * inv_facs[r]) % mod;
    }

    long long H(std::size_t n, std::size_t r) {
        if (n == 0 and r == 0) {
            return 1LL;
        }
        if (r > n + r - 1) {
            return 0LL;
        }
        return C(n + r - 1, r);
    }

    long long F(std::size_t n) {
        return facs[n];
    }

    long long invF(std::size_t n) {
        return inv_facs[n];
    }
};

} // namespace zawa
#line 6 "test/CF856-D.test.cpp"

#include <iostream>
#line 9 "test/CF856-D.test.cpp"
#include <utility>
#include <map>

const long long mod = 998244353;
const int sup = 1000100;
using mint = zawa::modint<mod>;

int main() {
	// int n; std::cin >> n;
	// std::vector A(2 * n, 0);
	// for (auto& a : A) std::cin >> a;
	// std::map<int, int> mp;
	// for (auto& a : A) mp[a]++;
	// std::vector P(0, std::pair(0, 0));
	// for (const auto& [x, c] : mp) P.emplace_back(x, c);
	// std::vector S(P.size() + 1, 0);
	// for (int i = 0 ; i < (int)P.size() ; i++) S[i + 1] = S[i] + P[i].second;
	// zawa::primeSieve siv(sup);
	// zawa::mod_combinations<mod> mc(sup);
	// std::vector dp(n + 1, mint());
	// dp[0] = mint(1);
	// for (int i = 0 ; i < (int)P.size() ; i++) {
	// 	std::vector nxt(n + 1, mint());
	// 	for (int j = 0 ; j <= n and S[i] - j >= 0 ; j++) {
	// 		nxt[j] += dp[j] * mc.H(S[i] - j + 1, P[i].second);
	// 		if (siv[P[i].first] and j + 1 <= n) {
	// 			nxt[j + 1] += dp[j] * mc.H(S[i] - j + 1, P[i].second - 1);
	// 		}
	// 	}
	// 	dp = std::move(nxt);
	// }
	// std::cout << dp.back().val() << std::endl;

	std::cout << "Hello World" << std::endl;
}

/*
 * Codeforces Round 856(Div. 2) - D Counting Factorizations
 * https://codeforces.com/contest/1794/submission/196139941
 */

Back to top page