营销网站开发找哪家,360网站建设企业,旅游网站国内外研究现状,网站维护 静态页面正题
题目链接:https://ac.nowcoder.com/acm/contest/186/D 题目大意 mmm个二元组(ai,bi)(a_i,b_i)(ai,bi)#xff0c;对于一个序列xxx的贡献是∏i1n(aixi2bixi1)\prod_{i1}^n(a_ix_i^2b_ix_i1)i1∏n(aixi2bixi1) qqq次询问给出nnn求在xi≥0x_i\geq 0xi≥0且…正题
题目链接:https://ac.nowcoder.com/acm/contest/186/D 题目大意
mmm个二元组(ai,bi)(a_i,b_i)(ai,bi)对于一个序列xxx的贡献是∏i1n(aixi2bixi1)\prod_{i1}^n(a_ix_i^2b_ix_i1)i1∏n(aixi2bixi1) qqq次询问给出nnn求在xi≥0x_i\geq 0xi≥0且∑i1nxin\sum_{i1}^nx_in∑i1nxin时的情况下所有序列的贡献和。 解题思路
dpdpdp思路
先列出简单的dpdpdp方程fi,j∑k0jfi,j−k∗(aik2bik1)f_{i,j}\sum_{k0}^jf_{i,j-k}*(a_ik^2b_ik1)fi,jk0∑jfi,j−k∗(aik2bik1)
然后发现这个每次转移时加的值是∑k0jfi,j−k∗(2aikaibi)\sum_{k0}^jf_{i,j-k}*(2a_ika_ib_i)k0∑jfi,j−k∗(2aikaibi) 然后这个加的值每次转移时加的值是∑k0jfi,j−k∗2ai\sum_{k0}^jf_{i,j-k}*2a_ik0∑jfi,j−k∗2ai 开几个差分变量统计即可。 时间复杂度O(nmq)O(nmq)O(nmq)
OGFOGFOGF思路
阿巴阿巴这个我一点都不会大部分都是靠幂炜大爷的指点的
每个物品是一个∑i≥0xi(ai2bi1)\sum_{i\geq 0}x^i(ai^2bi1)∑i≥0xi(ai2bi1)的一个生成函数然后化一下 a∑i≥0xii2b∑i≥0xii∑i≥0xia\sum_{i\geq 0}x^ii^2b\sum_{i\geq 0}x^ii\sum_{i\geq 0}x^iai≥0∑xii2bi≥0∑xiii≥0∑xi 最后一个是11−x\frac{1}{1-x}1−x1就不多解释了化一下前面两个 S∑i≥0xii2,xS∑i≥1xi1i2S\sum_{i\geq 0}x^ii^2,xS\sum_{i\geq 1}x^{i1}i^2Si≥0∑xii2,xSi≥1∑xi1i2 (1−x)S∑i≥1xi(i2−(i−1)2)2∗∑i≥1xii−∑i≥0xi(1-x)S\sum_{i\geq 1}x^{i}(\ i^2-(i-1)^2\ )2*\sum_{i\geq 1}x^i i-\sum_{i\geq 0}x^i(1−x)Si≥1∑xi( i2−(i−1)2 )2∗i≥1∑xii−i≥0∑xi 然后前面那个我们同理T∑i≥0xii,xT∑i≥1xi1iT\sum_{i\geq 0}x^ii,xT\sum_{i\geq 1}x^{i1}iTi≥0∑xii,xTi≥1∑xi1i (1−x)T∑i≥1xix1−x,Tx(1−x)2(1-x)T\sum_{i\geq 1}x^{i}\frac{x}{1-x},T\frac{x}{(1-x)^2}(1−x)Ti≥1∑xi1−xx,T(1−x)2x 代回去 (1−x)S2x(1−x)2−x(1−x)2x−x(1−x)(1−x)2x(x1)(1−x)2(1-x)S\frac{2x}{(1-x)^2}-\frac{x}{(1-x)}\frac{2x-x(1-x)}{(1-x)^2}\frac{x(x1)}{(1-x)^2}(1−x)S(1−x)22x−(1−x)x(1−x)22x−x(1−x)(1−x)2x(x1) S∑i≥0xii2x(x1)(1−x)3,∑i≥0xii1(1−x)2S\sum_{i\geq 0}x^ii^2\frac{x(x1)}{(1-x)^3}\ \ ,\ \ \ \sum_{i\geq 0}x_ii\frac{1}{(1-x)^2}Si≥0∑xii2(1−x)3x(x1) , i≥0∑xii(1−x)21 之前那个式子就可以变成 ax(x1)(1−x)3bx(1−x)211−x\frac{ax(x1)}{(1-x)^3}\frac{bx}{(1-x)^2}\frac{1}{1-x}(1−x)3ax(x1)(1−x)2bx1−x1 然后展开就成了 1(ab−2)x(a−b1)x2(1−x)3\frac {1(ab-2)x(a-b1)x^2}{(1-x)^{3}}(1−x)31(ab−2)x(a−b1)x2 然后所有的乘起来因为只有三个系数所以可以暴力乘。
答案就是乘积的生成函数中xnx^nxn的系数考虑如何求。
我们已经处理出了一个fff数组∑j≥0xifi(1−x)3m\frac{\sum_{j\geq 0}x^if_i}{(1-x)^{3m}}(1−x)3m∑j≥0xifi有 1(1−x)k(∑i≥0xi)k∑i≥0xi(ki−1i−1)\frac{1}{(1-x)^k}(\sum_{i\geq 0}x^i)^k\sum_{i\geq 0}x^i\binom{ki-1}{i-1}(1−x)k1(i≥0∑xi)ki≥0∑xi(i−1ki−1) ∑j≥0xifi(1−x)3m∑j≥0xifi∗∑i≥0xi(3mi−1i−1)\frac{\sum_{j\geq 0}x^if_i}{(1-x)^{3m}}\sum_{j\geq 0}x^if_i*\sum_{i\geq 0}x^i\binom{3mi-1}{i-1}(1−x)3m∑j≥0xifij≥0∑xifi∗i≥0∑xi(i−13mi−1) 然后就可以卷积了xnx_nxn的系数就是 ∑i0nfn−i(3mi−1i−1)\sum_{i0}^nf_{n-i}\binom{3mi-1}{i-1}i0∑nfn−i(i−13mi−1)
时间复杂度O((qm)n)O(\ (qm)n\ )O( (qm)n ) codecodecode
dpcodedp\ \ codedp code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1100,XJQ998244353;
ll m,q,n,a[N],b[N],f[N][11000];
int main()
{scanf(%lld,m);f[0][0]1;for(ll i1;im;i){scanf(%lld%lld,a[i],b[i]);ll tmp10,tmp20,tmp30,sum0;for(ll j0;j1e4;j){sum(sumtmp2tmp3f[i-1][j])%XJQ;f[i][j]sum;tmp2(tmp2tmp1)%XJQ;tmp1(tmp12*f[i-1][j]%XJQ*a[i]%XJQ)%XJQ;tmp3(tmp3(b[i]a[i])*f[i-1][j])%XJQ;}}scanf(%lld,q);while(q--){scanf(%lld,n);printf(%lld\n,f[m][n]);}return 0;
}OGFcodeOGF\ \ codeOGF code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e410,P998244353;
ll n,m,q,tot,fac[N],inv[N],f[N];
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
int main()
{scanf(%lld,m);inv[1]f[0]fac[0]inv[0]1;for(ll i2;i4e4;i)inv[i](P-P/i)*inv[P%i]%P;for(ll i1;i4e4;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P; for(ll i1;im;i){ll a,b;scanf(%lld%lld,a,b);ll A(a-b1P)%P,B(ab-2P)%P;tot3;for(ll j1e4;j0;j--){if(j1)(f[j]f[j-2]*A%P)%P;if(j0)(f[j]f[j-1]*B%P)%P;}}scanf(%lld,q);while(q--){scanf(%lld,n);ll ans0;for(ll i0;in;i)(ansC(itot-1,tot-1)*f[n-i]%P)%P;printf(%lld\n,ans);}return 0;
}
