当前位置:网站首页>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;
}
};
边栏推荐
- 【编程题】【Scratch二级】2019.03 垃圾分类
- QT establish signal slots between different classes and transfer parameters
- 如果在构造函数中抛出异常,最好的做法是防止内存泄漏?
- Single machine high concurrency model design
- 【obs】Impossible to find entrance point CreateDirect3D11DeviceFromDXGIDevice
- An error is reported during the process of setting up ADG. Rman-03009 ora-03113
- Introduction knowledge system of Web front-end engineers
- C# 泛型及性能比较
- The underlying principles and templates of new and delete
- Go learning notes (1) environment installation and hello world
猜你喜欢
new和delete的底层原理以及模板
52歲的周鴻禕,還年輕嗎?
C language 001: download, install, create the first C project and execute the first C language program of CodeBlocks
智慧监管入场,美团等互联网服务平台何去何从
【obs】官方是配置USE_GPU_PRIORITY 效果为TRUE的
【编程题】【Scratch二级】2019.09 绘制雪花图案
接口测试要测试什么?
测试流程不完善,又遇到不积极的开发怎么办?
Operating system principle --- summary of interview knowledge points
Stm32f1 and stm32cubeide programming example - rotary encoder drive
随机推荐
How to insert highlighted code blocks in WPS and word
[OBS] the official configuration is use_ GPU_ Priority effect is true
Reading notes 004: Wang Yangming's quotations
Relevant methods of sorting arrays in JS (if you want to understand arrays, it's enough to read this article)
[C language] objective questions - knowledge points
“一个优秀程序员可抵五个普通程序员”,差距就在这7个关键点
应用实践 | 数仓体系效率全面提升!同程数科基于 Apache Doris 的数据仓库建设
[programming questions] [scratch Level 2] March 2019 garbage classification
Linkedblockingqueue source code analysis - add and delete
3年经验,面试测试岗20K都拿不到了吗?这么坑?
paddle入门-使用LeNet在MNIST实现图像分类方法二
STM32F1與STM32CubeIDE編程實例-旋轉編碼器驅動
paddle一个由三个卷积层组成的网络完成cifar10数据集的图像分类任务
Is it safe to open an account on the official website of Huatai Securities?
测试流程不完善,又遇到不积极的开发怎么办?
If an exception is thrown in the constructor, the best way is to prevent memory leakage?
关于组织2021-2022全国青少年电子信息智能创新大赛西南赛区(四川)复赛的通知
Scrapy framework
paddle入门-使用LeNet在MNIST实现图像分类方法一
Robomaster visual tutorial (1) camera