传奇网站发布网,外贸型网站,贵州省住房和城乡建设厅网站报名网,优化是什么意思网络用语前言
刚开始看错题推了半天的生成函数 正题
题目链接:https://www.luogu.com.cn/problem/CF1251F 题目大意 nnn个白色木板#xff0c;kkk个红色木板#xff0c;给出这些木板的高度#xff0c;木板排成一排形成栅栏。栅栏要求只有一个红色木板且在红色木板左边单调升…前言
刚开始看错题推了半天的生成函数 正题
题目链接:https://www.luogu.com.cn/problem/CF1251F 题目大意
nnn个白色木板kkk个红色木板给出这些木板的高度木板排成一排形成栅栏。栅栏要求只有一个红色木板且在红色木板左边单调升右边单调降。
mmm次询问能够围成周长为qiq_iqi有多少种围法。 解题思路
首先如果栅栏多余两个可以看做是两个因为同一个高度的栅栏最多只能出现两次而木板相同。
因为kkk很小显然是要我们处理kkk次现在分开考虑出现两次的和出现一次的方案。若出现一次的栅栏有xxx个拿出kkk围个的方案数就是(xk)∗2k\binom{x}{k}*2^k(kx)∗2k若出现两次的栅栏有yyy个拿出kkk个围的方案数就是(k2x)\binom{k}{2x}(2xk)
然后两种方案卷起来就可以计算答案了。
时间复杂度O(k(nlognm))O(\ k(n\log nm)\ )O( k(nlognm) ) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N(12*1e5)10,P998244353;
struct poly{ll a[N],n;
}F,G;
ll n,m,t,f1,f2,r[N],a[N],v[N],b[N],f[N],pw[N],fac[N],inv[N],q[N],ans[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 n,ll op){for(ll i0;in;i)if(r[i]i)swap(f[r[i]],f[i]);for(ll p2;pn;p1){ll lenp1;ll tmppower(3,(P-1)/p);if(op-1)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttf[ilen]*buf%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(n,P-2);for(ll 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,n,1);NTT(b.a,n,1);for(ll i0;in;i)a.a[i]a.a[i]*b.a[i]%P;NTT(a.a,n,-1);return;
}
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lld,a[i]);fac[0]pw[0]inv[0]1;for(ll i1;i4*n;i)fac[i]fac[i-1]*i%P,pw[i]pw[i-1]*2%P;inv[4*n]power(fac[4*n],P-2);for(ll i4*n;i1;i--)inv[i-1]inv[i]*i%P;for(ll i1;im;i)scanf(%lld,b[i]);sort(b1,b1m);scanf(%lld,t);for(ll i1;it;i)scanf(%lld,q[i]);sort(a1,a1n);ll l1;for(ll k1;km;k){while(lna[l]b[k]){if(!v[a[l]])f1;else if(v[a[l]]1)f1--,f2;v[a[l]];l;}memset(G.a,0,sizeof(G.a));memset(F.a,0,sizeof(F.a));for(ll i0;if1;i)G.a[i]pw[i]*C(f1,i)%P;G.nf11;for(ll i0;i2*f2;i)F.a[i]C(2*f2,i);F.n2*f21;mul(G,F);for(ll i1;it;i)if(q[i]b[k]*22)ans[i](ans[i]G.a[q[i]/2-b[k]-1])%P;}for(ll i1;it;i)printf(%lld\n,ans[i]);return 0;
}
