题意
已知\(a_{i} = \sum_{j=1}^{i} \{^{i} _{j} \}b_{j}\), 给出\(a_{1} 到 a_{n}\) ；
求\(b_{l} 到 b_{r}\)在\(1e9+7\)的意义下取模的值；
\(1 \le l \le r \le n \le 10^5\)
\(r-l \le 100\)
\(0 \le a_{i} \lt 10^9 + 7\)
题解
Part1
斯特林反演（）：
- \(f(n) = \sum_{i=1}^{n} \{^n_i\} g(n) \Longleftrightarrow g(n) = \sum_{i=1}^{n} (-1)^{n-i} [^n_i]f(i)\)
由于\(r-l\)比较小，可以直接暴力求，只需要快速求出\([^n_1] - [^n_n]\)
\([_m^n] = [x^m] x^{\overline n}\) , 其中\(x^{\overline n} = \Pi_{i=1}^n(x+i-1)\)
Part 2
直接做是\(n log ^2n\)的，假设在计算\(F_n(x) = x^{\overline n}\)时已经计算了\(F_\frac{n}{2}(x)\),记\(m = \frac{n}{2} , F_{m} = \sum_{i=0}^{m}a_{i} x^{i}\)
只需要计算\(F'_{m} (x) = F_{m}(x+m)\)和\(F_{m}\)相乘；
\[ F'_m(x) = \sum_{i=0}^{m} a_{i} (x+m)^i \\ = \sum_{i=0}^{m} a _{i}\sum_{j=0}^{i}(^i_j)x^j m^{i-j} \\ = \sum_{i=0}^{m} \sum_{j=0}^{i} a_{i} \frac{i!}{j!(i-j)!}x^{j}m^{i-j} \\ = \sum_{i=0}^{m} \frac{x^i}{i!} \sum_{j=0}^{m-i} a_{i+j}(i+j)! \ \frac{m^{j}}{j!} \]
记$A(x)=\sum_{i=0}^{m} a_{i} i! x^{i}, B(x) = \sum_{i=0}^{m}\frac{m^{i}}{i!} x^{m-i} $
相乘之后取第\(m+i\)项可以算后面的东西
Part 3
可是不是\(ntt\)模数，直接取模会爆\(long \ long\)需要用到拆系数\(ntt\);
将\(A(x)*B(x)\)分解成\((k * A1(x) + A2(x)) * (k * B1(x) + B2(x)) , k 一般取\sqrt{n} (2^{15} ) 左右\)
暴力是7次\(fft\)，可以优化到需要4次\(fft\)
两次\(fft\)合并成一次的做法，需要计算\(dft(A(x))和dft(B(x))\)
记： \[\begin{align} P(x) = A(x) + iB(x)\\ Q(x) = A(x) -iB(x) \end{align}\]
考虑直接做\(P\)为\(P’\),考虑\(Q \ dft\)之后的结果\(Q'\)
\[ \begin{align} Q'[k] &= A(w_{n}^{k}) - iB(w_{n}^{k}) \\ &= \sum_{j=0}^{n-1} (a_{j}-ib_{j})w^{jk}_{n} \\ &= \sum_{j=0}^{n-1}(a_{j}-ib_{j})(cos(\frac{2\pi jk}{n} ) + isin(\frac{2\pi jk}{n}) ) \\ &= \sum_{j=0}^{n-1}(a_{j}cos(\frac{2\pi jk}{n}) + b_{j}sin(\frac{2\pi jk}{n}))- i(b_{j}cos(\frac{2\pi jk}{n}) - a_{j}sin(\frac{2\pi jk}{n})) \\ &= conj \sum_{j=0}^{n-1} (a_{j}cos(\frac{-2\pi jk}{n}) - b_{j}sin(\frac{-2\pi jk}{n} ) ) +i( b_{j}cos(\frac{-2\pi jk}{n}) + a_{j}sin(\frac{-2\pi jk}{n})) \\ &= conj \sum_{j=0}^{n-1} (a_{j}+ib_{j})(cos(\frac{-2\pi jk}{n})+isin(\frac{-2\pi jk}{n})) \\ &= conj \ \sum_{j=0}^{n-1} (a_{j}+ib_{j})w^{-jk}_{n} \\ &= conj \ P'[n-k] \end{align} \]
所以由\(P'\)直接得到\(Q'\):
即：\[ \begin{align} A'(x) = \frac{P'(x) + Q'(x)}{2} \\ B'(x) = \frac{P'(x) - Q'(x)}{2i}\end{align} g \]
结果也存在实部和虚部里直接\(idft\)回去就好了；
注意精度；
#include
#define ld long double#define ll long long using namespace std;const int N=400010,mod=1e9+7;const ld pi=acos(-1);int n,l,r,rev[N],fac[N],inv[N],p[N],a[N],b[N];char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++;}int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x;}int pw(int x,int y){ int re=1; while(y){ if(y&1)re=(ll)re*x%mod; y>>=1,x=(ll)x*x%mod; } return re;}struct C{ ld x,y; C(ld _x=0,ld _y=0):x(_x),y(_y){}; C operator +(const C&A)const{return C(x+A.x,y+A.y);} C operator -(const C&A)const{return C(x-A.x,y-A.y);} C operator *(const C&A)const{return C(x*A.x-y*A.y,x*A.y+y*A.x);} C operator /(const ld&A)const{return C(x/A,y/A);} C operator !()const{return C(x,-y);}};void fft(C*A,int len,int f){ for(int i=0;i