当前位置:网站首页>tourist的NTT模板
tourist的NTT模板
2022-07-07 22:41:00 【愚末语】
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
return v;
}
const Type& operator()() const { return value; }
template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular& operator++() { return *this += 1; }
Modular& operator--() { return *this -= 1; }
Modular operator++(int) { Modular result(*this); *this += 1; return result; }
Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (mod())
);
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
friend const Type& abs(const Modular& x) { return x.value; }
template <typename U>
friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
template <typename U>
friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
template <typename V, typename U>
friend V& operator>>(V& stream, Modular<U>& number);
private:
Type value;
};
template <typename T>
class NTT {
public:
using Type = typename decay<decltype(T::value)>::type;
static Type md;
static Modular<T> root;
static int base;
static int max_base;
static vector<Modular<T>> roots;
static vector<int> rev;
static void clear() {
root = 0;
base = 0;
max_base = 0;
roots.clear();
rev.clear();
}
static void init() {
md = T::value;
assert(md >= 3 && md % 2 == 1);
auto tmp = md - 1;
max_base = 0;
while (tmp % 2 == 0) {
tmp /= 2;
max_base++;
}
root = 2;
while (power(root, (md - 1) >> 1) == 1) {
root++;
}
assert(power(root, md - 1) == 1);
root = power(root, (md - 1) >> max_base);
base = 1;
rev = {0, 1};
roots = {0, 1};
}
static void ensure_base(int nbase) {
if (md != T::value) {
clear();
}
if (roots.empty()) {
init();
}
if (nbase <= base) {
return;
}
assert(nbase <= max_base);
rev.resize(1 << nbase);
for (int i = 0; i < (1 << nbase); i++) {
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
}
roots.resize(1 << nbase);
while (base < nbase) {
Modular<T> z = power(root, 1 << (max_base - 1 - base));
for (int i = 1 << (base - 1); i < (1 << base); i++) {
roots[i << 1] = roots[i];
roots[(i << 1) + 1] = roots[i] * z;
}
base++;
}
}
static void fft(vector<Modular<T>> &a) {
int n = (int) a.size();
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for (int i = 0; i < n; i++) {
if (i < (rev[i] >> shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for (int k = 1; k < n; k <<= 1) {
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
Modular<T> x = a[i + j];
Modular<T> y = a[i + j + k] * roots[j + k];
a[i + j] = x + y;
a[i + j + k] = x - y;
}
}
}
}
static vector<Modular<T>> multiply(vector<Modular<T>> a, vector<Modular<T>> b) {
if (a.empty() || b.empty()) {
return {};
}
int eq = (a == b);
int need = (int) a.size() + (int) b.size() - 1;
int nbase = 0;
while ((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
a.resize(sz);
b.resize(sz);
fft(a);
if (eq) b = a; else fft(b);
Modular<T> inv_sz = 1 / static_cast<Modular<T>>(sz);
for (int i = 0; i < sz; i++) {
a[i] *= b[i] * inv_sz;
}
reverse(a.begin() + 1, a.end());
fft(a);
a.resize(need);
return a;
}
};
边栏推荐
- 22年秋招心得
- 智慧监管入场,美团等互联网服务平台何去何从
- Cause analysis and solution of too laggy page of [test interview questions]
- 去了字节跳动,才知道年薪 40w 的测试工程师有这么多?
- How to insert highlighted code blocks in WPS and word
- Development of a horse tourism website (optimization of servlet)
- 玩转Sonar
- Huawei switch s5735s-l24t4s-qa2 cannot be remotely accessed by telnet
- LeetCode刷题
- 【转载】解决conda安装pytorch过慢的问题
猜你喜欢
【GO记录】从零开始GO语言——用GO语言做一个示波器(一)GO语言基础
【编程题】【Scratch二级】2019.12 绘制十个正方形
Reptile practice (VIII): reptile expression pack
【编程题】【Scratch二级】2019.03 垃圾分类
【编程题】【Scratch二级】2019.09 制作蝙蝠冲关游戏
某马旅游网站开发(登录注册退出功能的实现)
Detailed explanation of interview questions: the history of blood and tears in implementing distributed locks with redis
Reentrantlock fair lock source code Chapter 0
The underlying principles and templates of new and delete
从服务器到云托管,到底经历了什么?
随机推荐
Deep dive kotlin synergy (XXII): flow treatment
Qt添加资源文件,为QAction添加图标,建立信号槽函数并实现
【测试面试题】页面很卡的原因分析及解决方案
某马旅游网站开发(登录注册退出功能的实现)
ABAP ALV LVC template
Su embedded training - day4
3 years of experience, can't you get 20K for the interview and test post? Such a hole?
How can CSDN indent the first line of a paragraph by 2 characters?
大数据开源项目,一站式全自动化全生命周期运维管家ChengYing(承影)走向何方?
1293_ Implementation analysis of xtask resumeall() interface in FreeRTOS
When creating body middleware, express Is there any difference between setting extended to true and false in urlencoded?
Go learning notes (2) basic types and statements (1)
他们齐聚 2022 ECUG Con,只为「中国技术力量」
22年秋招心得
How does starfish OS enable the value of SFO in the fourth phase of SFO destruction?
【编程题】【Scratch二级】2019.09 绘制雪花图案
[programming problem] [scratch Level 2] December 2019 flying birds
C language 005: common examples
An error is reported during the process of setting up ADG. Rman-03009 ora-03113
接口测试要测试什么?