Code Chef May Challenge 2019题解

逃离我推掉我的手 2021-12-23 05:49 131阅读 0赞

[传送门][Link 1]

## \\(REDONE\\) ##

贡献可以拆成\\(X(Y+1)+Y\\)，那么一个数\\(x\\)的贡献对最终答案的贡献就是\\(x(a\_1+1)(a\_2+1)...\\)，那么最终答案肯定是\\(\\sum\\limits\_\{i=1\}^ni\\prod\\limits\_\{j=1\}^\{i-1\}(j+1)\\)最优

void init(){
        fac[0]=1;
        fp(i,1,1e6)fac[i]=mul(fac[i-1],i+1),ans[i]=add(ans[i-1],mul(i,fac[i-1]));
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        init();
        for(int T=read();T;--T)n=read(),print(ans[n]);
        return Ot(),0;
    }

## \\(MATCHS\\) ##

直接辗转相除，假设\\(n<m\\)（如果\\(n=m\\)先手必胜），如果\\(\\left\\lfloor\{m\\over n\}\\right\\rfloor=1\\)先后手必胜反一反，否则先手必胜，用\\(SG\\)函数就能证明

ll n,m;int flag; int main(){ // freopen("testdata.in","r",stdin); for(int T=read();T;--T){ n=read(),m=read(),flag=1; if(n>m)swap(n,m); while(m%n&&m/n==1)flag^=1,m%=n,swap(n,m); puts(flag?"Ari":"Rich"); } return 0; }

## \\(WTBTR\\) ##

先把坐标系旋转\\(45\\)度再扩大\\(\\sqrt\{2\}\\)倍，那么只能选竖直或者水平的直线

易知最优方案一定是\\(n-2\\)条直线穿过\\(n-2\\)个点，剩下一条直线在剩下两个点的中间位置，所以只要求出平面最近点对就行了（这里的距离只有\\(x\\)或\\(y\\)的距离）。正确性可以用反证法证明。

int main(){ // freopen("testdata.in","r",stdin); for(int T=read();T;--T){ n=read(),ans=inf; for(R int i=1,x,y;i<=n;++i)x=read(),y=read(),a[i]=x-y,b[i]=x+y; sort(a+1,a+1+n),sort(b+1,b+1+n); fp(i,2,n)cmin(ans,a[i]-a[i-1]),cmin(ans,b[i]-b[i-1]); printf("%lf\n",ans*0.5); } return 0; }

## \\(ADAROKS2\\) ##

劲啊……

考虑一种涂法，我们不断涂副对角线，并保证涂的过程中没有矩形

第一条副对角线从\\((1,1)\\)开始，然后涂\\((2,2),(3,3)\\)……第二条副对角线从\\((1,2)\\)开始，第三条从\\((1,4)\\)开始……

所以我们该如何保证涂副对角线的过程中没有矩形呢？

我们令副对角线之间的距离依次增大，并记这个距离为\\(a\_i\\)，那么有\\(a\_1=1,a\_2=2,...\\)，不难发现如果存在矩形就意味着有\\(\\sum\\limits\_\{i=l\}^ra\_i=\\sum\\limits\_\{j=ll\}^\{rr\}a\_i\\)，且\\(\[l,r\]\\cap\[ll,rr\]=\\varnothing\\)

可以直接暴力把\\(a\_i\\)预处理出来，然后后面染副对角线就行了

有个比较尴尬的问题就是如果\\(n\\leq 150\\)左右黑色格子数会少于\\(8n\\)，因为左下角那个三角形是没有染的，我们暴力染一下

## \\(BINARY\\) ##

我们可以看做是\\(1\\)不断往左跳，那么我们只要知道每个\\(1\\)往左跳了多少次就可以了，要注意不能跳过界

所以现在问题就是该如何计算一个\\(1\\)在这\\(z\\)秒里有多少秒是往左跳的，有多少秒是停下来的

考虑每一个极长的\\(1\\)的联通块，对于开头的那个\\(1\\)，它是第\\(1\\)秒就开始跳了的，对于第\\(i\\)个\\(1\\)，它是从第\\(i\\)秒才开始向左跳的。如果我们用一个队列来表示一个跳和停地状态，\\(q\[i\]=0\\)表示停下，\\(q\[i\]=1\\)表示跳跃，那么这个极长联通块中没加入一个\\(1\\)都会令\\(q\[++t\]=0\\)并使\\(++h\\)，只要保证\\(t-h+1=z\\)，动态维护这个区间的和就好了

然而跳跃的情况该如何考虑呢？设这个极长联通块到前一个极长联通块之间的\\(0\\)的个数为\\(p\\)，那么以当前的极长联通块中第一个点为例，它会连续往左跳\\(p\\)秒，此时有可能前一个联通块中所有点都已经跳完了，那么它可以继续跳。否则它就必须停下来等一下之后才能继续跳。如果以我们之前的那个\\(q\\)为例，可以发现一次往后加了\\(0\\)点的时候，会把\\(q\\)中的最后一个\\(1\\)变成\\(0\\)。那么我们只要对\\(1\\)开一个链表，记录一下上一个\\(1\\)的位置就行了

然后没有然后了

## \\(TREDEG\\) ##

强行二合一……

首先我们把无根树转化为\\(prufer\\)序列，那么无根树的总数就是\\(n^\{n-2\}\\)，只要计算总的贡献就行了。对于\\(n\\leq 100000\\)的数据答案就是

\\\[Ans=\[x^\{n-2\}\]\\left(\\sum\_\{i=0\}^\\infty \{(d\_i+1)^k\\over d\_i!\}x^i\\right)^n\\\]

直接多项式快速幂就行了

然后是\\(k=1\\)的情况，此时\\(n\\leq 2000000\\)，直接多项式快速幂显然会爆炸

那就换个方法数吧

\\\[ \\begin\{aligned\} Ans &=(n-2)!\\prod\_\{\\sum d\_i=n-2\}\\left(\{d\_i+1\\over d\_i!\}\\right)\\\\ &=(n-2)!\\prod\_\{\\sum d\_i=n-2\}\\left(\{1\\over d\_i!\}+\{1\\over (d\_i-1)!\}\\right)\\\\ \\end\{aligned\} \\\]

我们把括号里的给拆出来，那么假设有\\(x\\)项\\(\{1\\over (d\_i-1)!\}\\)，\\(n-x\\)项\\(\{1\\over d\_i!\}\\)，那么\\(\\sum d\_i=n-2-x\\)，且我们枚举这\\(n\\)个里面那些是\\(d\_i-1\\)，方案数还需要乘上一个\\(\{n\\over x\}\\)

于是总的方案数为

\\\[ \\begin\{aligned\} Ans &=(n-2)!\\sum\_\{k=0\}^\{n-2\}\{n\\choose k\}\\prod\_\{\\sum d\_i=n-2-k\}\{1\\over d\_i!\}\\\\ &=\\sum\_\{k=0\}^\{n-2\}\{n\\choose k\}(n-2)^\{\\underline\{k\}\}(n-2-k)!\\prod\_\{\\sum d\_i=n-2-k\}\{1\\over d\_i!\}\\\\ &=\\sum\_\{k=0\}^\{n-2\}\{n\\choose k\}(n-2)^\{\\underline\{k\}\}n^\{n-2-k\}\\\\ \\end\{aligned\} \\\]

直接\\(O(n)\\)计算就行了

//minamoto #include<bits/stdc++.h> #define R register #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } const int N=(1<<18)+5,P=998244353,M=2e6+5; inline void swap(R int &x,R int &y){R int t=x;x=y,y=t;} inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;} inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;} inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;} int ksm(R int x,R int y){ R int res=1; for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0; return res; } int lg[N],r[21][N],rt[2][N],lim,d; int fac[M],ifac[M],inv[M]; void init(){ fp(d,1,18){ fp(i,1,(1<<d)-1)r[d][i]=(r[d][i>>1]>>1)|((i&1)<<(d-1)); lg[1<<d]=d; } fac[0]=inv[0]=ifac[0]=fac[1]=inv[1]=ifac[1]=1; fp(i,2,2e6){ fac[i]=mul(fac[i-1],i), inv[i]=mul(P-P/i,inv[P%i]), ifac[i]=mul(ifac[i-1],inv[i]); } for(R int t=(P-1)>>1,i=1,x,y;i<262144;i<<=1,t>>=1){ x=ksm(3,t),y=ksm(332748118,t),rt[0][i]=rt[1][i]=1; fp(k,1,i-1) rt[1][i+k]=mul(rt[1][i+k-1],x), rt[0][i+k]=mul(rt[0][i+k-1],y); } } void NTT(int *A,int ty){ fp(i,0,lim-1)if(i<r[d][i])swap(A[i],A[r[d][i]]); R int t; for(R int mid=1;mid<lim;mid<<=1) for(R int j=0;j<lim;j+=(mid<<1)) fp(k,0,mid-1) A[j+k+mid]=dec(A[j+k],t=mul(rt[ty][mid+k],A[j+k+mid])), A[j+k]=add(A[j+k],t); if(!ty){ t=inv[lim]; fp(i,0,lim-1)A[i]=mul(A[i],t); } } void Inv(int *a,int *b,int len){ if(len==1)return b[0]=ksm(a[0],P-2),void(); Inv(a,b,len>>1);static int A[N],B[N]; lim=(len<<1),d=lg[lim]; fp(i,0,len-1)A[i]=a[i],B[i]=b[i]; fp(i,len,lim-1)A[i]=B[i]=0; NTT(A,1),NTT(B,1); fp(i,0,lim-1)A[i]=mul(A[i],mul(B[i],B[i])); NTT(A,0); fp(i,0,len-1)b[i]=dec(add(b[i],b[i]),A[i]); fp(i,len,lim-1)b[i]=0; } void Ln(int *a,int *b,int len){ static int A[N],B[N]; fp(i,1,len-1)A[i-1]=mul(a[i],i);A[len-1]=0; Inv(a,B,len);lim=(len<<1),d=lg[lim]; fp(i,len,lim-1)A[i]=B[i]=0; NTT(A,1),NTT(B,1); fp(i,0,lim-1)A[i]=mul(A[i],B[i]); NTT(A,0); fp(i,1,len-1)b[i]=mul(A[i-1],inv[i]);b[0]=0; fp(i,len,lim-1)b[i]=0; } void Exp(int *a,int *b,int len){ if(len==1)return b[0]=1,void(); Exp(a,b,len>>1); static int A[N];Ln(b,A,len); lim=(len<<1),d=lg[lim]; A[0]=dec(a[0]+1,A[0]); fp(i,1,len-1)A[i]=dec(a[i],A[i]); fp(i,len,lim-1)A[i]=b[i]=0; NTT(A,1),NTT(b,1); fp(i,0,lim-1)b[i]=mul(b[i],A[i]); NTT(b,0); fp(i,len,lim-1)b[i]=0; } void ksm(int *a,int *b,int len,int k){ static int A[N]; Ln(a,A,len); fp(i,0,len-1)A[i]=mul(A[i],k); Exp(A,b,len); } int n,k,ans; inline int C(R int n,R int m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;} int dfs(int pos,int now){ if(pos==n+1)return now==n-2?1:0; int res=0; fp(i,0,n-2-now)res=add(res,mul(dfs(pos+1,now+i),mul(1,ifac[i]))); return res; } int calc1(){ int res=0; int iv=ksm(n,P-2); for(R int i=0,p=ksm(n,n-2),tmp=n-2;i<=n-2;p=mul(p,mul(iv,tmp--)),++i) res=add(res,1ll*fac[n]*ifac[i]%P*ifac[n-i]%P*p%P); return res; } int A[N],B[N]; int calc2(){ int len=1;while(len<=n-2)len<<=1; fp(i,0,len-1)A[i]=mul(ksm(i+1,k),ifac[i]); ksm(A,B,len,n); return mul(B[n-2],fac[n-2]); } int main(){ // freopen("testdata.in","r",stdin); init(); for(int T=read();T;--T){ n=read(),k=read(); ans=(k==1)?calc1():calc2(); ans=mul(ans,ksm(ksm(n,n-2),P-2)); printf("%d\n",ans); } return 0; }

## \\(ADAPWN\\) ##

我们可以把一次操作看成删除一个点，那么这道题就可以看做是一个二分图，选出最少的点删掉，使得剩下的点之间没有边相连，也就是一个最小点覆盖

不过这里有一个问题，就是有一些点是不可能被删掉的，所以它们是不能被选在最小点覆盖里的。我们强制它们不删，那么所有和它们有边相连的点都要被强制删掉

然后就是如何求二分图最小点覆盖了……鉴于咱对二分图一无所知，可以看看\\(fcw\\)巨巨的总结

![5cd2b23f9d71f.png][]

没了

剩下的慢慢补……

转载于:https://www.cnblogs.com/bztMinamoto/p/10808881.html

[Link 1]: https://www.codechef.com/MAY19B?order=desc&sortBy=successful_submissions
[5cd2b23f9d71f.png]: https://i.loli.net/2019/05/08/5cd2b23f9d71f.png