焦作网站开发,免费制作头像的网站,山西手机响应式网站建设,wordpress 提前8小时前言
找大佬嫖到个号来划水打比赛了#xff0c;有的题没写或者不是我写的就不放了。 目前只有#xff1a;1004,1005,1007,1008,1011 正题
题目链接:https://acm.hdu.edu.cn/contests/contest_show.php?cid990 1004 Link with Balls
题目大意
两种盒子各有nnn个#xff…前言
找大佬嫖到个号来划水打比赛了有的题没写或者不是我写的就不放了。 目前只有1004,1005,1007,1008,1011 正题
题目链接:https://acm.hdu.edu.cn/contests/contest_show.php?cid990 1004 Link with Balls
题目大意
两种盒子各有nnn个每个盒子中球的颜色不同
第一种第iii个盒子中可以取出ik(k∈N)ik(k\in N)ik(k∈N)个球第二种第iii个盒子中可以取出不超过iii个球
求取出mmm个球的方案数。
1≤T≤105,1≤n,m≤1061\leq T\leq 10^5,1\leq n,m\leq 10^61≤T≤105,1≤n,m≤106
解题思路
用生成函数推导第一种球的函数是11−xi\frac{1}{1-x^i}1−xi1第二种球的函数是1−xi11−x\frac{1-x^{i1}}{1-x}1−x1−xi1发现相乘可以抵消。最后乘出来是 (1−xn1)(11−x)n1(1-x^{n1})(\frac{1}{1-x})^{n1}(1−xn1)(1−x1)n1 然后化回来就是 (nmn)−(m−1n)\binom{nm}{n}-\binom{m-1}{n}(nnm)−(nm−1) 就好了
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e610,P1e97;
ll T,inv[N],fac[N],n,m;
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
signed main()
{inv[1]1;for(ll i2;iN;i)inv[i]P-inv[P%i]*(P/i)%P;inv[0]fac[0]1;for(ll i1;iN;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P;scanf(%lld,T);while(T--){scanf(%lld%lld,n,m);ll ansC(mn,n);m-n1;if(m0)ans(ans-C(mn,n)P)%P;printf(%lld\n,ans);}
}1005 Link with EQ
题目大意
nnn个格子的凳子开始第一个同学会随机选择一个位置坐下剩下的同学会选择随机一个距离已有同学最远的位置坐下求没有位置的周围都没有同学时期望坐下了多少个同学。 1≤T≤105,1≤n≤1061\leq T\leq 10^5,1\leq n\leq 10^61≤T≤105,1≤n≤106
解题思路
设fif_ifi表示只有iii个格子且边边都有同学时还能做多少个人这个可以很容易dpdpdp出来。
然后主要考虑第一个人的座位特判一下头尾两个位置然后剩下的对fff求个前缀和就可以很快计算了。
时间复杂度O(nTlogP)O(nT\log P)O(nTlogP)
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1048576,P1e97;
ll T,n,f[N],g[N],s[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{for(ll i3;iN;i){ll mid(i1)/2;f[i]f[mid-1]f[i-mid]1;s[i](s[i-1]f[i]*2)%P;}for(ll i1;iN;i)g[i]f[i]2;scanf(%lld,T);while(T--){scanf(%lld,n);if(n2){puts(1);continue;}if(n3){puts(666666673);continue;}ll ans(3*(n-4)s[n-4])%P;(ansg[n-2]*2g[n-3]*2)%P;ansans*power(n,P-2)%P;printf(%lld\n,ans);}return 0;
}1007 Link with Limit
题目大意
给出置换fff然后fi(x)f_i(x)fi(x)表示xxx置换iii次之后的位置。 定义 g(x)limn−∞1n∑i1nfi(x)g(x)\lim_{n-\infty}\frac{1}{n}\sum_{i1}^nf_i(x)g(x)n−∞limn1i1∑nfi(x)
求是否对于所有g(x)(x∈[1,n])g(x)(x\in [1,n])g(x)(x∈[1,n])都是相同的值。
1≤n≤1051\leq n\leq 10^51≤n≤105
解题思路
最后肯定会置换到一个环内考虑每个环的平均值是否相等即可
时间复杂度O(n)O(n)O(n)
代码由我们伟大的stoorz\text{stoorz}stoorz写出所以我没有 1011 Yiwen with Formula
题目大意
给出nnn个数的一个可重集合aaa。求它的所有子集的和的乘积。模998244353998244353998244353。
1≤T≤10,1≤n≤105,∑n≤2.5×105,∑ai≤4×1051\leq T\leq 10,1\leq n\leq 10^5,\sum n\leq 2.5\times 10^5,\sum a_i\leq 4\times 10^51≤T≤10,1≤n≤105,∑n≤2.5×105,∑ai≤4×105
解题思路
暴力用分治NTTNTTNTT求出每个和的方案数然后因为是当指数的所以要模φ(998244353)\varphi(998244353)φ(998244353)所以要用任意模数就可暴草过去了。
code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long long
using namespace std;
const ll N4e5*410,sqq32768,p998244352,P998244353;
const double Piacos(-1);
struct complex{double x,y;complex (double xx0,double yy0){xxx;yyy;return;}
}A[N],B[N],C[N],D[N];
struct Poly{ll a[N],n;
}F[20];
ll power(ll x,ll b,ll P){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
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);}
complex w[N];
ll n,m,T,u[N],v[21],r[N];
void FFT(complex *f,ll op,ll n){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].x(ll)(f[i].x/n0.49);}return;
}
void MTT(ll *a,ll *b,ll *c,ll m,ll k){ll n1;while(nmk)n1;for(ll i0;in;i){r[i](r[i1]1)|((i1)?(n1):0);A[i].xA[i].yB[i].xB[i].y0;C[i].xC[i].yD[i].xD[i].y0;}for(ll len1;lenn;len1)for(ll i0;ilen;i)w[n/len*i]complex(cos(i*Pi/len),sin(i*Pi/len));for(ll i0;im;i)A[i].xa[i]/sqq,B[i].xa[i]%sqq;for(ll i0;ik;i)C[i].xb[i]/sqq,D[i].xb[i]%sqq;FFT(A,1,n);FFT(B,1,n);FFT(C,1,n);FFT(D,1,n);complex t1,t2;for(ll i0;in;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,-1,n);FFT(B,-1,n);FFT(C,-1,n);for(ll i0;in;i){c[i]0;(c[i](ll)(A[i].x)*sqq%p*sqq%p)%p;(c[i](ll)(B[i].x)*sqq%p)%p;(c[i](ll)(C[i].x))%p;}return;
}
void Mul(Poly a,Poly b){MTT(a.a,b.a,a.a,a.n,b.n);a.na.nb.n-1;return;
}
ll findq(){for(ll i0;i20;i)if(!v[i]){v[i]1;return i;}
}
ll Solve(ll l,ll r){if(lr){ll pfindq();for(ll i0;iu[l];i)F[p].a[i]0;F[p].a[0]1;F[p].a[u[l]]1;F[p].nu[l]1;return p;}ll mid(lr)1;ll lsSolve(l,mid),rsSolve(mid1,r);Mul(F[ls],F[rs]);v[rs]0;return ls;
}
signed main(){scanf(%lld,T);while(T--){scanf(%lld,n);bool flag0;ll ans1,sum0;for(ll i1;in;i){scanf(%lld,u[i]);flag|!u[i];sumu[i];}if(flag){puts(0);continue;}ll idSolve(1,n);u[id]0;for(ll i1;isum;i)ansans*power(i,F[id].a[i],P)%P;printf(%lld\n,ans);}
}
