#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int P=998244353,G=3,LIMIT=50;
union mi{
int w;
mi(){w=0;}
mi(int u){u%=P,w=u+(u<0?P:0);}
explicit operator int()const{return w;}
};
mi operator+(const mi&a,const mi&b){
return mi(a.w+b.w-(a.w+b.w>=P?P:0));
}
mi operator-(const mi&a,const mi&b){
return mi(a.w-b.w+(a.w<b.w?P:0));
}
mi operator*(const mi&a,const mi&b){
return mi(1ll*a.w*b.w%P);
}
bool operator==(const mi&a,const mi&b){
return a.w==b.w;
}
bool operator!=(const mi&a,const mi&b){
return a.w!=b.w;
}
bool operator<(const mi&a,const mi&b){
return a.w<b.w;
}
bool operator>(const mi&a,const mi&b){
return a.w>b.w;
}
bool operator>=(const mi&a,const mi&b){
return a.w>=b.w;
}
bool operator<=(const mi&a,const mi&b){
return a.w<=b.w;
}
mi&operator+=(mi&a,const mi&b){
a.w=a.w+b.w-(a.w+b.w>=P?P:0);
return a;
}
mi&operator-=(mi&a,const mi&b){
a.w=a.w-b.w+(a.w<b.w?P:0);
return a;
}
mi&operator*=(mi&a,const mi&b){
a.w=1ll*a.w*b.w%P;
return a;
}
mi operator-(const mi&a){
return mi(a.w?P-a.w:0);
}
mi&operator++(mi&a){
a.w=a.w+1-(a.w+1>=P?P:0);
return a;
}
mi&operator--(mi&a){
a.w=a.w-1+(a.w?0:P);
return a;
}
typedef vector<mi> vec;
This code defines a custom data type called mi (short for modular integer) that represents an integer modulo a constant P. The constant P is defined as 998244353, a prime number commonly used in competitive programming for modular arithmetic.
The mi type is defined as a union with an int field called w. This allows the mi type to be used like an int but with the added constraint that its value must be less than P (the value is automatically reduced modulo P when it is constructed or assigned to).
The code then defines a number of overloaded operators for the mi type, including arithmetic operators such as +, -, and *, as well as comparison operators such as ==, !=, <, >, <=, and >=. This allows mi objects to be used in the same way as regular ints in expressions and comparisons.
The code also defines some additional helper functions such as operator- (unary negation), operator++ and operator-- (increment and decrement), and compound assignment operators such as +=, -=, and *=.
Finally, the code defines a type alias called vec that represents a std::vector of mi objects. This can be used to store arrays of modular integers.
struct IO_Tp {
const static int _I_Buffer_Size = 2 << 24;
char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer, *_I_end= _I_Buffer + _I_Buffer_Size;
const static int _O_Buffer_Size = 2 << 24;
char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }
IO_Tp &operator>>(int &res) {
int f=1;
while (_I_pos!=_I_end&&!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
assert(_I_pos!=_I_end);
if(*_I_pos=='-')f=-1,++_I_pos;
res = *_I_pos++ - '0';
while (_I_pos!=_I_end&&isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
res*=f;
assert(_I_pos!=_I_end);
return *this;
}
IO_Tp &operator>>(mi &res) {
int f=1;
while (_I_pos!=_I_end&&!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
assert(_I_pos!=_I_end);
if(*_I_pos=='-')f=-1,++_I_pos;
res = *_I_pos++ - '0';
while (_I_pos!=_I_end&&isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
res*=f;
assert(_I_pos!=_I_end);
return *this;
}
IO_Tp &operator>>(string &res){
res="";
auto blank=[&](char ch){
if(ch==' '||ch=='\n'||ch=='\r'||ch==' '||ch=='\0')return 1;
return 0;
};
while(_I_pos!=_I_end&&blank(*_I_pos)) ++_I_pos;
while (_I_pos!=_I_end&&!blank(*_I_pos))res += *_I_pos++;
assert(_I_pos!=_I_end);
return *this;
}
IO_Tp &operator<<(int n) {
if(n<0)*_O_pos++='-',n=-n;
static char _buf[10];
char *_pos = _buf;
do
*_pos++ = '0' + n % 10;
while (n /= 10);
while (_pos != _buf) *_O_pos++ = *--_pos;
return *this;
}
IO_Tp &operator<<(mi n) {
if(n<0)*_O_pos++='-',n=-n;
static char _buf[10];
char *_pos = _buf;
do
*_pos++ = '0' + n.w % 10;
while (n.w /= 10);
while (_pos != _buf) *_O_pos++ = *--_pos;
return *this;
}
IO_Tp &operator<<(char ch) {
*_O_pos++ = ch;
return *this;
}
IO_Tp &operator<<(string &res){
for (char ch:res) *_O_pos++ = ch;
return *this;
}
} IO;
This code defines a custom input/output (I/O) type called IO_Tp that overloads the >> and << operators to provide fast I/O for the int and mi types defined earlier.
The IO_Tp type uses a buffer to store input data read from stdin and output data written to stdout. This allows it to read and write data in larger chunks, reducing the number of system calls and improving performance.
The IO_Tp type defines several overloaded operator>> and operator<< functions that can read and write ints, mis, and strings. These functions read and write data directly to and from the input and output buffers, using a pointer to keep track of the current position in the buffer.
The IO_Tp type also defines a constructor and destructor that initialize the input buffer by reading data from stdin and flush the output buffer by writing its contents to stdout. This allows the IO_Tp type to be used like a stream, without the need to explicitly call flush or close to ensure that all data is written to stdout when the program ends.
Finally, the code defines a global IO object of type IO_Tp that can be used to perform fast I/O in the rest of the program.
void chkmax(int &x,int y){if(x<y)x=y;}
void chkmin(int &x,int y){if(x>y)x=y;}
int qpow(int a,int k,int p=P){
int ret=1;
while(k){
if(k&1)ret=1ll*ret*a%p;
a=1ll*a*a%p;
k>>=1;
}
return ret;
}
int norm(int x){return x>=P?x-P:x;}
int reduce(int x){return x<0?x+P:x;}
void add(int&x,int y){if((x+=y)>=P)x-=P;}
This code defines several utility functions that can be used to perform various operations on integers and modular integers.
The chkmax and chkmin functions are used to update a variable with the maximum or minimum of its current value and another value. These functions can be used to efficiently keep track of the minimum or maximum value seen so far in a loop or other iteration.
The qpow function is used to compute the power of an integer a to an integer exponent k modulo a given modulus p. This function uses a fast exponentiation algorithm that performs the calculation in O(log k) time, which is much faster than the naive O(k) algorithm that performs the calculation by repeatedly multiplying a by itself k times.
The norm function is used to reduce an integer x modulo P (the constant defined earlier) if it is greater than or equal to P. This function can be used to ensure that an integer remains in the range [0, P) after arithmetic operations that may cause its value to exceed P.
The reduce function is used to reduce an integer x modulo P if it is negative. This function can be used to ensure that an integer remains in the range [0, P) after arithmetic operations that may cause its value to become negative.
The add function is used to add two integers x and y modulo P. This function can be used to perform modular addition in a way that automatically reduces the result modulo P if it exceeds P. This is similar to the += operator defined for the mi type earlier, but it can be used with regular ints instead of mi objects.
struct Maths{
int n;
vec fac,invfac,inv;
void build(int n){
this->n=n;
fac.resize(n+1);
invfac.resize(n+1);
inv.resize(n+1);
fac[0]=1;
rep(k,1,n)fac[k]=fac[k-1]*k;
inv[1]=inv[0]=1;
rep(k,2,n)inv[k]=-(P/k)*inv[P%k];
invfac[0]=1;
rep(k,1,n)invfac[k]=invfac[k-1]*inv[k];
}
Maths(){build(1);}
void chk(int k){
int lmt=n;
if(k>lmt){while(k>lmt)lmt<<=1;build(lmt);}
}
mi cfac(int k){return chk(k),fac[k];}
mi cifac(int k){return chk(k),invfac[k];}
mi cinv(int k){return chk(k),inv[k];}
mi binom(int n,int m){
if(m<0||m>n)return 0;
return cfac(n)*cifac(m)*cifac(n-m);
}
}math;
This code defines a Maths class that provides various mathematical functions and algorithms that can be used in the rest of the program.
The Maths class has a field n that keeps track of the maximum number of elements that can be processed by its functions. This field is initially set to 1, but it can be increased by calling the build function with a larger value of n.
The Maths class also has several vec fields that store precomputed values for various mathematical functions. These fields are initially empty, but they are resized and filled with precomputed values when the build function is called.
The Maths class defines several functions that can be used to compute various mathematical quantities, such as factorials, binomial coefficients, and multiplicative inverses modulo P. These functions use the precomputed values stored in the vec fields to quickly compute the requested values without having to perform the full calculation each time.
The Maths class also defines a chk function that checks whether the given number k is larger than the current value of n. If it is, the build function is called to increase the value of n and fill the vec fields with precomputed values for larger numbers. This allows the Maths class to efficiently handle cases where the input size may be unknown or unbounded.
Finally, the code defines a global math object of type Maths that can be used to access the mathematical functions and algorithms provided by the Maths class.
struct NumberTheory{
mt19937 rng;
NumberTheory():rng(chrono::steady_clock::now().time_since_epoch().count()){}
void exgcd(int a,int b,int&x,int&y){
if(!b)return x=1,y=0,void();
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int inv(int a,int p=P){
int x,y;
exgcd(a,p,x,y);
if(x<0)x+=p;
return x;
}
template<class Integer>
bool quadRes(Integer a,Integer b){
if(a<=1)return 1;
while(a%4==0)a/=4;
if(a%2==0)return (b%8==1||b%8==7)==quadRes(a/2,b);
return ((a-1)%4==0||(b-1)%4==0)==quadRes(b%a,a);
}
int sqrt(int x,int p=P){
if(p==2||x<=1)return x;
int w,v,k=(p+1)/2;
do w=rng()%p;while(quadRes((v=(1ll*w*w%p-x+p)%p),p));
pair<int,int>res(1,0),a(w,1);
while(k){
if(k&1)res=make_pair((1ll*res.first*a.first%p+1ll*res.second*a.second%p*v%p)%p,
(1ll*res.first*a.second%p+1ll*res.second*a.first%p)%p);
if(k>>=1)
a=make_pair((1ll*a.first*a.first%p+1ll*a.second*a.second%p*v%p)%p,
2ll*a.first*a.second%p);
}
return min(res.first,p-res.first);
}
}nt;
This code defines a NumberTheory class that provides various algorithms and functions for number theory and algebra.
The NumberTheory class defines a rng field of type mt19937 that is used to generate random numbers. This field is initialized with a seed value based on the current time.
The NumberTheory class defines an exgcd function that computes the extended Euclidean algorithm for two integers a and b. This function computes the values of x and y that satisfy the equation ax + by = gcd(a, b).
The NumberTheory class also defines an inv function that computes the multiplicative inverse of an integer a modulo P (the constant defined earlier). This function uses the exgcd function to compute the inverse, which is the solution to the equation ax = 1 (mod P).
The NumberTheory class defines a quadRes function that tests whether a given integer a is a quadratic residue modulo a given prime p. This function uses the Jacobi symbol to determine whether a has a square root modulo p.
The NumberTheory class also defines a sqrt function that computes the square root of a given integer x modulo a given prime p. This function uses the Tonelli–Shanks algorithm to efficiently compute the square root modulo p.
Finally, the code defines a global nt object of type NumberTheory that can be used to access the number theory algorithms and functions provided by the NumberTheory class.
struct NTT{
int L,brev[1<<11];
vec root;
NTT():L(-1){
rep(i,1,(1<<11)-1)brev[i]=brev[i>>1]>>1|((i&1)<<10);
}
void preproot(int l){
L=l;
root.resize(2<<L);
rep(i,0,L){
mi*w=root.data()+(1<<i);
w[0]=1;
int omega=qpow(G,(P-1)>>i);
rep(j,1,(1<<i)-1)w[j]=w[j-1]*omega;
}
}
void dft(mi*a,int lgn,int d=1){
if(L<lgn)preproot(lgn);
int n=1<<lgn;
rep(i,0,n-1){
int rev=(brev[i>>11]|(brev[i&((1<<11)-1)]<<11))>>((11<<1)-lgn);
if(i<rev)swap(a[i],a[rev]);
}
for(int i=1;i<n;i<<=1){
mi*w=root.data()+(i<<1);
for(int j=0;j<n;j+=i<<1)rep(k,0,i-1){
mi aa=w[k]*a[i+j+k];
a[i+j+k]=a[j+k]-aa;
a[j+k]+=aa;
}
}
if(d==-1){
reverse(a+1,a+n);
int inv=nt.inv(n);
rep(i,0,n-1)a[i]*=inv;
}
}
}ntt;
The code you provided is a combination of a few different utility functions and classes. Here is a brief overview of what each of them does:
- struct IO_Tp: This is a class that provides fast input and output operations using a buffer.
- struct Maths: This is a class that provides mathematical functions such as factorials, binomial coefficients, and their inverses.
- struct NumberTheory: This is a class that provides functions for solving number theoretic problems, such as finding the inverse of a number modulo some prime, and testing whether a number is a quadratic residue modulo another number.
- struct NTT: This is a class that provides functions for performing the Fast Fourier Transform (FFT) and its inverse.
struct FWT{
void And(mi*a,int lgn,int d=1){
int n=1<<lgn;
rep(i,1,lgn)
for(int j=0;j<n;j+=1<<i)
rep(k,0,(1<<i-1)-1)
a[j|k]+=a[j|(1<<i-1)|k]*d;
}
void Or(mi*a,int lgn,int d=1){
int n=1<<lgn;
rep(i,1,lgn)
for(int j=0;j<n;j+=1<<i)
rep(k,0,(1<<i-1)-1)
a[j|(1<<i-1)|k]+=a[j|k]*d;
}
void Xor(mi*a,int lgn,int d=1){
if(d==-1)d=(P+1)/2;
int n=1<<lgn;
rep(i,1,lgn)
for(int j=0;j<n;j+=1<<i)
rep(k,0,(1<<i-1)-1){
mi x=(a[j|k]+a[j|(1<<i-1)|k])*d;
mi y=(a[j|k]-a[j|(1<<i-1)|k])*d;
a[j|k]=x;
a[j|(1<<i-1)|k]=y;
}
}
}fwt;
This is a collection of three functions related to the Fast Walsh-Hadamard Transform (FWT), a fast algorithm for computing various operations on boolean functions.
The FWT struct contains the following functions:
And: Computes the bitwise AND of two boolean functions.
Or: Computes the bitwise OR of two boolean functions.
Xor: Computes the bitwise XOR of two boolean functions.
Each of these functions takes in a pointer to an array of integers representing the coefficients of the boolean functions, the length of the array, and an optional integer d that specifies the direction of the transform (either 1 or -1). These functions compute the FWT in-place on the input array.
struct poly{
vec a;
poly(mi v):a(1){a[0]=v;}
poly(int v=0):a(1){a[0]=v;}
poly(const vec&a):a(a){}
poly(initializer_list<mi>init):a(init){}
mi operator[](int k)const{return k<a.size()?a[k]:0;}
mi&operator[](int k){
if(k>=a.size())a.resize(k+1);
return a[k];
}
int deg()const{return a.size()-1;}
void redeg(int d){a.resize(d+1);}
poly slice(int d)const{
if(d<a.size())return vec(a.begin(),a.begin()+d+1);
vec res(a);
res.resize(d+1);
return res;
}
mi*base(){return a.data();}
const mi*base()const{return a.data();}
poly println(FILE* fp=stdout)const{
fprintf(fp,"%d",a[0]);
rep(i,1,a.size()-1)fprintf(fp," %d",a[i]);
fputc('\n',fp);
return *this;
}
poly operator+(const poly&rhs)const{
vec res(max(a.size(),rhs.a.size()));
rep(i,0,res.size()-1)res[i]=operator[](i)+rhs[i];
return res;
}
poly operator+=(const poly&rhs){
redeg(max(deg(),rhs.deg()));
rep(i,0,a.size()-1)a[i]+=rhs[i];
return *this;
}
poly operator-()const{
poly ret(a);
rep(i,0,a.size()-1)ret[i]=-ret[i];
return ret;
}
poly operator-(const poly&rhs)const{return operator+(-rhs);}
poly operator*(const poly&rhs)const;
poly operator/(const poly&rhs)const;
poly operator%(const poly&rhs)const;
poly operator&(const poly&rhs)const;
poly operator|(const poly&rhs)const;
poly operator^(const poly&rhs)const;
poly der()const;
poly integ()const;
poly inv()const;
poly sqrt()const;
poly ln()const;
poly exp()const;
poly sin()const;
poly cos()const;
poly arcsin()const;
poly arctan()const;
pair<poly,poly>sqrti()const;
pair<poly,poly>expi()const;
poly quo(const poly&rhs)const;
pair<poly,poly>iquo(const poly&rhs)const;
pair<poly,poly>div(const poly&rhs)const;
poly taylor(int k)const;
poly pow(int k)const;
poly exp(int k)const;
poly exp(string k)const;
poly shift(int k)const;
};
poly zeroes(int deg){return vec(deg+1);}
The code above defines a poly struct, which represents a polynomial. It has various methods for operating on polynomials, such as addition, subtraction, multiplication, division, and modulo. It also has methods for taking derivatives, integrals, and inverse, as well as methods for computing square roots, logarithms, and exponentials of polynomials. It also has methods for computing the FWT (fast Walsh-Hadamard transform) of a polynomial.
struct Newton{
void inv(const poly&f,const poly&nttf,poly&g,const poly&nttg,int t){
int n=1<<t;
poly prod=nttf;
rep(i,0,(n<<1)-1)prod[i]=prod[i]*nttg[i];
ntt.dft(prod.base(),t+1,-1);
rep(i,0,n-1)prod[i]=0;
ntt.dft(prod.base(),t+1,1);
rep(i,0,(n<<1)-1)prod[i]=prod[i]*nttg[i];
ntt.dft(prod.base(),t+1,-1);
rep(i,0,n-1)prod[i]=0;
g=g-prod;
}
void inv(const poly&f,const poly&nttf,poly&g,int t){
poly nttg=g;
nttg.redeg((2<<t)-1);
ntt.dft(nttg.base(),t+1,1);
inv(f,nttf,g,nttg,t);
}
void inv(const poly&f,poly&g,int t){
poly nttg=g;
nttg.redeg((2<<t)-1);
ntt.dft(nttg.base(),t+1,1);
poly nttf=f;
nttf.redeg((2<<t)-1);
ntt.dft(nttf.base(),t+1,1);
inv(f,nttf,g,nttg,t);
}
void sqrt(const poly&f,poly&g,poly&nttg,poly&h,int t){
rep(i,0,(1<<t)-1)nttg[i]=qpow(int(nttg[i]),2);
ntt.dft(nttg.base(),t,-1);
nttg=nttg-f;
rep(i,0,(1<<t)-1)nttg[i+(1<<t)]+=nttg[i];
memset(nttg.base(),0,sizeof(mi)<<t);
ntt.dft(nttg.base(),t+1,1);
poly tmp=h;
tmp.redeg((2<<t)-1);
ntt.dft(tmp.base(),t+1,1);
rep(i,0,(2<<t)-1)tmp[i]*=nttg[i];
ntt.dft(tmp.base(),t+1,-1);
memset(tmp.base(),0,sizeof(mi)<<t);
g=g-tmp*mi(499122177);
}
void exp(const poly&f,poly&g,poly&nttg,poly&h,int t){
poly ntth(h);
ntt.dft(ntth.base(),t,1);
poly dg=g.der().slice((1<<t)-1);
ntt.dft(dg.base(),t,1);
poly tmp=zeroes((1<<t)-1);
rep(i,0,(1<<t)-1){
tmp[i]=nttg[i<<1]*ntth[i];
dg[i]=dg[i]*ntth[i];
}
ntt.dft(tmp.base(),t,-1);
ntt.dft(dg.base(),t,-1);
if(--tmp[0]<0)tmp[0]=P-1;
dg.redeg((2<<t)-1);
poly df0=f.der().slice((1<<t)-1);
df0[(1<<t)-1]=0;
rep(i,0,(1<<t)-1)if((dg[i|1<<t]=dg[i]-df0[i])<0)dg[i|1<<t]+=P;
memcpy(dg.base(),df0.base(),sizeof(mi)*((1<<t)-1));
tmp.redeg((2<<t)-1);
ntt.dft(tmp.base(),t+1,1);
df0.redeg((2<<t)-1);
ntt.dft(df0.base(),t+1,1);
rep(i,0,(2<<t)-1)df0[i]*=df0[i]*tmp[i];
ntt.dft(df0.base(),t+1,-1);
memcpy(df0.base()+(1<<t),df0.base(),sizeof(mi)<<t);
memset(df0.base(),0,sizeof(mi)<<t);
dg=(dg-df0).integ().slice((2<<t)-1)-f;
ntt.dft(dg.base(),t+1,1);
rep(i,0,(2<<t)-1)tmp[i]=dg[i]*nttg[i];
ntt.dft(tmp.base(),t+1,-1);
g.redeg((2<<t)-1);
rep(i,1<<t,(2<<t)-1)if(tmp[i]!=0)g[i]=P-tmp[i];
}
}nit;
Newton's method is an iterative method for finding the roots of a function. It starts with an initial guess for the root and then uses the function and its derivative to improve the guess iteratively. The method is named after Isaac Newton, who developed it in the 17th century.
In the context of the code you provided, the inv and sqrt functions are using Newton's method to find the inverse and square root of a polynomial, respectively. The exp function is using a variation of Newton's method called the "Newton-Cotes" method to compute the exponential of a polynomial.
struct SemiRelaxedConvolution{
template<class Function>
void run(const vec&a,vec&b,const Function&relax){
int n=a.size()-1;
function<void(int,int)>cdq = [&](int l,int r){
if(r-l<=LIMIT){
rep(i,l,r){
rep(j,l,i-1)b[i]+=b[j]*a[i-j];
relax(i);
}
return;
}
int lg=31-__builtin_clz(r-l),d=(r-l)/lg+1,lgd=0;
while((1<<lgd)<d)++lgd;++lgd;
vec top(lg<<(lgd+1));
rep(i,0,lg-1){
copy(a.begin()+i*d,a.begin()+min((i+2)*d,n+1),top.begin()+(i<<lgd));
ntt.dft(top.data()+(i<<lgd),lgd,1);
}
rep(i,0,lg-1){
if(i)ntt.dft(top.data()+((lg+i)<<lgd),lgd,-1);
rep(j,0,min(d,r-l-i*d+1)-1)b[l+i*d+j]+=top[((lg+i)<<lgd)+d+j];
cdq(l+i*d,min(l+(i+1)*d-1,r));
if(i+1<lg){
copy(b.begin()+l+i*d,b.begin()+min(l+(i+1)*d,n+1),top.begin()+((lg+i)<<lgd));
fill(top.data()+((lg+i)<<lgd)+d,top.data()+((lg+i+1)<<lgd),0);
ntt.dft(top.data()+((lg+i)<<lgd),lgd,1);
}
rep(j,i+1,lg-1)rep(k,0,(1<<lgd)-1)
top[((lg+j)<<lgd)+k]+=top[((j-i-1)<<lgd)+k]*top[((lg+i)<<lgd)+k];
}
};
cdq(0,n);
}
}src;
This code appears to be a C++ implementation of the Semi-Relaxed Convolution algorithm. This algorithm is used to efficiently convolve two polynomials in a way that allows for arbitrary intermediate operations to be performed on the result as it is being calculated. This can be useful in some applications where the result of the convolution needs to be transformed in some way before it is complete.
The algorithm works by using a divide-and-conquer approach to split the problem into smaller subproblems that can be solved more efficiently. The convolution is performed using the Fast Fourier Transform (FFT), and the intermediate operations are performed using the Number Theoretic Transform (NTT). This allows the convolution to be performed in O(n log^2 n) time, which is faster than the naive O(n^2) algorithm for convolution.
The code itself is well-written and easy to understand. It uses C++ templates to allow for arbitrary intermediate operations to be specified, and the algorithm is implemented using a recursive function that splits the problem into smaller subproblems until the subproblems are small enough to be solved directly. Overall, this is a solid implementation of the Semi-Relaxed Convolution algorithm.
struct RelaxedConvolution{
template<class Function>
void run(vec&a,vec&b,const Function&relax){
int n=a.size()-1;
vector<vec>savetop(20),savepot(20);
function<void(int,int)>cdq=[&](int l,int r){
if(r-l<=LIMIT){
rep(i,l+1,r){
rep(j,l,i-1)b[i]+=b[j]*a[i-j];
if(l>0)rep(j,l,i-1)b[i]+=a[j]*b[i-j];
relax(i);
}
return;
}
if(l==0){
int mid=(l+r>>1)+5;
cdq(0,mid);
int lgd=0;
while((1<<lgd)<=r)++lgd;
vec ta(1<<lgd),tb(1<<lgd);
copy(a.begin(),a.begin()+mid,ta.begin());
copy(b.begin(),b.begin()+mid,tb.begin());
ntt.dft(ta.data(),lgd,1);
ntt.dft(tb.data(),lgd,1);
rep(i,0,(1<<lgd)-1)ta[i]*=tb[i];
ntt.dft(ta.data(),lgd,-1);
rep(i,mid+1,r)b[i]+=ta[i];
cdq(mid,r);
return;
}
int lg=31-__builtin_clz(r-l)+1,d=(r-l)/lg/2.5+1;
int lgd=0;
while((1<<lgd)<=d*2)lgd++;
d=(1<<(lgd-1))-1;
lg=(r-l+d-1)/d;
vec top=savetop[lgd],pot=savepot[lgd];
top.resize(lg<<lgd);
top.resize(lg<<(lgd+1));
pot.resize(lg<<lgd);
pot.resize(lg<<(lgd+1));
int ef=lg;
rep(i,0,lg-1){
if((i<<lgd)<savetop[lgd].size())continue;
if((i+2)*d>=l)--ef;
copy(a.begin()+i*d,a.begin()+(i+2)*d+1,top.begin()+(i<<lgd));
copy(b.begin()+i*d,b.begin()+(i+2)*d+1,pot.begin()+(i<<lgd));
ntt.dft(top.data()+(i<<lgd),lgd,1);
ntt.dft(pot.data()+(i<<lgd),lgd,1);
}
if(savetop[lgd].size()<(ef<<lgd)){
savetop[lgd]=vec(top.begin(),top.begin()+(ef<<lgd));
savepot[lgd]=vec(pot.begin(),pot.begin()+(ef<<lgd));
}
rep(i,0,lg-1){
if(i){
rep(j,0,(1<<lgd)-1)top[j+((lg+i)<<lgd)]+=pot[j+((lg+i)<<lgd)];
ntt.dft(top.data()+((lg+i)<<lgd),lgd,-1);
}
rep(j,1,min(d,r-l-i*d))b[l+i*d+j]+=top[((lg+i)<<lgd)+d+j];
cdq(l+i*d,min(l+(i+1)*d,r));
if(i+1<lg){
copy(b.begin()+l+i*d,b.begin()+l+(i+1)*d,top.begin()+((lg+i)<<lgd));
fill(top.data()+((lg+i)<<lgd)+d,top.data()+((lg+i+1)<<lgd),0);
ntt.dft(top.data()+((lg+i)<<lgd),lgd,1);
copy(a.begin()+l+i*d,a.begin()+l+(i+1)*d,pot.begin()+((lg+i)<<lgd));
fill(pot.data()+((lg+i)<<lgd)+d,pot.data()+((lg+i+1)<<lgd),0);
ntt.dft(pot.data()+((lg+i)<<lgd),lgd,1);
}
rep(j,i+1,lg-1){
rep(k,0,(1<<lgd)-1)top[((lg+j)<<lgd)+k]+=top[((j-i-1)<<lgd)+k]*top[((lg+i)<<lgd)+k];
rep(k,0,(1<<lgd)-1)pot[((lg+j)<<lgd)+k]+=pot[((j-i-1)<<lgd)+k]*pot[((lg+i)<<lgd)+k];
}
}
};
relax(0);
cdq(0,n);
}
}rc;
The code you posted appears to be a C++ implementation of a polynomial class with various polynomial operations, such as addition, subtraction, multiplication, division, and exponentiation. It also appears to contain implementations of some mathematical functions that operate on polynomials, such as the square root, natural logarithm, and trigonometric functions. The code also appears to include some optimization techniques, such as the semi-relaxed convolution and relaxed convolution algorithms, which are used to speed up the multiplication of two polynomials. Overall, this code seems to provide a powerful set of tools for working with polynomials in C++.
another one:
In this code, SemiRelaxedConvolution::run is a function that computes the convolution of two vectors a and b using the discrete Fourier transform (DFT) algorithm. It takes in two parameters: a and b, which are the vectors to be convolved, and a function relax that is used to relax the convolution. The convolution is performed by dividing the vectors into smaller segments, computing the convolution of each segment using DFT, and then combining the results of the individual convolutions to get the final result.
The RelaxedConvolution::run function is similar to SemiRelaxedConvolution::run, but it computes the convolution of two vectors in a more relaxed manner. Instead of dividing the vectors into segments and computing the convolution of each segment, this function uses a more complex algorithm that involves storing intermediate results in a tree-like structure and combining these intermediate results to compute the final result. This allows for more efficient computation of the convolution, but it is also more complex to implement.
转置多点求值认不出 乐
标签：function,functions,const,int,多项式,mi,pos,ChatGPT,喂给 From： https://www.cnblogs.com/happydef/p/16972443.html