爆炸的比较厉害……果然还是菜啊……

\(A\)

我们强制一个点为\((0,0)\)，那么设剩下两个点分别为\((a,b),(c,d)\)，根据叉积可以计算出面积为\(ad-bc=S\)，那么令\(ad\)略大于\(S\)，然后对于\(bc\)暴力枚举一下就行了

ll S,p,a,b,c,d,t;void init(){    if(p*p==S)return a=b=p,void();    a=b=p+1;}int main(){    cin>>S,p=sqrt(S);init(),t=a*b-S;    fp(i,1,1e9)if(t%i==0&&t/i<=1e9){c=i,d=t/i;break;}    printf("%lld %lld %lld %lld %lld %lld\n",0ll,0ll,a,c,d,b);    return 0;}

\(B\)

我们考虑记录一个\(pos\)，初始为\(1\)，每一次找到序列中下一个和它元素值一样的位置，不管他们两个位置之间元素值长什么样子，他们两个之间肯定是要全被删掉的，然后令新的\(pos\)为那个一样的位置\(+1\)。因为\(pos\)的取值最多只有\(O(n)\)种，所以最多跑\(n\)次就可以找到循环节，找到循环节之后把\(k\)取个模就行了，剩下的就可以暴力跑了

//quming#include
    
     #define R register#define fp(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
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;typedef long long ll;const int N=5e5+5;int st[N],pk[N],a[N],nxt[N],las[N],xia[N],n,pos,top;ll k;int main(){    scanf("%d%lld",&n,&k);    fp(i,1,n)scanf("%d",&a[i]),nxt[las[a[i]]]=i,las[a[i]]=i;    fp(i,1,n)nxt[las[a[i]]]=i,las[a[i]]=i;    fp(i,1,n-1)xia[i]=i+1;xia[n]=1;    st[++top]=1,pk[top]=1,pos=1;    do{        ++top,pk[top]=pk[top-1]+(nxt[pos]<=pos)+(nxt[pos]==n);        st[top]=pos=xia[nxt[pos]];    }while(st[top]!=st[1]);    k-=(k-1)/(pk[top]-1)*(pk[top]-1);    R int j=1;//  fp(i,1,top)printf("%d %d %d\n",i,st[i],pk[i]);//  printf("%lld\n",k);    while(j<=top-1&&pk[j+1]<=k)++j;//  if(j==top-1)return 0;//  fp(i,st[j],n)printf("%d ",a[i]);    for(R int i=st[j];i<=n;++i){        if(nxt[i]>i)i=nxt[i];        else printf("%d ",a[i]);    }    return 0;}
        
       
      
     
    

\(C\)

比赛的时候我简直就是个\(zz\)

首先，最终的序列合法，当且仅当

\(1.\max(a_i)\leq 2m\)

\(2.a_i\)为奇数的个数小于等于\(m\)个

那么我们只要枚举奇数的个数，把剩下的用隔板法分掉，就能计算出满足条件\(2\)的总的序列个数了。然后再减去所有最大值大于等于\(2m\)的序列，这个相当于把\(m-1\)个数分给\(n\)个人并把剩下的\(2m-1\)个数分给\(n\)个人中的任意一个，把这个方案数减掉就行了

//quming#include
    
     #define R register#define fp(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
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int P=998244353;inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}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;}const int N=3e6+5;int fac[N],ifac[N],n,m,res,lim;inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}int main(){    scanf("%d%d",&n,&m);lim=m*3+n-1;    fac[0]=ifac[0]=1;fp(i,1,lim)fac[i]=mul(fac[i-1],i);    ifac[lim]=ksm(fac[lim],P-2);fd(i,lim-1,1)ifac[i]=mul(ifac[i+1],i+1);    fp(i,0,m)if((3*m-i)&1^1)upd(res,mul(C(n,i),C(((3*m-i)>>1)+n-1,n-1)));    res=dec(res,mul(n,C(m-1+n-1,n-1)));     printf("%d\n",res);    return 0;}
        
       
      
     
    

\(D\)

思路的确很巧妙啊

为了方便起见以下从\(1\)开始标号

没有负环，意味着我们可以跑一个最短路，记\(p_i\)表示点\(i\)到\(1\)的最短距离，则对于剩下的每一条边\((i,j)\)，都有\(p_i+w(i,j)\geq p_j\)

因为所有的\(0\)边都不能被删，所以必然有\(p_i\geq p_{i+1}\)，那么我们定义\(q_i=p_i-p_{i+1}\)，则\(q_i\geq 0\)

对于一条长度为\(1\)的边\((i,j)\)，有\(p_i+1\geq p_j\)，即\(q_j+q_{j+1}+...+q_{i-1}\leq 1\)

对于一条长度为\(-1\)的边\((i,j)\)，有\(p_i-1\geq p_j\)，即\(q_i+q_{i+1}+...+q_{j-1}\geq 1\)

不难发现，对于所有的\(q\)，我们需要考虑的取值只有\(0\)和\(1\)

那么我们设\(f_{j,i}\)表示考虑完了\(q_1\)到\(q_i\)，且上一个为\(1\)的是\(q_i\)，再上一个为\(1\)的是\(q_j\)，此时最小花费是多少。转移的时候，枚举下一个为\(1\)的位置\(q_k\)，则需要删掉的边是，长度为\(1\)，且满足\(r>k,i<l\leq j\)的\((r,l)\)，或者长度为\(-1\)，且满足\(j<l<r\leq k\)的\((l,r)\)，这两个都可以用前缀和预处理，总的复杂度即为\(O(n^3)\)，不过跑不满

//quming#include
    
     #define R register#define fp(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
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;typedef long long ll;const int N=505;const ll inf=0x3f3f3f3f3f3f3f3f;ll sa[N][N],sb[N][N],f[N][N];int n,a[N][N];int main(){    scanf("%d",&n);    fp(i,1,n)fp(j,1,n)if(i!=j)scanf("%d",&a[i][j]);    fp(i,1,n)fp(j,i+1,n+1){        sa[i][j]=sa[i][j-1];        fp(k,i,j-1)sa[i][j]+=a[k][j];    }    fp(i,1,n)fd(j,n,i+1){        sb[i][j]=sb[i][j+1];        fp(k,1,i)sb[i][j]+=a[j][k];    }    memset(f,0x3f,sizeof(f));    f[0][0]=0;    fp(i,0,n)fp(j,i,n)if(f[i][j]
        
       
      
     
    

\(E\)

代码看起来好长啊不写了……

\(F\)

思路很妙啊……

首先容斥，那么我们现在就需要计算至少\(k\)个位置满足\(i+p_i<n^2\)，且所有位置都满足\(i+p_i<(2n)^2\)的方案数

定义\(f(i)\)表示最小的\(a\)使得\(i^2+a^2\geq n\)，\(g(i)\)表示最小的\(a\)使得\(i^2+a^2\geq (2n)^2+1\)，那么假设我们现在已经选出了\(k\)个数使其满足\(i+p_i<n^2\)，那么对于每一个数，它的取值范围都可以表示成\(p_i<h(i)\)，其中\(h(i)=f(i)\)或者\(g(i)\)

然后我们把所有的\(h\)给\(sort\)一下，此时的方案数就是\(\prod\limits_{i=0}^{2n-1}(h_i-i)\)

然后我们考虑所有的\(f(i)(0\leq i<n)\)和\(g(i)(0\leq i<n)\)和\(g(i)(n\leq i<2n)\)，分别记为\(A,B,C\)三类，不难发现\(B\)类永远大于\(A\)类和\(C\)类。且由于\(f\)和\(g\)都不降，我们把三类数合起来排个序，记\(fpos(i)\)表示排序后\(f(i)\)在数组中的位置，则有\(f(0)>f(1)>...>f(n-1)\)恒成立，对\(g\)也如此

那么现在问题转化成从\(0\)到\(n-1\)中，每一个数可以选择\(f(i)\)或者\(g(i)\)，如果选了\(f(i)\)可以对\(k\)这一维\(+1\)，对于一个选的方案贡献数为\(\prod\limits_{i=0}^{2n-1}(h_i-i)\)，求总的贡献

那么\(dp\)，设\(dp_{i,j}\)表示考虑完了\(f,g\)排序之后的前\(i\)个数，且选了\(f\)的有\(j\)个，此时的贡献总和。如果该位置是\(A\)类或\(C\)类我们可以直接计算出它前面有多少个数来计算贡献，如果是\(B\)类，我们可以根据此时的\(k\)来计算它的贡献

所以只要枚举\(k\)即可，复杂度\(O(n^3)\)

//quming#include
    
     #define R register#define fi first#define se second#define fp(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
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;int P;inline int up(R int x){return x<0?x+P:x;}inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}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;}typedef pair
         
           pi;const int N=505;pi st[N];int c[N],a[N],dp[N],top,n,res;inline int f(R int x,R int y){R int r=0;while(r<(n<<1)&&r*r+y*y