大连三合一网站制作,diy,wordpress泛域名解析,wordpress最简单主题正题
题目链接:https://www.luogu.com.cn/problem/P4351 题目大意 n∗nn*nn∗n的矩形#xff0c;给出第一行和第一列的数#xff0c;剩下的满足Fi,ja∗Fi,j−1b∗Fi−1,jcF_{i,j}a*F_{i,j-1}b*F_{i-1,j}cFi,ja∗Fi,j−1b∗Fi−1,jc
求Fn,nF_{n,n}Fn,n 解题思路
第…正题
题目链接:https://www.luogu.com.cn/problem/P4351 题目大意
n∗nn*nn∗n的矩形给出第一行和第一列的数剩下的满足Fi,ja∗Fi,j−1b∗Fi−1,jcF_{i,j}a*F_{i,j-1}b*F_{i-1,j}cFi,ja∗Fi,j−1b∗Fi−1,jc
求Fn,nF_{n,n}Fn,n 解题思路
第一眼看以为是水题因为给出的数字的贡献通过组合数很好算但是后来发现麻烦的是那个ccc。我们考虑每个格子的ccc产生的贡献。
下面为了方便我们先默认让所有格子横纵坐标减111 对于一个格子(i,j)(i,j)(i,j)通过它的路径有(2n−i−jn−i)\binom{2n-i-j}{n-i}(n−i2n−i−j)种然后产生的贡献是an−ibn−ja^{n-i}b^{n-j}an−ibn−j。为了方便我们反过来表示然后因为第一行第一列没有贡献所以nnn减一。 那么总共的贡献就是∑i0n∑j0naibi(iji)\sum_{i0}^n\sum_{j0}^na^ib^i\binom{ij}{i}i0∑nj0∑naibi(iij) 然后因为有ijijij很麻烦考虑枚举ijijij就有 ∑i02n∑jmax{0,i−n}min{i,n}ajbi−j(ij)!j!(i−j)!\sum_{i0}^{2n}\sum_{jmax\{0,i-n\}}^{min\{i,n\}}a^jb^{i-j}\frac{(ij)!}{j!(i-j)!}i0∑2njmax{0,i−n}∑min{i,n}ajbi−jj!(i−j)!(ij)! 把(ij)!(ij)!(ij)!拿出去就是一个卷积的形式了模数比较丑所以要用MTTMTTMTT来做。除了MTTMTTMTT部分全部自己推。
记得要预处理单位根不然会被卡精度时间复杂度O(nlogn)O(n\log n)O(nlogn)常数巨大
好像有更简单的做法就是用一个xxx满足axbxcxaxbxcxaxbxcx的来消掉ccc这个元就可以直接做了但是我不会。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long long
using namespace std;
const double Piacos(-1);
const ll N2e610,P1e63;
ll n,a,b,c,ans,F[N],H[N],G[N];
ll inv[N],fac[N],r[N],apw[N],bpw[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
namespace Poly{const ll seq32768;struct complex{double x,y;complex(double xx0,double yy0){xxx;yyy;}}A[N],B[N],C[N],D[N],w[N];complex operator(complex a,complex b){return complex(a.xb.x,a.yb.y);}complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x);}void FFT(complex *f,ll n,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1;for(ll k0;kn;kp){for(ll ik;iklen;i){complex tmpw[n/len*(i-k)];if(op-1)tmp.y-tmp.y;complex ttf[ilen]*tmp;f[ilen]f[i]-tt;f[i]f[i]tt;}}}if(op-1){for(ll i0;in;i)f[i].xfabs(f[i].x/n0.5);}return;}void MTT(ll *a,ll *b,ll *c,ll n,ll m){ll l1;while(lnm)l1;for(ll i0;il;i)r[i](r[i1]1)|((i1)?(l1):0);for (ll k1;kl;k1)for (ll i0;ik;i)w[l/k*i](complex){cos(i*Pi/k),sin(i*Pi/k)};for(ll i0;in;i)A[i].xa[i]/seq,B[i].xa[i]%seq;for(ll i0;im;i)C[i].xb[i]/seq,D[i].xb[i]%seq;FFT(A,l,1);FFT(B,l,1);FFT(C,l,1);FFT(D,l,1);complex t1,t2;for(ll i0;il;i){t1A[i]*C[i];t2B[i]*D[i];B[i]A[i]*D[i]B[i]*C[i];A[i]t1;C[i]t2;}FFT(A,l,-1);FFT(B,l,-1);FFT(C,l,-1);for(ll i0;il;i){c[i](c[i](ll)(A[i].x)*seq%P*seq%P)%P;c[i](c[i](ll)(B[i].x)*seq%P)%P;c[i](c[i](ll)(C[i].x))%P;}return;}
}
void init(){inv[1]1;apw[0]bpw[0]1;for(ll i1;i2*n;i)apw[i]apw[i-1]*a%P,bpw[i]bpw[i-1]*b%P;for(ll i2;i2*n;i)inv[i](P-(P/i)*inv[P%i]%P)%P;inv[0]fac[0]1;for(ll i1;i2*n;i){fac[i]fac[i-1]*i%P;inv[i]inv[i-1]*inv[i]%P;}
}
signed main()
{scanf(%lld%lld%lld%lld,n,a,b,c);init();n--;for(ll i0;in;i){ll x;scanf(%lld,x);if(!i)continue;xx*bpw[n-i]%P*apw[n]%P;(ansx*C(nn-i-1,n-1)%P)%P;}for(ll i0;in;i){ll x;scanf(%lld,x);if(!i)continue;xx*apw[n-i]%P*bpw[n]%P;(ansx*C(nn-i-1,n-1)%P)%P;}//处理已知数列for(ll i0;in;i){F[i]apw[i]*inv[i]%P;H[i]bpw[i]*inv[i]%P;}Poly::MTT(F,H,G,n,n);for(ll i0;i2*n-1;i)(ansG[i]*c%P*fac[i]%P)%P;
// for(ll i0;in;i){
// (ansP-apw[n-i]*bpw[n]%P*c%P*C(nn-i,n)%P)%P;
// if(!i)continue;
// (ansP-bpw[n-i]*apw[n]%P*c%P*C(nn-i,n)%P)%P;
// }printf(%lld\n,ans);return 0;
}
