首页 > 其他分享 >2.1闲话 - 『奏起我的幻想曲』

2.1闲话 - 『奏起我的幻想曲』

时间：2024-02-01 21:24:26浏览次数：23  
标签：ch Val Get Fast operator Istream 幻想曲 奏起 2.1

打算换个闲话风格，现在的看起来非常不好

今天手滑交了个图片上去卡住了评测集导致被 D 了

漆黑的夜 古城之中 遗失的传说
漆黑的翼 苏醒之后 陌生的轮廓
是谁在我的身后呼唤 一时的怔忪
是谁在我的心中呼唤 为何不将一切掌控

快速傅立叶之二

我们可以进行卷积的式子标准形式形如

\[\begin{align} c[i]=\sum_{j=0}^ia[j]b[i-j] \end{align} \]

本题的原式可以表示为

\[\begin{align} c(k)&=\sum_{i=k}^{n-1}(a(i)*b(i-k) )\\ \end{align} \]

考虑让第二个式子变成第一个

先把 \(b\) 翻转，那么$$c(k)=\sum_{i=k}^{n-1}(a(i)*b(n-i+k))$$

假设 $$d(k)=\sum_{i=k}^{i-1}a(i)*b(k-i)$$

那么就好解了(?

\[c(k)=d(n+k) \]

此处的\(d\)可以直接 \(\text{FFT}\)

这题就解决了

  • 代码

    点击查看代码 
    

#include<bits/stdc++.h>
inline void fire(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);}
namespace Fast_I {char *_Buf, *_Start_ptr, *_End_ptr;std::streambuf* inbuf;unsigned int Size;bool _Ok;struct Fast_Istream {operator bool(){return _Ok; }Fast_Istream(std::streambuf*, unsigned int);Fast_Istream(unsigned int);Fast_Istream(const char*, unsigned int);Fast_Istream& operator>>(char&);Fast_Istream& operator>>(char*);Fast_Istream& operator>>(bool&);Fast_Istream& operator>>(short&);Fast_Istream& operator>>(int&);Fast_Istream& operator>>(long&);Fast_Istream& operator>>(long long&);Fast_Istream& operator>>(unsigned short&);Fast_Istream& operator>>(unsigned int&);Fast_Istream& operator>>(unsigned long&);Fast_Istream& operator>>(unsigned long long&);Fast_Istream& operator>>(float&);Fast_Istream& operator>>(double&);Fast_Istream& operator>>(long double&);Fast_Istream& operator>>(std::string&);template <typename Typex>void operator()(Typex& _Val) { *this >> _Val; }template <typename Typex, typename... More>void operator()(Typex&, More&...);std::streambuf* rdbuf() { return inbuf; }void rdbuf(std::streambuf* _inbuf) { inbuf = _inbuf; }void rdbuf(const char*);void pop();char peek();};}
namespace Fast_O {std::string buf;std::streambuf* outbuf;struct Fast_Ostream {Fast_Ostream(std::streambuf*, unsigned int);Fast_Ostream(std::streambuf* out) { outbuf = out; }Fast_Ostream(const char*, unsigned int);Fast_Ostream(unsigned int);void flush();~Fast_Ostream();void endl() { buf.push_back('\n'); }template <typename Typex>void endl(const Typex& _Val);template <typename Typex, typename... More>void endl(const Typex&, const More&...);template <typename Typex>void operator()(const Typex& _Val);template <typename Typex, typename... More>void operator()(const Typex&, const More&...);Fast_Ostream& operator<<(char);Fast_Ostream& operator<<(const char*);Fast_Ostream& operator<<(const std::string&);Fast_Ostream& operator<<(bool);Fast_Ostream& operator<<(short);Fast_Ostream& operator<<(int);Fast_Ostream& operator<<(long);Fast_Ostream& operator<<(long long);Fast_Ostream& operator<<(unsigned short);Fast_Ostream& operator<<(unsigned int);Fast_Ostream& operator<<(unsigned long);Fast_Ostream& operator<<(unsigned long long);std::streambuf* rdbuf() { return outbuf; }void rdbuf(std::streambuf* _outbuf) { outbuf = _outbuf; }void rdbuf(const char*);};}
namespace Fast_IO {Fast_I::Fast_Istream fin(std::cin.rdbuf(), 1048576);Fast_O::Fast_Ostream fout(std::cout.rdbuf()); }
#define cin Fast_IO::fin
#define cout Fast_IO::fout
namespace Fast_I {Fast_Istream::Fast_Istream(std::streambuf* in, unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;inbuf = in;_Start_ptr = _End_ptr = _Buf = new char[Sz];}Fast_Istream::Fast_Istream(const char* in, unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;rdbuf(in);_Start_ptr = _End_ptr = _Buf = new char[Sz];}Fast_Istream::Fast_Istream(unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;_Start_ptr = _End_ptr = _Buf = new char[Sz];}void Fast_Istream::rdbuf(const char* File) {static std::ifstream __In__(File);rdbuf(__In__.rdbuf());}void Get_Char(char& _Val) {if (_Start_ptr == _End_ptr) {_Start_ptr = _Buf;_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);}if (_Start_ptr == _End_ptr) {_Val = -1;_Ok = 0;} else {_Val = *_Start_ptr++;}}Fast_Istream& Fast_Istream::operator>>(char& _Val) {if(_Ok){Get_Char(_Val);while (_Val == 32 || _Val == 10 || _Val == 13 || _Val == 8 || _Val == 9 || _Val == 7 || _Val == 12 || _Val == 11) {Get_Char(_Val);}}return *this;}Fast_Istream& Fast_Istream::operator>>(char* _Val) {if (_Ok) {Get_Char(*_Val);while (*_Val == 32 || *_Val == 10 || *_Val == 13 || *_Val == 8 ||*_Val == 9 || *_Val == 7 || *_Val == 12 || *_Val == 11) {Get_Char(*_Val);}while (*_Val != 32 && *_Val != 10 && *_Val && *_Val != -1 && *_Val != 9 &&*_Val != 11 && *_Val != 12) {Get_Char(*++_Val);}*_Val = 0;--_Start_ptr;}return *this;}Fast_Istream& Fast_Istream::operator>>(std::string& _Val) {if (_Ok) {char c;Get_Char(c);while (c == 32 || c == 10 || c == 13 || c == 8 || c == 9 || c == 7 ||c == 12 || c == 11) {Get_Char(c);}for (_Val.clear();c != 32 && c != 10 && c && c != -1 && c != 9 && c != 11 && c != 12;Get_Char(c)) {_Val.push_back(c);}--_Start_ptr;}return *this;}template <typename Typex>void Get_Int(Typex& _Val) {if (_Ok) {char ch;bool _F = 0;for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {_F = ch == 45;}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}if (_F) {_Val = ~_Val + 1;}--_Start_ptr;}}template <typename Typex>void Get_Unsigned(Typex& _Val) {if (_Ok) {char ch;Get_Char(ch);while ((ch < 48 || ch > 57) && ch != -1) {Get_Char(ch);}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}--_Start_ptr;}}template <typename Typex>void Get_Double(Typex& _Val) {if(_Ok){char ch;bool _F = 0;for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {_F = ch == 45;}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}if (ch == 46) {unsigned long long _Pow = 1;for (Get_Char(ch); ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val += Typex((ch ^ 48) * 1.0 / (_Pow *= 10));}}if (_F) {_Val = -_Val;}--_Start_ptr;}}Fast_Istream& Fast_Istream::operator>>(bool& _Val) {if(_Ok){char ch;Get_Char(ch);while (ch == 32 || ch == 10 || ch == 13 || ch == 8 || ch == 9 || ch == 7 ||ch == 12 || ch == 11) {Get_Char(ch);}while (ch != 32 && ch != 10 && ch && ch != -1 && ch != 9 && ch != 11 &&ch != 12) {_Val |= ch != 48;Get_Char(ch);}--_Start_ptr;}return *this;}Fast_Istream& Fast_Istream::operator>>(short& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(int& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long long& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned short& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned int& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned long& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned long long& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(float& _Val) {Get_Double(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(double& _Val) {Get_Double(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long double& _Val) {Get_Double(_Val);return *this;}template <typename Typex, typename... More>void Fast_Istream::operator()(Typex& _Val, More&... _More) {*this >> _Val;operator()(_More...);}void Fast_Istream::pop() {char ch;Get_Char(ch);}char Fast_Istream::peek() {if (_Start_ptr == _End_ptr) {_Start_ptr = _Buf;_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);}if (_Start_ptr == _End_ptr) {_Ok = 0;return -1;} else {return *_Start_ptr;}}}
namespace Fast_O {Fast_Ostream::Fast_Ostream(std::streambuf* out, unsigned int Size) {buf.reserve(Size);outbuf = out;}Fast_Ostream::Fast_Ostream(const char* File, unsigned int Size) {buf.reserve(Size);rdbuf(File);}void Fast_Ostream::rdbuf(const char* File) {static std::ofstream __Out__(File);rdbuf(__Out__.rdbuf());}Fast_Ostream::Fast_Ostream(unsigned int Size) {buf.reserve(Size);}void Fast_Ostream::flush() {outbuf->sputn(buf.data(), buf.size());buf.clear();}Fast_Ostream::~Fast_Ostream() {flush();}Fast_Ostream& Fast_Ostream::operator<<(char _Val) {buf.push_back(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(const char* _Val) {while (*_Val) {buf.push_back(*_Val++);}return *this;}Fast_Ostream& Fast_Ostream::operator<<(const std::string& _Val) {for (auto&& i : _Val) {buf.push_back(i);}return *this;}template <typename Typex>void Put_Unsigned(Typex _Val) {char* _Stack = (char*)malloc(sizeof(Typex) * 3);unsigned S_top = 0;while (_Val) {_Stack[++S_top] = (_Val % 10) ^ 48;_Val /= 10;}if (!S_top) {buf.push_back('0');}while (S_top) {buf.push_back(_Stack[S_top--]);}free(_Stack);}void Put_Int(long long _Val) {if (_Val < 0) {buf.push_back('-');Put_Unsigned(~_Val + 1);} else {Put_Unsigned(_Val);}}Fast_Ostream& Fast_Ostream::operator<<(bool _Val) {buf.push_back(_Val ? '1' : '0');return *this;}Fast_Ostream& Fast_Ostream::operator<<(short _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(int _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(long _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(long long _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned short _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned int _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned long _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned long long _Val) {Put_Unsigned(_Val);return *this;}template <typename Typex>void Fast_Ostream::endl(const Typex& _Val) {*this << _Val << '\n';}template <typename Typex, typename... More>void Fast_Ostream::endl(const Typex& _Val, const More&... _More) {*this << _Val;endl(_More...);}template <typename Typex>void Fast_Ostream::operator()(const Typex& _Val) {*this << _Val;}template <typename Typex, typename... More>void Fast_Ostream::operator()(const Typex& _Val, const More&... _More) {*this << _Val;operator()(_More...);}}
#define ull unsigned long long
#define int long long
#define INF (0x66ccff0712ll)
#define N (0x66ccff)
#define M (0x6cf)
#define MAXN (1e6+5)
#define MAXM (1e5+5)
#define lc (q<<1)
#define rc (q<<1|1)
#define cerr std::cerr
#define sort std::stable_sort
#define re register
#define lower_bound std::lower_bound
#define upper_bound std::upper_bound
#define unique std::unique
#define string std::string
#define pair std::pair
#define vector std::vector
#define map std::map
#define set std::set
#define queue std::queue
#define make_pair std::make_pair
#define priority_queue std::priority_queue
#define bitset std::bitset
#define deque std::deque
#define array std::array
#define unordered_set std::unordered_set
#define unordered_map std::unordered_map
#define list std::list
#define it map<int,int>::iterator
#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)<(b)?(b):(a)
#define PII pair<int,int>
#define swap std::swap
// #define debug
const char endl='\n';
const int mod1=998244353,mod2=1e9+7,mod3=1e9+9;
const double PI=acos(-1);
struct Complex{
    double x,y;
    Complex operator+(const Complex&t)const{
        return {x+t.x , y+t.y};
    } 
    Complex operator-(const Complex&t)const{
        return {x-t.x,y-t.y};
    }
    Complex operator*(const Complex&t)const{
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[N],b[N];
int rev[N],bit,tot;
int n,m;
void fft(Complex a[],int inv){
    for(int i=0;i<tot;i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(int mid=1;mid<tot;mid<<=1){
        auto w1=Complex({cos(PI/mid),inv*sin(PI/mid)});
        for(int i=0;i<tot;i+=mid*2){
            auto wk=Complex({1,0});
            for(int j=0;j<mid;j++,wk=wk*w1){
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
}
signed main(){
    // fire();
    cin(n);
    for(int i=0;i<n;i++) cin(a[i].x,b[n-i-1].x);
    while((1<<bit)<n+n+1) bit++;
    tot=1<<bit;
    for(int i=0;i<tot;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,1),fft(b,1);
    for(int i=0;i<tot;i++)
        a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=n-1;i<n+n-1;i++)
        cout((int)(a[i].x/tot+0.5),"\n");
}
所以我 站上这处纷扰的中心
望向这片懵懂的土地 血脉奔涌躁动不已
奏起我的幻想曲

[ZJOI2014]力

求

\[F_j=\sum_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum_{i>j}\frac{q_iq_j}{(i-j)^2} \]

设

\[E_i=\frac{F_i}{q_i} \]

求\(E_i\)

那么

\[E_i = \frac{F_i}{q_i} = \sum_{j=1}^{i-1} \frac{q_j}{(i-j)^2} - \sum_{j=i-1}^{n} \frac{q_j}{(j-i)^2} \]

设一个\(a(x)=\frac{1}{x^2}\)

\[E_i = \sum_{j=1}^{i-1} {q_j}a(i-j) - \sum_{j=i-1}^{n} {q_j}{a(j-i)} \]

和上题有些一样的感觉，前面的可以\(FFT\)，后面的转化一下也可以\(FFT\)

呃呃呃转化同上题

点击查看代码 


#include<bits/stdc++.h>
inline void fire(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);}
namespace Fast_I {char *_Buf, *_Start_ptr, *_End_ptr;std::streambuf* inbuf;unsigned int Size;bool _Ok;struct Fast_Istream {operator bool(){return _Ok; }Fast_Istream(std::streambuf*, unsigned int);Fast_Istream(unsigned int);Fast_Istream(const char*, unsigned int);Fast_Istream& operator>>(char&);Fast_Istream& operator>>(char*);Fast_Istream& operator>>(bool&);Fast_Istream& operator>>(short&);Fast_Istream& operator>>(int&);Fast_Istream& operator>>(long&);Fast_Istream& operator>>(long long&);Fast_Istream& operator>>(unsigned short&);Fast_Istream& operator>>(unsigned int&);Fast_Istream& operator>>(unsigned long&);Fast_Istream& operator>>(unsigned long long&);Fast_Istream& operator>>(float&);Fast_Istream& operator>>(double&);Fast_Istream& operator>>(long double&);Fast_Istream& operator>>(std::string&);template <typename Typex>void operator()(Typex& _Val) { *this >> _Val; }template <typename Typex, typename... More>void operator()(Typex&, More&...);std::streambuf* rdbuf() { return inbuf; }void rdbuf(std::streambuf* _inbuf) { inbuf = _inbuf; }void rdbuf(const char*);void pop();char peek();};}
namespace Fast_O {std::string buf;std::streambuf* outbuf;struct Fast_Ostream {Fast_Ostream(std::streambuf*, unsigned int);Fast_Ostream(std::streambuf* out) { outbuf = out; }Fast_Ostream(const char*, unsigned int);Fast_Ostream(unsigned int);void flush();~Fast_Ostream();void endl() { buf.push_back('\n'); }template <typename Typex>void endl(const Typex& _Val);template <typename Typex, typename... More>void endl(const Typex&, const More&...);template <typename Typex>void operator()(const Typex& _Val);template <typename Typex, typename... More>void operator()(const Typex&, const More&...);Fast_Ostream& operator<<(char);Fast_Ostream& operator<<(const char*);Fast_Ostream& operator<<(const std::string&);Fast_Ostream& operator<<(bool);Fast_Ostream& operator<<(short);Fast_Ostream& operator<<(int);Fast_Ostream& operator<<(long);Fast_Ostream& operator<<(long long);Fast_Ostream& operator<<(unsigned short);Fast_Ostream& operator<<(unsigned int);Fast_Ostream& operator<<(unsigned long);Fast_Ostream& operator<<(unsigned long long);std::streambuf* rdbuf() { return outbuf; }void rdbuf(std::streambuf* _outbuf) { outbuf = _outbuf; }void rdbuf(const char*);};}
namespace Fast_IO {Fast_I::Fast_Istream fin(std::cin.rdbuf(), 1048576);Fast_O::Fast_Ostream fout(std::cout.rdbuf()); }
#define cin Fast_IO::fin
#define cout Fast_IO::fout
namespace Fast_I {Fast_Istream::Fast_Istream(std::streambuf* in, unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;inbuf = in;_Start_ptr = _End_ptr = _Buf = new char[Sz];}Fast_Istream::Fast_Istream(const char* in, unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;rdbuf(in);_Start_ptr = _End_ptr = _Buf = new char[Sz];}Fast_Istream::Fast_Istream(unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;_Start_ptr = _End_ptr = _Buf = new char[Sz];}void Fast_Istream::rdbuf(const char* File) {static std::ifstream __In__(File);rdbuf(__In__.rdbuf());}void Get_Char(char& _Val) {if (_Start_ptr == _End_ptr) {_Start_ptr = _Buf;_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);}if (_Start_ptr == _End_ptr) {_Val = -1;_Ok = 0;} else {_Val = *_Start_ptr++;}}Fast_Istream& Fast_Istream::operator>>(char& _Val) {if(_Ok){Get_Char(_Val);while (_Val == 32 || _Val == 10 || _Val == 13 || _Val == 8 || _Val == 9 || _Val == 7 || _Val == 12 || _Val == 11) {Get_Char(_Val);}}return *this;}Fast_Istream& Fast_Istream::operator>>(char* _Val) {if (_Ok) {Get_Char(*_Val);while (*_Val == 32 || *_Val == 10 || *_Val == 13 || *_Val == 8 ||*_Val == 9 || *_Val == 7 || *_Val == 12 || *_Val == 11) {Get_Char(*_Val);}while (*_Val != 32 && *_Val != 10 && *_Val && *_Val != -1 && *_Val != 9 &&*_Val != 11 && *_Val != 12) {Get_Char(*++_Val);}*_Val = 0;--_Start_ptr;}return *this;}Fast_Istream& Fast_Istream::operator>>(std::string& _Val) {if (_Ok) {char c;Get_Char(c);while (c == 32 || c == 10 || c == 13 || c == 8 || c == 9 || c == 7 ||c == 12 || c == 11) {Get_Char(c);}for (_Val.clear();c != 32 && c != 10 && c && c != -1 && c != 9 && c != 11 && c != 12;Get_Char(c)) {_Val.push_back(c);}--_Start_ptr;}return *this;}template <typename Typex>void Get_Int(Typex& _Val) {if (_Ok) {char ch;bool _F = 0;for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {_F = ch == 45;}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}if (_F) {_Val = ~_Val + 1;}--_Start_ptr;}}template <typename Typex>void Get_Unsigned(Typex& _Val) {if (_Ok) {char ch;Get_Char(ch);while ((ch < 48 || ch > 57) && ch != -1) {Get_Char(ch);}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}--_Start_ptr;}}template <typename Typex>void Get_Double(Typex& _Val) {if(_Ok){char ch;bool _F = 0;for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {_F = ch == 45;}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}if (ch == 46) {unsigned long long _Pow = 1;for (Get_Char(ch); ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val += Typex((ch ^ 48) * 1.0 / (_Pow *= 10));}}if (_F) {_Val = -_Val;}--_Start_ptr;}}Fast_Istream& Fast_Istream::operator>>(bool& _Val) {if(_Ok){char ch;Get_Char(ch);while (ch == 32 || ch == 10 || ch == 13 || ch == 8 || ch == 9 || ch == 7 ||ch == 12 || ch == 11) {Get_Char(ch);}while (ch != 32 && ch != 10 && ch && ch != -1 && ch != 9 && ch != 11 &&ch != 12) {_Val |= ch != 48;Get_Char(ch);}--_Start_ptr;}return *this;}Fast_Istream& Fast_Istream::operator>>(short& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(int& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long long& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned short& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned int& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned long& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned long long& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(float& _Val) {Get_Double(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(double& _Val) {Get_Double(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long double& _Val) {Get_Double(_Val);return *this;}template <typename Typex, typename... More>void Fast_Istream::operator()(Typex& _Val, More&... _More) {*this >> _Val;operator()(_More...);}void Fast_Istream::pop() {char ch;Get_Char(ch);}char Fast_Istream::peek() {if (_Start_ptr == _End_ptr) {_Start_ptr = _Buf;_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);}if (_Start_ptr == _End_ptr) {_Ok = 0;return -1;} else {return *_Start_ptr;}}}
namespace Fast_O {Fast_Ostream::Fast_Ostream(std::streambuf* out, unsigned int Size) {buf.reserve(Size);outbuf = out;}Fast_Ostream::Fast_Ostream(const char* File, unsigned int Size) {buf.reserve(Size);rdbuf(File);}void Fast_Ostream::rdbuf(const char* File) {static std::ofstream __Out__(File);rdbuf(__Out__.rdbuf());}Fast_Ostream::Fast_Ostream(unsigned int Size) {buf.reserve(Size);}void Fast_Ostream::flush() {outbuf->sputn(buf.data(), buf.size());buf.clear();}Fast_Ostream::~Fast_Ostream() {flush();}Fast_Ostream& Fast_Ostream::operator<<(char _Val) {buf.push_back(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(const char* _Val) {while (*_Val) {buf.push_back(*_Val++);}return *this;}Fast_Ostream& Fast_Ostream::operator<<(const std::string& _Val) {for (auto&& i : _Val) {buf.push_back(i);}return *this;}template <typename Typex>void Put_Unsigned(Typex _Val) {char* _Stack = (char*)malloc(sizeof(Typex) * 3);unsigned S_top = 0;while (_Val) {_Stack[++S_top] = (_Val % 10) ^ 48;_Val /= 10;}if (!S_top) {buf.push_back('0');}while (S_top) {buf.push_back(_Stack[S_top--]);}free(_Stack);}void Put_Int(long long _Val) {if (_Val < 0) {buf.push_back('-');Put_Unsigned(~_Val + 1);} else {Put_Unsigned(_Val);}}Fast_Ostream& Fast_Ostream::operator<<(bool _Val) {buf.push_back(_Val ? '1' : '0');return *this;}Fast_Ostream& Fast_Ostream::operator<<(short _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(int _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(long _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(long long _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned short _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned int _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned long _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned long long _Val) {Put_Unsigned(_Val);return *this;}template <typename Typex>void Fast_Ostream::endl(const Typex& _Val) {*this << _Val << '\n';}template <typename Typex, typename... More>void Fast_Ostream::endl(const Typex& _Val, const More&... _More) {*this << _Val;endl(_More...);}template <typename Typex>void Fast_Ostream::operator()(const Typex& _Val) {*this << _Val;}template <typename Typex, typename... More>void Fast_Ostream::operator()(const Typex& _Val, const More&... _More) {*this << _Val;operator()(_More...);}}
#define ull unsigned long long
#define int long long
#define INF (0x66ccff0712ll)
#define N (0x66ccff)
#define M (0x6cf)
#define MAXN (1e6+5)
#define MAXM (1e5+5)
#define lc (q<<1)
#define rc (q<<1|1)
#define cerr std::cerr 
#define sort std::stable_sort
#define re register
#define lower_bound std::lower_bound
#define upper_bound std::upper_bound
#define unique std::unique
#define string std::string
#define pair std::pair
#define vector std::vector
#define map std::map
#define set std::set
#define queue std::queue
#define make_pair std::make_pair
#define priority_queue std::priority_queue
#define bitset std::bitset
#define deque std::deque
#define array std::array
#define unordered_set std::unordered_set
#define unordered_map std::unordered_map
#define list std::list
#define it map<int,int>::iterator
#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)<(b)?(b):(a)
#define PII pair<int,int>
#define swap std::swap
// #define debug
const char endl='\n';
const int mod1=998244353,mod2=1e9+7,mod3=1e9+9;
const double PI=acos(-1);
struct Complex{
    double x,y;
    Complex operator+(const Complex&t)const{
        return {x+t.x , y+t.y};
    } 
    Complex operator-(const Complex&t)const{
        return {x-t.x,y-t.y};
    }
    Complex operator*(const Complex&t)const{
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[N],b[N],c[N];
int rev[N];int bit,tot;
int n,m;double q[N];
void fft(Complex *a,int inv){
    for(int i=0;i<tot;i++)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(int mid=1;mid<tot;mid<<=1){
        auto w1=Complex({cos(PI/mid),inv*sin(PI/mid)});
        for(int i=0;i<tot;i+=mid*2){
            auto wk=Complex({1,0});
            for(int j=0;j<mid;j++,wk=wk*w1){
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y,
                a[i+j+mid]=x-y;
            }
        }
    }
    if(inv==-1)
        for(int i=0;i<tot;i++)
            a[i].x/=tot;
}
signed main(){
    // fire();
    cin(n);
    for(int i=0;i<n;i++)
        cin(q[i]);
    for(int i=0;i<n;i++) 
        a[i].x=(q[i]),
        c[i].x=(q[n-1-i]);
    for(int i=1;i<n;i++) 
        b[i].x=(1.0/i/i);
    while((1<<bit)<2*n) bit++;
    tot=1<<bit;
    for(int i=0;i<tot;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,1),
    fft(b,1),
    fft(c,1);
    for(int i=0;i<tot;i++)
        a[i]=a[i]*b[i];
    for(int i=0;i<tot;i++)
        c[i]=c[i]*b[i];
    fft(a,-1);
    fft(c,-1);
    for(int i=0;i<n;i++)
        printf("%.3f\n",(a[i].x-c[n-i-1].x));
}
耳中灌注我的歌声
眼中弥漫我的全胜
向我表露你的忠诚
犹豫者不等

本来这里应该有一道主席树的题的，但是天依实在太菜了QAQ导致没有在发闲话之前写完

标签：ch,Val,Get,Fast,operator,Istream,幻想曲,奏起,2.1
From： https://www.cnblogs.com/Vsinger-LuoTianYi/p/18001125

相关文章

  • 2.1
    今天写得有点早，主要经历了一些事情。实际上也没什么不正常的。上午先打\(AC\)自动机，确切的说压根没理解是个什么东西，打病毒这道题，因为没理解费解了好长时间，几乎大半个上午，最后发到博客里请各位大佬指教，恍然大悟。挺尴尬的就把博删了。下午继续搞，先把病毒那题\(A\)了，继续......
  • 2.1
    二月第一天！整个emoji里最抽象的字符串：......
  • Dash 2.15版本新特性介绍
    本文示例代码已上传至我的Github仓库https://github.com/CNFeffery/dash-master大家好我是费老师，Dash不久前发布了其2.15.0版本，新增了一些实用的特性，下面我们就来一起get其中的重点......
  • 工作中的网络知识之三802.3和802.11
    工作中的网络知识之三802.3和802.11背景网络知识其实不仅仅有硬件,软件,IP地址性能相关,其实还有一些协议相关的内容.比如wifi或者是4G/5G的网络.所以想着这里再总结一下部分协议相关802协议簇IEEE802系列标准是IEEE802LAN/MAN标准委员会制定的局域网、城域网技术标准。......
  • Python web crawler（2.1）多循环嵌套练习
    写个函数，传入（书名:book，标题:tittle，内容:content），要求在book文件夹下（不存在则创建），创建每个tittle.txt文件，写入content内容importosdefsave_to_file(folder_book,title,content):#如果文件夹不存在，则创建ifnotos.path.exists(folder_book):os.makedirs(......
  • 《数学分析习题课讲义2.1-2.2》
    ......
  • 【常微分方程】2.1.6
    [T020101]设\(f(x)\)满足\(f(x+y)=\frac{f(x)+f(y)}{1-f(x)f(y)}\),且\(f'(0)\)存在,求\(f(x)\)的表达式.解令\(x=y=0\),则\(f(0)=\frac{2f(0)}{1-f(0)^2}\),得\(f(0)=0\).注意到\[f(x+\Deltax)=\frac{f(x)+f(\Deltax)}{1-f(x)f(\Deltax)}\Lo......
  • 工作中的网络知识之三802.3和802.11
    工作中的网络知识之三802.3和802.11背景网络知识其实不仅仅有硬件,软件,IP地址性能相关,其实还有一些协议相关的内容.比如wifi或者是4G/5G的网络.所以想着这里再总结一下部分协议相关802协议簇IEEE802系列标准是IEEE802LAN/MAN标准委员会制定的局域网、城域网技......
  • day39基于阿里云的全面云上业务 - 基于AWS的全面云上业务（12.1-12.2）
    12.1、基于阿里云的全面云上业务（两节）容器服务ACK控制台：https://cs.console.aliyun.com/?spm=5176.12818093_47.categories-n-products.dcsk.60eb16d0N97QLB#/k8s/cluster/list容器服务Kubernetes版产品文档：https://help.aliyun.com/zh/ack/ack-managed-and-ack-dedicated/user-......
  • ROS串口通信报错：IO Exception (13): Permission denied, file /tmp/binarydeb/ros-noe
    ROS在串口通信时，当我们插入USB后，catkin_make之后，报错：IOException(13):Permissiondenied,file/tmp/binarydeb/ros-noetic-serial-1.2.1/src/impl/unix.cc,line151.[ERROR][1705845384.528602780]:Unabletoopenport这是usb权限不够的原因我们首先查看接口设备：l......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99