有哪些做的比较精美的网站,做外贸用什么网站比较好,域名备案和网站备案的区别,腕表之家网站正题
题目链接:https://www.luogu.com.cn/problem/P5488 题目大意
求一个长度为nnn的序列的kkk阶差分/前缀和。 解题思路
先考虑前缀和怎么做 搞出来生成函数就是(∑i0naixi)∗(∑i0∞xi)k(\sum_{i0}^na_ix^i)*(\sum_{i0}^{\infty}x^i)^k(i0∑naixi)∗(i0∑∞xi)k
然…正题
题目链接:https://www.luogu.com.cn/problem/P5488 题目大意
求一个长度为nnn的序列的kkk阶差分/前缀和。 解题思路
先考虑前缀和怎么做 搞出来生成函数就是(∑i0naixi)∗(∑i0∞xi)k(\sum_{i0}^na_ix^i)*(\sum_{i0}^{\infty}x^i)^k(i0∑naixi)∗(i0∑∞xi)k
然后根据常识我们知道(∑i0∞xi)k∑i0∞(ik−1i)xi(\sum_{i0}^{\infty}x^i)^k\sum_{i0}^{\infty}\binom{ik-1}{i}x^i(∑i0∞xi)k∑i0∞(iik−1)xi当然也可以理解为xix^ixi的系数就是每次会往后跳任意格可以是000然后kkk次跳iii步的方案数。
之后式子(∑i0naixi)∗(∑i0∞(ik−1i)xi)(\sum_{i0}^na_ix^i)*(\sum_{i0}^{\infty}\binom{ik-1}{i}x^i)(i0∑naixi)∗(i0∑∞(iik−1)xi)
直接卷就好了
然后是差分就是∑i0naixi(∑i0∞xi)k\frac{\sum_{i0}^na_ix^i}{(\sum_{i0}^{\infty}x^i)^k}(∑i0∞xi)k∑i0naixi 直接上多项式除法就好 。考虑怎么转换这个式子我们需要用生成函数的方法了上等比数列公式就有(∑i0∞xi)k1(1−x)k(\sum_{i0}^{\infty}x^i)^k\frac{1}{(1-x)^k}(∑i0∞xi)k(1−x)k1
那么它的倒数就是(1−x)k(1-x)^k(1−x)k上二项式定理就有∑i0k(−1)i(ki)xi\sum_{i0}^k(-1)^i\binom{k}{i}x^i∑i0k(−1)i(ik)xi
然后也是两个式子卷起来就好了。
然后kkk可以直接模ppp考虑f(k)(∑i0∞xi)kf(k)(\sum_{i0}^\infty x^i)^kf(k)(∑i0∞xi)k那么有f(kn)f(k)nf(k^n)f(k)^nf(kn)f(k)n所以直接让kkk模ppp即可
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includealgorithm
#includecstring
#define ll long long
using namespace std;
const ll N(1e5)*6,P1004535809,g3;
struct poly{ll a[N],n;
}G,F;
ll n,k,t,inv[N],r[N];
char s[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void NTT(ll *f,ll op,ll n){for(ll i0;in;i)if(r[i]i)swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll len(p1);ll tmppower(g,(P-1)/p);if(op)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[ilen]%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op){int invnpower(n,P-2);for(int i0;in;i)f[i]f[i]*invn%P;}return;
}
void mul(poly a,poly b){ll n1;while(na.nb.n)n1;for(ll i0;in;i)r[i](r[i1]1)^((i1)?(n1):0);NTT(a.a,0,n);NTT(b.a,0,n);for(ll i0;in;i)a.a[i]a.a[i]*b.a[i]%P;NTT(a.a,1,n);return;
}
int main()
{scanf(%lld,n);scanf(%s,s);ll lstrlen(s);scanf(%lld,t);for(ll i0;il;i)k(k*10s[i]-0)%P;inv[1]1;for(ll i2;in;i)inv[i](P-(P/i)*inv[P%i]%P)%P;for(ll i0;in;i)scanf(%lld,F.a[i]);G.a[0]1;for(ll i1;in;i){if(!t)G.a[i]G.a[i-1]*(ik-1)%P*inv[i]%P;else{if(ik)break;G.a[i](-1)*G.a[i-1]*(k-i1)%P*inv[i]%P;G.a[i](G.a[i]P)%P;}}G.nF.nn;mul(G,F);for(ll i0;in;i)printf(%lld ,G.a[i]);return 0;
}
