Skip to content

Instantly share code, notes, and snippets.

View GoBigorGoHome's full-sized avatar

Pat GoBigorGoHome

13 followers · 77 following
View GitHub Profile
@GoBigorGoHome
GoBigorGoHome / 【模板】拉格朗日插值求多项式系数.cpp
Last active December 13, 2019 16:54
用Lagrange插值公式求多项式系数。这个实现针对域Fp上的多项式，且p很小（<= 2999）的情形。一般情况下需要注意爆 long long 的问题。来自 ABC137F。
// tourist 的逆元模板
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
@GoBigorGoHome
GoBigorGoHome / Kick_Start_2019_round_A_Contention.cpp
Created October 4, 2019 18:51
Kick Start 2019 Round A Contention 官方题解的代码实现
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#include <bits/stdc++.h>
#include <type_traits>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
private:
@GoBigorGoHome
GoBigorGoHome / CF1209D Cow and Snacks.cpp
Created September 16, 2019 14:59
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
private:
using ll = long long;
@GoBigorGoHome
GoBigorGoHome / hiho-offer102C.cpp
Last active June 2, 2019 23:30
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
// #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
#endif
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
@GoBigorGoHome
GoBigorGoHome / hiho-offer102B.cpp
Created June 2, 2019 23:15
to submit
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
// #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
#endif
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
@GoBigorGoHome
GoBigorGoHome / hiho-offer102A.cpp
Created June 2, 2019 22:31
to submit
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
// #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
#endif
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
@GoBigorGoHome
GoBigorGoHome / kickstart-2019-Round3-Wiggle-Walk.cpp
Created May 27, 2019 17:52
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
// #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
#endif
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
@GoBigorGoHome
GoBigorGoHome / contest: Codeforces Round #562 (Div. 2), problem: (E) And Reachability-Attempt1.cpp
Created May 26, 2019 20:23
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
// #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
#endif
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
@GoBigorGoHome
GoBigorGoHome / 2019-Kick-Start-Round3-B.cpp
Last active May 27, 2019 03:23
Circuit Board
const int mod1 = 1000000007, mod2 = 998244353;
const int mod = mod1;
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
// #pragma comment(linker, "/STACK:102400000,102400000") // 在 Windows 上有效
#endif
#include <bits/stdc++.h>
using namespace std;
// Andrew He's modular-arithmetic class
template <int MOD_> struct modnum {
@GoBigorGoHome
GoBigorGoHome / 【模板】单调栈求最大矩形.cpp
Created May 26, 2019 12:01
单调栈求最大矩形
auto solve = [](vi& h, int n) {
vi L(n + 1), R(n + 1);
// 严格递增的单调栈
vpii inc{{0, 0}}; // pair.first 表示高度，pair.second 表示下标。假设 h[0] = -INF。
assert(SZ(inc) == 1);
for (int i = 1; i <= n; i++) {
while (inc.back().first >= h[i]) {
inc.pop_back();
}
L[i] = inc.back().second + 1; //左闭