题目地址 https://codeforces.com/gym/102220
题解来源 https://www.cnblogs.com/clrs97/p/11080565.html

题目PDF
the-13th-northeast-collegiate-programming-contest-en.pdf
the-13th-northeast-collegiate-programming-contest-en.pdf

题解概述

the-13th-northeast-collegiate-programming-contest-en.pdf
东北赛Editorial.zip

The 13th Chinese Northeast Collegiate Programming Contest

Code：

A. Apple Business

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N=100010;
  7. int Case,len[N],n,m,i,mx,a[N],size[N],tmp[N];ll ans;
  8. vector<ll>v[N],f[N];
  9. struct E{int u,v,c,w;}e[N];
  10. inline bool cmp(const E&a,const E&b){return a.w>b.w;}
  11. void dfs(int x,int y){
  12.   if(x>n)return;
  13.   if(y>mx)mx=y;
  14.   tmp[y]=a[x];
  15.   dfs(x<<1,y<<1);
  16.   dfs(x<<1|1,y<<1|1);
  17. }
  18. inline void init(int o){
  19.   mx=0;
  20.   dfs(o,1);
  21.   size[o]=mx;
  22.   v[o].resize(mx+1);
  23.   f[o].resize(mx+1);
  24.   for(int i=1;i<=mx;i++)v[o][i]=f[o][i]=tmp[i];
  25. }
  26. inline int getid(int x,int y){
  27.   int k=1<<(len[y]-len[x]);
  28.   return (y&(k-1))|k;
  29. }
  30. inline void append(int A,int B,int C,int W){
  31.   int x,y,o,t,m;
  32.   for(x=A;x;x>>=1){
  33.     o=getid(x,B);
  34.     m=size[x];
  35.     ll dp=f[x][o];
  36.     for(y=o>>1;y;o=y,y>>=1){
  37.       dp+=v[x][y];
  38.       t=y<<1;
  39.       if(t<=m&&t!=o&&f[x][t]<0)dp+=f[x][t];
  40.       t=y<<1|1;
  41.       if(t<=m&&t!=o&&f[x][t]<0)dp+=f[x][t];
  42.     }
  43.     if(dp<C)C=dp;
  44.   }
  45.   if(!C)return;
  46.   ans+=1LL*C*W;
  47.   for(x=A;x;x>>=1){
  48.     o=getid(x,B);
  49.     m=size[x];
  50.     v[x][o]-=C;
  51.     f[x][o]-=C;
  52.     for(y=o>>1;y;y>>=1){
  53.       f[x][y]=v[x][y];
  54.       t=y<<1;
  55.       if(t<=m&&f[x][t]<0)f[x][y]+=f[x][t];
  56.       t=y<<1|1;
  57.       if(t<=m&&f[x][t]<0)f[x][y]+=f[x][t];
  58.     }
  59.   }
  60. }
  61. int main(){
  62.   for(i=1;i<N;i++)len[i]=len[i>>1]+1;
  63.   scanf("%d",&Case);
  64.   while(Case--){
  65.     scanf("%d%d",&n,&m);
  66.     for(i=1;i<=n;i++)scanf("%d",&a[i]);
  67.     for(i=1;i<=n;i++)init(i);
  68.     for(i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].c,&e[i].w);
  69.     sort(e+1,e+m+1,cmp);
  70.     ans=0;
  71.     for(i=1;i<=m;i++)append(e[i].u,e[i].v,e[i].c,e[i].w);
  72.     printf("%lld\n",ans);
  73.   }
  74. }

B. Balanced Diet

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5. const int N=100010;
  6. int T,n,m,i,j,k,l[N];ll f[N],s,A,B,d;
  7. struct E{int a,b;}e[N];
  8. inline bool cmp(const E&a,const E&b){return a.b==b.b?a.a>b.a:a.b<b.b;}
  9. ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
  10. int main(){
  11.   scanf("%d",&T);
  12.   while(T--){
  13.     scanf("%d%d",&n,&m);
  14.     for(i=1;i<=m;i++)scanf("%d",&l[i]);
  15.     for(i=1;i<=n;i++)scanf("%d%d",&e[i].a,&e[i].b);
  16.     sort(e+1,e+n+1,cmp);
  17.     for(i=1;i<=n;i++)f[i]=0;
  18.     for(i=1;i<=n;i=j){
  19.       for(j=i;j<=n&&e[i].b==e[j].b;j++);
  20.       s=0;
  21.       for(k=i;k<j;k++){
  22.         s+=e[k].a;
  23.         if(k-i+1==l[e[i].b])f[k-i+1]+=s;
  24.         if(k-i+1>l[e[i].b])f[k-i+1]+=e[k].a;
  25.       }
  26.     }
  27.     for(i=1;i<=n;i++)f[i]+=f[i-1];
  28.     A=f[1],B=1;
  29.     for(i=2;i<=n;i++)if(f[i]*B>A*i)A=f[i],B=i;
  30.     d=gcd(A,B);
  31.     printf("%lld/%lld\n",A/d,B/d);
  32.   }
  33. }

C. Line-line Intersection

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5. const int N=100010;
  6. int Case,n,i;pair<ll,pair<ll,ll> >f[N],g[N];
  7. inline ll myabs(ll x){return x>0?x:-x;}
  8. ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
  9. inline ll cal(pair<ll,pair<ll,ll> >f[]){
  10.   int i,j;
  11.   ll ret=0;
  12.   sort(f+1,f+n+1);
  13.   for(i=1;i<=n;i=j){
  14.     for(j=i;j<=n&&f[i]==f[j];j++);
  15.     ret+=1LL*(j-i)*(j-i-1);
  16.   }
  17.   return ret/2;
  18. }
  19. int main(){
  20.   scanf("%d",&Case);
  21.   while(Case--){
  22.     scanf("%d",&n);
  23.     for(i=1;i<=n;i++){
  24.       int x1,y1,x2,y2;
  25.       scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  26.       int dx=x2-x1,dy=y2-y1;
  27.       ll a,b,c;
  28.       if(dx==0){
  29.         a=1;
  30.         b=0;
  31.         c=-x1;
  32.       }else{
  33.         a=-dy;
  34.         b=dx;
  35.         c=1LL*dy*x1-1LL*dx*y1;
  36.       }
  37.       if(a<0)a=-a,b=-b,c=-c;
  38.       if(a==0&&b<0)b=-b,c=-c;
  39.       ll d=gcd(myabs(a),gcd(myabs(b),myabs(c)));
  40.       a/=d,b/=d,c/=d;
  41.       f[i].first=a,f[i].second.first=b,f[i].second.second=c;
  42.       d=gcd(myabs(a),myabs(b));
  43.       a/=d,b/=d;
  44.       g[i].first=a,g[i].second.first=b,g[i].second.second=0;
  45.     }
  46.     printf("%lld\n",1LL*n*(n-1)/2-cal(g)+cal(f));
  47.   }
  48. }

D. Master of Data Structure

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cstdlib>
  4. const int N=500010,M=2010,K=M*4,inf=~0U>>1;
  5. int Case,n,m,i,o,x,y,z,root,op[M][4];
  6. int vip[N],g[N],v[N<<1],nxt[N<<1],ed,f[N],d[N],id[N],cnt;
  7. int at[K],G[K],W[K],NXT[K],F[K],D[K];
  8. int vv[K],ve[K];
  9. inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
  10. inline void addedge(int x,int y,int z){NXT[y]=G[x];G[x]=y;W[y]=z;}
  11. inline void umin(int&a,int b){a>b?(a=b):0;}
  12. inline void umax(int&a,int b){a<b?(a=b):0;}
  13. inline int abs(int x){return x>0?x:-x;}
  14. inline void swap(int&a,int&b){int c=a;a=b;b=c;}
  15. void dfs(int x){
  16.   int deg=0;
  17.   for(int i=g[x];i;i=nxt[i]){
  18.     int u=v[i];
  19.     if(u==f[x])continue;
  20.     f[u]=x;
  21.     d[u]=d[x]+1;
  22.     dfs(u);
  23.     if(!id[u])continue;
  24.     deg++;
  25.     id[x]^=id[u];
  26.   }
  27.   if(deg>1)vip[x]=1;
  28.   if(!vip[x])return;
  29.   id[x]=++cnt;
  30.   at[cnt]=x;
  31.   for(int i=g[x];i;i=nxt[i]){
  32.     int u=v[i];
  33.     if(u==f[x])continue;
  34.     u=id[u];
  35.     if(!u)continue;
  36.     addedge(cnt,u,d[at[u]]-d[x]-1);
  37.   }
  38. }
  39. void dfs2(int x,int y){
  40.   F[x]=y;
  41.   D[x]=D[y]+1;
  42.   for(int i=G[x];i;i=NXT[i])dfs2(i,x);
  43. }
  44. int main(){
  45.   scanf("%d",&Case);
  46.   while(Case--){
  47.     scanf("%d%d",&n,&m);
  48.     for(ed=cnt=i=0;i<=n;i++)f[i]=d[i]=id[i]=vip[i]=g[i]=0;
  49.     memset(G,0,sizeof G);
  50.     memset(W,0,sizeof W);
  51.     memset(F,0,sizeof F);
  52.     memset(D,0,sizeof D);
  53.     memset(vv,0,sizeof vv);
  54.     memset(ve,0,sizeof ve);
  55.     for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
  56.     for(i=1;i<=m;i++){
  57.       scanf("%d%d%d",&o,&x,&y);
  58.       vip[x]=vip[y]=1;
  59.       op[i][0]=o;
  60.       op[i][1]=x;
  61.       op[i][2]=y;
  62.       if(o==1||o==2||o==3||o==7)scanf("%d",&op[i][3]);
  63.     }
  64.     for(i=1;i<=n;i++)if(vip[i])root=i;
  65.     dfs(root);
  66.     dfs2(id[root],0);
  67.     for(i=1;i<=m;i++){
  68.       o=op[i][0];
  69.       x=id[op[i][1]];
  70.       y=id[op[i][2]];
  71.       z=op[i][3];
  72.       if(o==1){
  73.         while(x!=y){
  74.           if(D[x]<D[y])swap(x,y);
  75.           vv[x]+=z;
  76.           ve[x]+=z;
  77.           x=F[x];
  78.         }
  79.         vv[x]+=z;
  80.       }
  81.       if(o==2){
  82.         while(x!=y){
  83.           if(D[x]<D[y])swap(x,y);
  84.           vv[x]^=z;
  85.           ve[x]^=z;
  86.           x=F[x];
  87.         }
  88.         vv[x]^=z;
  89.       }
  90.       if(o==3){
  91.         while(x!=y){
  92.           if(D[x]<D[y])swap(x,y);
  93.           if(vv[x]>=z)vv[x]-=z;
  94.           if(ve[x]>=z)ve[x]-=z;
  95.           x=F[x];
  96.         }
  97.         if(vv[x]>=z)vv[x]-=z;
  98.       }
  99.       if(o==4){
  100.         long long ans=0;
  101.         while(x!=y){
  102.           if(D[x]<D[y])swap(x,y);
  103.           ans+=vv[x];
  104.           ans+=1LL*ve[x]*W[x];
  105.           x=F[x];
  106.         }
  107.         printf("%lld\n",ans+vv[x]);
  108.       }
  109.       if(o==5){
  110.         int ans=0;
  111.         while(x!=y){
  112.           if(D[x]<D[y])swap(x,y);
  113.           ans^=vv[x];
  114.           if(W[x]&1)ans^=ve[x];
  115.           x=F[x];
  116.         }
  117.         printf("%d\n",ans^vv[x]);
  118.       }
  119.       if(o==6){
  120.         int mi=inf,ma=0;
  121.         while(x!=y){
  122.           if(D[x]<D[y])swap(x,y);
  123.           umin(mi,vv[x]);
  124.           umax(ma,vv[x]);
  125.           if(W[x]){
  126.             umin(mi,ve[x]);
  127.             umax(ma,ve[x]);
  128.           }
  129.           x=F[x];
  130.         }
  131.         umin(mi,vv[x]);
  132.         umax(ma,vv[x]);
  133.         printf("%d\n",ma-mi);
  134.       }
  135.       if(o==7){
  136.         int ans=inf;
  137.         while(x!=y){
  138.           if(D[x]<D[y])swap(x,y);
  139.           umin(ans,abs(vv[x]-z));
  140.           if(W[x])umin(ans,abs(ve[x]-z));
  141.           x=F[x];
  142.         }
  143.         umin(ans,abs(vv[x]-z));
  144.         printf("%d\n",ans);
  145.       }
  146.     }
  147.   }
  148. }

E. Minimum Spanning Tree

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N=100010;
  7. int Case,n,i,j,x,y,z;vector<int>f[N];ll ans;
  8. int main(){
  9.   scanf("%d",&Case);
  10.   while(Case--){
  11.     scanf("%d",&n);
  12.     for(i=1;i<=n;i++)f[i].clear();
  13.     for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),f[x].push_back(z),f[y].push_back(z);
  14.     ans=0;
  15.     for(i=1;i<=n;i++)if(f[i].size()>1){
  16.       sort(f[i].begin(),f[i].end());
  17.       for(j=1;j<f[i].size();j++)ans+=f[i][0]+f[i][j];
  18.     }
  19.     printf("%lld\n",ans);
  20.   }
  21. }

F. Mini-game Before Contest

  1. #include<cstdio>
  2. const int N=100010,M=200010,K=1<<24;
  3. int Case,n,m,i,j,k,S,A,B,x,y,z,o,deg[N],g[N],v[M],nxt[M],ed;
  4. bool isactor[6],isa[6],ismin[6];
  5. char tmp[9];
  6. int f[N][6],w[N][6][3];
  7. int q[K+5],h,t;
  8. inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
  9. inline void ext(int x,int y,int B){
  10.   int A=f[x][y];
  11.   if(A==B)return;
  12.   t=(t+1)&(K-1);
  13.   q[t]=(x<<7)|(y<<4)|(A<<2)|B;
  14.   f[x][y]=B;
  15. }
  16. inline void check(int x,int y){
  17.   int ret;
  18.   if(ismin[y]){
  19.     if(w[x][y][0])ret=0;
  20.     else if(w[x][y][1])ret=1;
  21.     else ret=2;
  22.   }else{
  23.     if(w[x][y][2])ret=2;
  24.     else if(w[x][y][1])ret=1;
  25.     else ret=0;
  26.   }
  27.   ext(x,y,ret);
  28. }
  29. int main(){
  30.   scanf("%d",&Case);
  31.   while(Case--){
  32.     scanf("%d%d",&n,&m);
  33.     for(ed=i=0;i<=n;i++)deg[i]=g[i]=0;
  34.     while(m--)scanf("%d%d",&x,&y),deg[x]++,add(y,x);
  35.     scanf("%s",tmp);
  36.     for(i=0;i<6;i++)isa[i]=tmp[i]=='A';
  37.     scanf("%s",tmp);
  38.     for(i=0;i<6;i++)isactor[i]=tmp[i]=='1';
  39.     for(i=0;i<6;i++)ismin[i]=isa[i]^isactor[i];
  40.     for(i=1;i<=n;i++)for(j=0;j<6;j++){
  41.       f[i][j]=1;
  42.       for(k=0;k<3;k++)w[i][j][k]=0;
  43.       w[i][j][1]=deg[i];
  44.     }
  45.     h=1,t=0;
  46.     for(i=1;i<=n;i++)if(!deg[i])for(j=0;j<6;j++){
  47.       if(isa[j])ext(i,j,2);
  48.       else ext(i,j,0);
  49.     }
  50.     while(h!=((t+1)&(K-1))){
  51.       S=q[h];
  52.       h=(h+1)&(K-1);
  53.       x=S>>7,y=S>>4&7,A=S>>2&3,B=S&3;
  54.       o=(y+5)%6;
  55.       for(i=g[x];i;i=nxt[i]){
  56.         z=v[i];
  57.         w[z][o][A]--;
  58.         w[z][o][B]++;
  59.         check(z,o);
  60.       }
  61.     }
  62.     for(i=1;i<=n;i++){
  63.       if(f[i][0]==0)putchar('A');
  64.       if(f[i][0]==1)putchar('D');
  65.       if(f[i][0]==2)putchar('B');
  66.     }
  67.     puts("");
  68.   }
  69. }

G. Radar Scanner

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5. const int N=100010;
  6. int Case,n,m,i,j,e[N<<1];
  7. struct P{int l,r;}a[N],b[N];
  8. inline ll solve(P*a){
  9.   m=0;
  10.   ll ans=0;
  11.   for(i=1;i<=n;i++){
  12.     e[++m]=a[i].l;
  13.     e[++m]=a[i].r;
  14.     ans-=a[i].r-a[i].l;
  15.   }
  16.   sort(e+1,e+m+1);
  17.   for(i=1;i<=m;i++)ans+=abs(e[i]-e[n]);
  18.   return ans/2;
  19. }
  20. int main(){
  21.   scanf("%d",&Case);
  22.   while(Case--){
  23.     scanf("%d",&n);
  24.     for(i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].l,&b[i].l,&a[i].r,&b[i].r);
  25.     printf("%lld\n",solve(a)+solve(b));
  26.   }
  27. }

H. Skyscraper

#include<cstdio>
typedef long long ll;
const int N=100010;
int Case,n,m,i,op,x,y;ll z,a[N],b[N],f[N],g[N];
inline void ins(ll*f,int x,ll p){for(;x<=n;x+=x&-x)f[x]+=p;}
inline ll ask(ll*f,int x){ll t=0;for(;x;x-=x&-x)t+=f[x];return t;}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    for(i=1;i<=n;i++)f[i]=g[i]=0;
    for(i=1;i<=n;i++){
      ins(f,i,b[i]);
      if(b[i]>0)ins(g,i,b[i]);
    }
    while(m--){
      scanf("%d%d%d",&op,&x,&y);
      if(op==1){
        y++;
        scanf("%lld",&z);
        ins(f,x,z);
        ins(f,y,-z);
        if(b[x]>0)ins(g,x,-b[x]);
        if(b[y]>0)ins(g,y,-b[y]);
        b[x]+=z;
        b[y]-=z;
        if(b[x]>0)ins(g,x,b[x]);
        if(b[y]>0)ins(g,y,b[y]);
      }else{
        printf("%lld\n",ask(f,x)+ask(g,y)-ask(g,x));
      }
    }
  }
}

I. Temperature Survey

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N=524288,M=200010,K=18,P=998244353,G=3;
typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;
typedef uint32 word;
typedef uint64 dword;
typedef int sword;
const int word_bits=sizeof(word)*8;
word mod,Modinv,r2;
struct UnsafeMod{
  word x;
  UnsafeMod(): x(0) {}
  UnsafeMod(word _x): x(init(_x)) {}
  UnsafeMod& operator += (const UnsafeMod& rhs) {
    (x += rhs.x) >= mod && (x -= mod);
    return *this;
  }
  UnsafeMod& operator -= (const UnsafeMod& rhs) {
    sword(x -= rhs.x) < 0 && (x += mod);
    return *this;
  }
  UnsafeMod& operator *= (const UnsafeMod& rhs) {
    x = reduce(dword(x) * rhs.x);
    return *this;
  }
  UnsafeMod operator + (const UnsafeMod &rhs) const {
    return UnsafeMod(*this) += rhs;
  }
  UnsafeMod operator - (const UnsafeMod &rhs) const {
    return UnsafeMod(*this) -= rhs;
  }
  UnsafeMod operator * (const UnsafeMod &rhs) const {
    return UnsafeMod(*this) *= rhs;
  }
  UnsafeMod pow(uint64 e) const {
    UnsafeMod ret(1);
    for (UnsafeMod base = *this; e; e >>= 1, base *= base) {
      if (e & 1) ret *= base;
    }
    return ret;
  }
  word get() const {
    return reduce(x);
  }
  static word modulus() {
    return mod;
  }
  static word init(word w) {
    return reduce(dword(w) * r2);
  }
  static void set_mod(word m) {
    mod = m;
    Modinv = mul_inv(mod);
    r2 = -dword(mod) % mod;
  }
  static word reduce(dword x) {
    word y = word(x >> word_bits) - word((dword(word(x) * Modinv) * mod) >> word_bits);
    return sword(y) < 0 ? y + mod : y;
  }
  static word mul_inv(word n, int e = 6, word x = 1) {
    return !e ? x : mul_inv(n, e - 1, x * (2 - x * n));
  }
};
int Case,n,i,j,lim[M];
UnsafeMod a[M],b[M],c[M],d[M];
UnsafeMod ta[N+5],tb[N+5];
UnsafeMod g[K+1],ng[K+10],gw[N+10],ngw[N+10];
int pos[N+10],inv[N+10];
UnsafeMod fac[N+5],rev[N+5];
map<int,UnsafeMod>f[M];
struct E{int xl,xr,yl,yr;}e[M];
inline UnsafeMod C(int n,int m){return n<m?0:fac[n]*rev[m]*rev[n-m];}
inline void NTT(UnsafeMod*a,int n,int t){
  int j=__builtin_ctz(n)-1;
  for(int i=0;i<n;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);
  for(int i=1;i<n;i++)if(i<pos[i])std::swap(a[i],a[pos[i]]);
  for(int d=0;(1<<d)<n;d++){
    int m=1<<d,m2=m<<1;
    UnsafeMod*_w=t==1?gw:ngw;
    _w+=m;
    for(int i=0;i<n;i+=m2){
      UnsafeMod*w=_w;
      for(int j=i;j<m+i;j++,w++){
        UnsafeMod t=*w*a[j+m];
        a[j+m]=a[j]-t;
        a[j]+=t;
      }
    }
  }
  if(t==-1){
    UnsafeMod j=inv[n];
    for(int i=0;i<n;i++)a[i]*=j;
  }
}
void build(int l,int r,int yl){
  if(l>r)return;
  int mid=(l+r)>>1;
  e[mid].xl=mid;
  e[mid].xr=r;
  e[mid].yl=yl;
  e[mid].yr=lim[mid];
  build(l,mid-1,yl);
  build(mid+1,r,lim[mid]+1);
}
inline UnsafeMod cal(int x,int y){
  UnsafeMod t=0;
  if(x>1)t=f[x-1][y];
  if(y>1)t+=f[x][y-1];
  return f[x][y]=t;
}
inline void work0(int n,int m,UnsafeMod*a,UnsafeMod*b){
  int i,k;
  for(k=1;k<=(n-1)*2;k<<=1);
  for(i=0;i<k;i++)ta[i]=tb[i]=0;
  for(i=0;i<n;i++){
    ta[i]=a[i]*rev[m];
    tb[i]=fac[i+m]*rev[i];
  }
  NTT(ta,k,1),NTT(tb,k,1);
  for(i=0;i<k;i++)ta[i]*=tb[i];
  NTT(ta,k,-1);
  for(i=0;i<n;i++)b[i]+=ta[i];
}
inline void work1(int n,int m,UnsafeMod*a,UnsafeMod*b){
  int i,k;
  for(k=1;k<=n+n+m-2;k<<=1);
  for(i=0;i<k;i++)ta[i]=tb[i]=0;
  for(i=0;i<n;i++)ta[i]=a[i]*rev[n-i];
  for(i=0;i<n+m;i++)tb[i]=fac[i];
  NTT(ta,k,1),NTT(tb,k,1);
  for(i=0;i<k;i++)ta[i]*=tb[i];
  NTT(ta,k,-1);
  for(i=0;i<m;i++)b[i]+=ta[i+n]*rev[i];
}
inline void solve(int o){
  int xl=e[o].xl,xr=e[o].xr,yl=e[o].yl,yr=e[o].yr;
  if(yl>yr)return;
  int i,j,k,ca,cb;
  if(xl==1){
    for(i=xl;i<=xr;i++)for(j=yl;j<=yr;j++)f[i][j]=C(i+j-2,i-1);
    return;
  }
  cal(xl,yl);
  for(i=yl+1,k=0;i<=yr;i++,k++)a[k]=cal(xl,i);
  for(i=xl+1,k=0;i<=xr;i++,k++)b[k]=cal(i,yl);
  ca=yr-yl-1;
  cb=xr-xl-1;
  if(ca<=0||cb<=0){
    for(i=xl;i<=xr;i++)for(j=yl;j<=yr;j++){
      if(i==xl||j==yl)continue;
      cal(i,j);
    }
    return;
  }
  for(i=0;i<ca;i++)c[i]=b[cb];
  for(i=0;i<cb;i++)d[i]=a[ca];
  work0(ca,cb,a,c);
  work0(cb,ca,b,d);
  work1(ca,cb,a,d);
  work1(cb,ca,b,c);
  for(i=0;i<ca;i++)f[xr][yl+i+1]=c[i];
  for(i=0;i<cb;i++)f[xl+i+1][yr]=d[i];
  f[xr][yr]=c[ca-1]+d[cb-1];
}
int main(){
  UnsafeMod::set_mod(P);
  for(g[K]=((UnsafeMod)G).pow((P-1)/N),ng[K]=g[K].pow(P-2),i=K-1;~i;i--)g[i]=g[i+1]*g[i+1],ng[i]=ng[i+1]*ng[i+1];
  for(i=0;i<=K;i++){
    gw[1<<i]=ngw[1<<i]=1;
    for(j=1;j<1<<i;j++){
      gw[(1<<i)+j]=gw[(1<<i)+j-1]*g[i];
      ngw[(1<<i)+j]=ngw[(1<<i)+j-1]*ng[i];
    }
  }
  for(inv[0]=inv[1]=1,i=2;i<=N;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P;
  for(rev[0]=rev[1]=1,i=2;i<=N;i++)rev[i]=rev[i-1]*inv[i];
  for(fac[0]=i=1;i<=N;i++)fac[i]=fac[i-1]*i;
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&lim[i]);
    n++;
    lim[n]=lim[n-1];
    for(i=1;i<=n;i++)f[i].clear();
    build(1,n,1);
    for(i=1;i<=n;i++)solve(i);
    printf("%u\n",f[n][lim[n]].get());
  }
}

J. Time Limit

#include<cstdio>
#include<algorithm>
using namespace std;
int Case,n,i,x,ans;
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
      scanf("%d",&x);
      if(i==1)ans=x*3;
      else ans=max(ans,x+1);
    }
    while(ans%2)ans++;
    printf("%d\n",ans);
  }
}