网站建设招标流程图,辽宁网站建设招标,网页设计策划书ppt,新闻wordpress主题题目大意定义一个$S-$四面体表示六条边由$S$根不同的木棍组成#xff0c;定义一种染色方法合法当且仅当至少有$S$根木棍被染色且与每个顶点相邻的三根木棍中至多有一根被染色#xff0c;求有$N$个$S1,2...N$四面体#xff0c;求至少染$K$个的方案数。 题解 单独考虑$S1$四面… 题目大意定义一个$S-$四面体表示六条边由$S$根不同的木棍组成定义一种染色方法合法当且仅当至少有$S$根木棍被染色且与每个顶点相邻的三根木棍中至多有一根被染色求有$N$个$S1,2...N$四面体求至少染$K$个的方案数。 题解 单独考虑$S1$四面体染它有$9$中方案否则将与每个顶点相邻的$12$条边单独拿出来计算。 考虑其余四面体被染色的方案数他们中有$k$个顶点$(k0,1,2,3,4)$相邻的木棍三条中有一条被染色方案是$C_4^k\times 3^k$剩余的边则有$\sum\limits_{iS-k}^{6S-12}C_{6S-12}^{i}$用乘法原理乘一下即可。 由于$k$很小可以只求$\sum\limits_{iS}^{6S-12}C_{6S-12}^{i}$其余加上组合数即可。而这个式子是杨辉三角上的某一行的一个后缀所以是可以递推的考虑上一行答案对下一行答案的贡献只需要乘二再加上上一行后缀左侧的那个组合数即可。 我们现在已经解决了每一个$S$的方案数接下来就是求染出至少$K$个的方案数也只需要递推设$G_x$表示染$x$个的方案数$V$表示当染前四边形的方案数$G_xG_xV\times G_{x-1}$。这是$N$个简单最高次项次数是一次的多项式的卷积用分治$FFT$解决即可。 有两个细节由于模数只有$10^53$所以算组合数要用$lucas$定理。并且$FFT$中每一位可能达到$10^{15}$级别精度可能会爆炸所以要优化或者使用$long\space double$。 #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
#define LL long long
#define LD long double
#define mod 100003
#define M 100020
using namespace std;
int read(){int nm0,fh1; int cwgetchar();for(;!isdigit(cw);cwgetchar()) if(cw-) fh-fh;for(;isdigit(cw);cwgetchar()) nmnm*10(cw-0);return nm*fh;
}
const int P[]{1,12,54,108,81};
const LD PI3.141592653589793238462643383;
int mul(int x,int y){return (LL)x*(LL)y%mod;}
int add(int x,int y){return (xy)mod?xy-mod:xy;}
int mus(int x,int y){return (x-y)0?x-ymod:x-y;}
void upd(int x,int y){xadd(x,y);}
int qpow(int x,int sq){int res1;for(;sq;sq1,xmul(x,x)) if(sq1) resmul(res,x);return res;
}
int n,m,fac[mod],ifac[mod],G[M2],lg[M2];
int C(int tot,int tk){if(tot0||tk0||tottk)return 0;return mul(fac[tot],mul(ifac[tot-tk],ifac[tk]));}
int lucas(int tot,int tk){if(!tk) return 1;return mul(C(tot%mod,tk%mod),lucas(tot/mod,tk/mod));}
int rev[M2],F[M2],S[M];
struct comp{LD r,d; comp(){rd0.0;}comp(LD _r,LD _d){r_r,d_d;}comp operator (const compk)const{return comp(rk.r,dk.d);}comp operator -(const compk)const{return comp(r-k.r,d-k.d);}comp operator *(const compk)const{return comp(r*k.r-d*k.d,r*k.dd*k.r);}
}A[M2],B[M2];
void FFT(comp *x,int len,LD kd){for(int i1;ilen;i) if(irev[i]) swap(x[i],x[rev[i]]);for(int tt1;ttlen;tt1){comp unit(cos(PI*kd/(tt*1.0)),sin(PI*kd/(tt*1.0)));for(int st0;stlen;st(tt1)){comp now(1.0,0.0);for(int posst;possttt;pos,nownow*unit){comp t1x[pos],t2x[postt]*now;x[pos]t1t2,x[postt]t1-t2;}}}if(kd0.0){for(int i0;ilen;i) x[i].r/(len*1.0);}
}
void tms(int *x,int *x1,int *x2,int n1,int n2){if(n1n2120){memset(S,0,sizeof(int)*(n1n21));for(int i0;in1;i){for(int j0;jn2;j) S[ij]mul(x1[i],x2[j]);}for(int i0;in1n2;i) x[i]S[i]%mod;}else{int len1,nw-1;for(;lenn1n21;len1,nw);for(int i1;ilen;i) rev[i](rev[i1]1)|((i1)nw);for(int i0;in1;i) A[i]comp(x1[i]*1.0,0.0);for(int i0;in2;i) B[i]comp(x2[i]*1.0,0.0);for(int in11;ilen;i) A[i]comp(0.0,0.0);for(int in21;ilen;i) B[i]comp(0.0,0.0);FFT(A,len,1.0),FFT(B,len,1.0);for(int i0;ilen;i) A[i]A[i]*B[i]; FFT(A,len,-1.0);for(int i0;in1n2;i) x[i]llround(A[i].r)%mod;}
}
void solve(int *x,int L,int R){if(LR){x[0]1,x[1]G[L];return;}int mid((LR)1),ls,rs; lsmid-L1,rsR-mid;solve(x,L,mid),solve(xls1,mid1,R);tms(x,x,xls1,ls,rs);
}
int main(){fac[0]ifac[0]1,G[1]9,G[2]243,G[3]16224,G[4]46489;for(int i1;imod;i) fac[i]mul(fac[i-1],i),ifac[i]qpow(fac[i],mod-2);for(int i5,K,pre,last3797,rem;iM;i){for(K(i-2)*6,preK-6;preK;pre) lastadd(add(last,last),lucas(pre,i-2));lastmus(last,lucas(K,i-1)),remlast;for(int k0;k4;k) upd(G[i],mul(P[k],rem)),upd(rem,lucas(K,i-k-1));}for(int Tread(),ans0;T;--T,ans0){nread(),mread(),solve(F,1,n);for(int in;im;i--) upd(ans,F[i]);printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/OYJason/p/9751387.html
