P25195. 夜夜夜夜原题链接P25195 夜夜夜夜分析不妨排个序然后慢慢枚举吗我们以排序之后x xx不妨记其出现次数为c n t cntcnt出现的最后一次的位置不妨记为p o s pospos来计算……差不多这个意思吧然后我们进行一些枚举即我们假定长度为l e n lenlen当l e n lenlen的长度为奇数的时候我们的答案就是C p o s − 1 l e n − 1 2 × C n − p o s l e n − 1 2 C_{pos-1}^{\frac{len-1}{2}}\times C_{n-pos}^{\frac{len-1}{2}}Cpos−12len−1​​×Cn−pos2len−1​​。当l e n lenlen的长度为奇数的时候答案是C c n t − 1 1 × C p o s − c n t l e n − 2 2 × C n − p o s l e n − 2 2 C_{cnt-1}^{1}\times C_{pos-cnt}^{\frac{len-2}{2}}\times C_{n-pos}^{\frac{len-2}{2}}Ccnt−11​×Cpos−cnt2len−2​​×Cn−pos2len−2​​。果真如此吗并非只按照最后一次出现是错误的。对于奇数我们贡献实为∑ a i x C n − 1 i − 1 \sum\limits_{a_ix}C_{n-1}^{i-1}ai​x∑​Cn−1i−1​对于偶数枚举i ii只考虑a i ≤ x a_i\le xai​≤x令v a i va_ivai​需要w 2 x − v w2x-vw2x−v。若v x vxvx设w ww区间为[ l , r ] [l,r][l,r]贡献为C n i − l i − C n i − r − 1 i C_{ni-l}^{i}-C_{ni-r-1}^{i}Cni−li​−Cni−r−1i​。若v x vxvx若x xx最右端的点为R RR贡献为C n − 1 i − C n i − R − 1 i C_{n-1}^i-C_{ni-R-1}^{i}Cn−1i​−Cni−R−1i​。就是一个范德蒙德卷积。正解#includebits/stdc.h#defineintlonglong#definemod998244353usingnamespacestd;constintN2000005;intn,x;inta[N];intfac[N],inv[N];intqpow(inta,intb){intres1;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}intC(intn,intm){if(n0||m0||mn)return0;returnfac[n]*inv[m]%mod*inv[n-m]%mod;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnx;for(inti1;in;i){cina[i];}sort(a1,an1);fac[0]1;for(inti1;iN;i){fac[i]fac[i-1]*i%mod;}inv[N-1]qpow(fac[N-1],mod-2);for(intiN-2;i0;i--){inv[i]inv[i1]*(i1)%mod;}mapint,intl,r;for(inti1;in;i){if(l.find(a[i])l.end()){l[a[i]]i;}r[a[i]]i;}intans0;if(l.find(x)!l.end()){intlbl[x],rbr[x];for(intilb;irb;i){ans(ansC(n-1,i-1))%mod;}}for(inti1;in;i){if(a[i]x)break;intva[i];if(vx){intw2*x-v;if(l.find(w)!l.end()){intlbl[w],rbr[w];ans(ansC(ni-lb,i)-C(ni-rb-1,i)mod)%mod;}}elseif(vx){if(l.find(x)!l.end()){intrbr[x];ans(ansC(n-1,i)-C(ni-rb-1,i)mod)%mod;}}}coutans;}C9255 飞飞的树原题链接C9255 飞飞的树分析不是哥们……其实不是特别难吧……原题是棒棒糖。正解#includebits/stdc.h#defineintlonglong#definemod998244353usingnamespacestd;constintN1000005;intn,m;vectorinte[N];intpw[N];intf[N][25],de[N];intfac[N],inv[N];intqpow(inta,intb){intres1;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}voiddfs(intu,intfa){f[u][0]fa;de[u]de[fa]1;for(autov:e[u]){if(vfa)continue;dfs(v,u);}}intLCA(intx,inty){if(de[x]de[y])swap(x,y);intdeltade[x]-de[y];for(inti20;i0;i--){if(delta(1i)){xf[x][i];}}if(xy)returny;for(inti20;i0;i--){if(f[x][i]!f[y][i]){xf[x][i];yf[y][i];}}returnf[x][0];}intC(intn,intm){if(n0||m0||mn)return0;returnfac[n]*inv[n-m]%mod*inv[m]%mod;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;cinm;for(inti1,u,v;in;i){cinu;vi1;// cin u v;e[u].push_back(v);e[v].push_back(u);}pw[0]1;fac[0]1;for(inti1;iN;i){pw[i]pw[i-1]*2%mod;fac[i]fac[i-1]*i%mod;}inv[N-1]qpow(fac[N-1],mod-2);for(intiN-2;i0;i--){inv[i]inv[i1]*(i1)%mod;}dfs(1,0);for(inti1;i20;i){for(intu1;un;u){f[u][i]f[f[u][i-1]][i-1];}}for(intcs1,u,v;csm;cs){cinuv;if(uv){cout1\n;continue;}if(de[u]de[v])swap(u,v);intlcaLCA(u,v);if(lcav){coutqpow(pw[de[u]-de[v]],mod-2)\n;}else{intansC(de[u]-de[lca]de[v]-de[lca],de[v]-de[lca]);coutans*qpow(pw[de[u]-de[lca]de[v]-de[lca]],mod-2)%mod\n;}}}LGP14315 [Aboi Round 2] Faputa原题链接[Aboi Round 2] Faputa