2024初三年前集訓測試2

UU：這是我們最簡單一場

菜，就多練練

1. 華二（T2）：

   簡單題。

   直接組合。

   考慮只有互質可以交換。

   所以只要滿足不互質的相對順序不變。

   將所有先扣下來在按回去，求組合數即可。

   就是簡單插板。

   賽時光考慮 \(dp\) 了。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   const int MOD=998244353,N=1e5+3;
   int n,cnt1,cnt2,cnt3,cnt5,cnt7,ans=1;
   
   namespace IO{
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline void read(T &x){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   class MATH{
       int fc[N];
   public:
       MATH(){fc[0]=1;For(i,1,N-1,1) fc[i]=1ll*fc[i-1]*i%MOD;}
       inline int Fpw(int a,int b){
           int ans=1;
           while(b){
               if(b&1) ans=1ll*ans*a%MOD;
               a=1ll*a*a%MOD,b>>=1;
           }
           return ans;
       }
       inline int Inv(int x){return Fpw(x,MOD-2);}
       inline int C(int a,int b){return 1ll*fc[a]*Inv(fc[b])%MOD*Inv(fc[a-b])%MOD;}
   }mt;
   
   int main(){
       freopen("b.in","r",stdin);
       freopen("b.out","w",stdout);
       read(n);
       For(i,1,n,1){
           int a;read(a);
           if(a==1) cnt1++;
           else if(a==5) cnt5++;
           else if(a==7) cnt7++;
           else if(a==3||a==9) cnt3++;
           else if(a==2||a==4||a==8) cnt2++;
           else ans=1ll*ans*mt.C(cnt2+cnt3,cnt2)%MOD,cnt2=cnt3=0;
       }
       ans=1ll*ans*mt.C(cnt2+cnt3,cnt2)%MOD;
       n=n-cnt1-cnt5-cnt7;
       n+=cnt1,ans=1ll*ans*mt.C(n,cnt1)%MOD;
       n+=cnt5,ans=1ll*ans*mt.C(n,cnt5)%MOD;
       n+=cnt7,ans=1ll*ans*mt.C(n,cnt7)%MOD;
       write(ans);
   }
   

2. 高爸（T3）：

   顯然對于每次選取是單峰的，直接權值線段樹維護區間和，套三分即可通過。

   考慮性質：

    1. 每次都一定會將力量值化成已有的一條龍。
   
    2. 每插入一次選擇最多會在值上對上一次移動一個。（若上次 1 2 3 3 5 8 中選 3 最優，則要是插入 4 變成 1 2 3 3 4 5 8，最優一定在 2 3 4 之間）。
   

   1 顯然。

   2：

   考慮一次由 \(n\to n+1 \to n+2\)

   貢獻:

   \[an+b(i-n) \to a(n+1)+b(i-n-1) \to a(n+2)+b(i-n-2) \]

   因為 \(n\) 已經是上次最優，所以：

   \[an+b(i-n-1)\le a(n+1)+b(i-n-2) \le a(n+2)+b(i-n-2) \]

   證畢。

   所以不用三分，隨便拿啥維護下即可。

   注意判重。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   #define int llt
   const int N=1e6+3,S=1e4;
   const int MAX=LLONG_MAX;
   int n,a,b,lp=1;
   int c[N],sum=0,ans=0;
   
   namespace IO{
       template<typename T> inline void write(T x){
           static T st[45];T top=0;if(x<0)x=~x+1,putchar('-');
           do{st[top++]=x%10;}while(x/=10);while(top)putchar(st[--top]^48);
       }
       template<typename T> inline void read(T &x){
           char s=getchar();x=0;bool pd=false;while(s<'0'||'9'<s){if(s=='-') pd=true;s=getchar();}
           while('0'<=s&&s<='9'){x=(x<<1)+(x<<3)+(s^48),s=getchar();}if(pd) x=-x;
       }
   }
   namespace IO{
       template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
       inline void write(const char c){putchar(c);}
       inline void write(const char *c){int len=strlen(c);For(i,0,len-1,1) putchar(c[i]);}
       template<typename T> inline void Write(T x){write(x);putchar(' ');}
       inline void Write(const char c){write(c);if(c!='\n') putchar(' ');}
       inline void Write(const char *c){write(c);if(c[strlen(c)-1]!='\n') putchar(' ');}
       template<typename T,typename... Args> inline void write(T x,Args... args){write(x);write(args...);}
       template<typename T,typename... Args> inline void Write(T x,Args... args){Write(x);Write(args...);}
   }
   using namespace IO;
   class DB{
   private:
       int Len=300,Sz=1,ma[S];
       int sum[S];
       vector<int> bk[S],ls;
       struct POS{int a,b;};
       void rbuild(){
           ls.clear();
           For(i,1,Sz,1){
               for(auto x:bk[i]) ls.push_back(x);
               bk[i].clear(),ma[i]=0,sum[i]=0;
           }
           int ll=ls.size();
           For(i,0,ll-1,1){
               int p=i/Len+1;
               bk[p].push_back(ls[i]),ma[p]=max(ma[p],ls[i]),sum[p]+=ls[i];
           }
           Sz=(ll-1)/Len+1;
       }
   public:
       inline POS Pos(int x){
           int p=1;
           while (x>bk[p].size()&&p<=Sz) x-=bk[p++].size();
           return {p,x-1};
       }
       inline int Pre(int x){
           int p=1,rk=0;
           while(ma[p]<x&&p<Sz) rk+=bk[p++].size();
           int i=0,ll=bk[p].size();
           while(bk[p][i]<x&&i<ll) i++,rk++;
           return rk;
       }
       inline int Nxt(int x){
           int p=1,rk=0;
           while(ma[p]<=x&&p<Sz) rk+=bk[p++].size();
           int i=0,ll=bk[p].size();
           while(bk[p][i]<=x&&i<ll) i++,rk++;
           return rk+1;
       }
       inline void Ins(int x){
           int p=1;
           while(ma[p]<x&&p<Sz) p++;
           ma[p]=max(ma[p],x),sum[p]+=x;
           bk[p].insert(lower_bound(bk[p].begin(),bk[p].end(),x),x);
           if(bk[p].size()>Len*10) rbuild();
       }
       inline int Sum(int l,int r){
           if(r==0||l>r) return 0;
           POS L=Pos(l),R=Pos(r);int ans=0;
           if(L.a==R.a) For(i,L.b,R.b,1) ans+=bk[L.a][i];
           else{
               int la=bk[L.a].size()-1;
               For(i,L.b,la,1) ans+=bk[L.a][i];
               For(i,0,R.b,1) ans+=bk[R.a][i];
               For(i,L.a+1,R.a-1,1) ans+=sum[i];
           }
           return ans;
       }
   }db;
   inline int Get(int x,int n){
       int val=db.Sum(x,x),sa=db.Sum(1,x-1),sb=sum-val-sa;
       return ((x-1)*val-sa)*a+(sb-(n-x)*val)*b;
   }
   
   signed main(){
   #ifndef ONLINE_JUDGE
       freopen("in_out/in.in","r",stdin);
       freopen("in_out/out.out","w",stdout);
   #else
       freopen("c.in","r",stdin);
       freopen("c.out","w",stdout);
   #endif
       read(n),read(a),read(b);
       puts("0"),read(c[1]),db.Ins(c[1]),sum=c[1];
       For(i,2,n,1){
           int val=db.Sum(lp,lp);int x=MAX,y=MAX;
           read(c[i]),db.Ins(c[i]),sum+=c[i];
           if(c[i]<val) ans+=(val-c[i])*a,lp++;
           else ans+=(c[i]-val)*b;
           int nt=db.Nxt(val),pr=db.Pre(val);
           if(nt<=i) x=Get(nt,i);
           if(pr>=1) y=Get(pr,i);
           if(ans>x) ans=x,lp=nt;
           if(ans>y) ans=y,lp=pr;
           write(ans,'\n');
       }
   }
   

3. 金牌（T4）

   可以將一組詢問拆成三段：\(x\) 子樹，\(y\) 子樹，\(x\to y\)

   換根 \(dp\) 分別維護，套個 \(lca\) 就好了。

   UU 把倍增卡了，我又不會 tarjan 和樹剖，只有 99 pts。

   CODE

   #include<bits/stdc++.h>
   using namespace std;
   typedef long long llt;
   typedef unsigned long long ull;
   #define For(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
   #define For_(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
   const int MOD=998244353,N=1e6+4;
   int n,m;
   
   #define LOCAL
   namespace IO {
   #ifdef LOCAL
   FILE *Fin(fopen("d.in", "r")), *Fout(fopen("d.out", "w"));
   #else
   FILE *Fin(stdin), *Fout(stdout);
   #endif
   class qistream {
       static const size_t SIZE = 1 << 24, BLOCK = 32;
       FILE *fp;
       char buf[SIZE];
       int p;
   public:
       qistream(FILE *_fp = stdin): fp(_fp), p(0) {
           fread(buf + p, 1, SIZE - p, fp);
       } void flush() {
           memmove(buf, buf + p, SIZE - p), fread(buf + SIZE - p, 1, p, fp), p = 0;
       } qistream &operator>>(char &str) {
           str = getch();
   
           while (isspace(str))
               str = getch();
   
           return*this;
       } template<class T>qistream &operator>>(T &x) {
           x = 0;
           p + BLOCK >= SIZE ? flush() : void();
           bool flag = false;
   
           for (; !isdigit(buf[p]); ++p)
               flag = buf[p] == '-';
   
           for (; isdigit(buf[p]); ++p)
               x = x * 10 + buf[p] - '0';
   
           x = flag ? -x : x;
           return*this;
       } char getch() {
           return buf[p++];
       } qistream &operator>>(char *str) {
           char ch = getch();
   
           while (ch <= ' ')
               ch = getch();
   
           int i;
   
           for (i = 0; ch > ' '; ++i, ch = getch())
               str[i] = ch;
   
           str[i] = '\0';
   
           return*this;
       }
   } qcin(Fin);
   class qostream {
       static const size_t SIZE = 1 << 24, BLOCK = 32;
       FILE *fp;
       char buf[SIZE];
       int p;
   public:
       qostream(FILE *_fp = stdout): fp(_fp), p(0) {}~qostream() {
           fwrite(buf, 1, p, fp);
       } void flush() {
           fwrite(buf, 1, p, fp), p = 0;
       } template<class T>qostream &operator<<(T x) {
           int len = 0;
           p + BLOCK >= SIZE ? flush() : void();
           x < 0 ? (x = -x, buf[p++] = '-') : 0;
   
           do
               buf[p + len] = x % 10 + '0', x /= 10, ++len;
   
           while (x)
               ;
   
           for (int i = 0, j = len - 1; i < j; ++i, --j)
               swap(buf[p + i], buf[p + j]);
   
           p += len;
           return*this;
       } qostream &operator<<(char x) {
           putch(x);
           return*this;
       } void putch(char ch) {
           p + BLOCK >= SIZE ? flush() : void();
           buf[p++] = ch;
       } qostream &operator<<(char *str) {
           for (int i = 0; str[i]; ++i)
               putch(str[i]);
   
           return*this;
       }
   } qcout(Fout);
   } using namespace IO;
   #define endl '\n'
   class MATH{
   private: int pow[N];
   public: 
       MATH(){pow[0]=1;For(i,1,N,1) pow[i]=1ll*pow[i-1]*2%MOD;}
       inline int Pow(int x){return pow[x];}
   }mt;
   class TO{
   private:
       int fa[N][25],ws[N],w[N],dep[N],to[N<<1],nt[N<<1],hd[N],tot_;
   public:
       #define For_to(i,x,y) for(int i=hd[x],y=to[i];~i;i=nt[i],y=to[i])
       TO(){memset(hd,-1,sizeof hd),dep[1]=1;}
       inline void Add(int x,int y){to[++tot_]=y,nt[tot_]=hd[x],hd[x]=tot_;}
       void dfs1(int x,int f){
           ws[x]=1;
           For_to(i,x,y){
               if(y==f) continue;
               fa[y][0]=x,dep[y]=dep[x]+1;
               For(i,1,20,1) fa[y][i]=fa[fa[y][i-1]][i-1];
               dfs1(y,x);
               ws[x]=(ws[x]+2*ws[y]%MOD)%MOD;
           }
       }
       void dfs2(int x,int f){
           if(f==0) w[x]=ws[x];
           For_to(i,x,y){
               if(y==f) continue;
               w[y]=((w[x]-ws[y]*2%MOD+MOD)%MOD*2%MOD+ws[y])%MOD;
               dfs2(y,x);
           }
       }
       inline int Lca(int x,int y){
           if(dep[x]<dep[y]) swap(x,y);
           For_(i,20,0,1) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
           if(x==y) return x;
           For_(i,20,0,1) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
           return fa[x][0];
       }
       inline int Ans(int x,int y){
           int a=Lca(x,y);
           if(a!=x&&a!=y){
               int dis=mt.Pow(dep[x]+dep[y]-2*dep[a]);
               return 1ll*dis*ws[x]%MOD*ws[y]%MOD;
           }
           if(a==x) swap(x,y);
           if(a==y){
               int cwx=ws[x],dis=mt.Pow(dep[x]-dep[y]);
               For_(i,20,0,1) if(dep[fa[x][i]]>dep[y]) x=fa[x][i];
               return 1ll*dis*cwx%MOD*(w[y]-2*ws[x]%MOD+MOD)%MOD;
           }
           return 0;
       }
   }to;
   
   signed main(){
       qcin>>n;
       For(i,1,n-1,1) {int a,b;qcin>>a>>b;to.Add(a,b),to.Add(b,a);}
       to.dfs1(1,0),to.dfs2(1,0);
       qcin>>m;
       For(i,1,m,1){
           int a,b;qcin>>a>>b;
           qcout<<to.Ans(a,b)<<'\n';
       }
   }