Solved:2/10; Upsolved:6/10;

A B C D E F G H I J K L
ylh 🎉 ✔️ 🎉 🎉
pzy
yzj 🎉 🎉

A. B-Suffix Array

Waiting for Solve…..

解题思路:

B. Infinite Tree

解题思路:

​ 对于1到m的阶乘,求出包含它们以及它们LCA的虚树,具体实现过程中dfs序用dep深度代替,然后求LCA需要用到树状数组。建完虚树后就是简单的树形dp。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+50;
int w[maxn],T[maxn],n;
vector<int>pri[maxn],g[maxn];
int h[maxn],st[maxn];
ll dp[maxn],son[maxn],wsum;
void add(int k,int v){for(;k<=n;k+=k&-k) T[k]+=v;}
int qsum(int k){int ans=0;for(;k;k-=k&-k) ans+=T[k];return ans;}
void dfs1(int u,int f){
    for(auto v:g[u]){
        if(v==f) continue;
        dfs1(v,u);son[u]+=son[v];
    }if(u<=n) son[u]+=w[u];
}void dfs2(int u,int f){
    for(auto v:g[u]){
        if(v==f) continue;
        dp[v]=dp[u]+1ll*(h[v]-h[u])*(wsum-2ll*son[v]);dfs2(v,u);
    }
}int cmp(int a,int b){
    return a>b;
}
int main(){
    //freopen("in.txt","r",stdin);
    for(int i=2;i<=1e5;i++){ int a=i;
        for(int j=2;j*j<=a;j++){
            while(a%j==0){
                a/=j;pri[i].push_back(j);
            }
        }if(a>1) pri[i].push_back(a);
        sort(pri[i].begin(),pri[i].end(),cmp);
    }while(scanf("%d",&n)!=EOF){ wsum=0,dp[1]=0;
        for(int i=1;i<=2*n;i++) g[i].clear(),son[i]=0,T[i]=0;
        for(int i=1;i<=n;i++) scanf("%d",&w[i]),wsum+=w[i];
        int top=0,cnt=n;st[++top]=1;
        for(int i=2;i<=n;i++){
            int lca=h[i-1]-qsum(pri[i][0]-1);
            if(lca!=h[st[top]]){
                while(top>1&&h[st[top-1]]>=lca){
                    int x=st[top-1],y=st[top];top--;
                    g[x].push_back(y);g[y].push_back(x);
                }if(top>1&&h[st[top-1]]<lca){
                    int x=st[top];h[++cnt]=lca;
                    g[cnt].push_back(x);g[x].push_back(cnt);
                    st[top]=cnt; 
                }
            }st[++top]=i;h[i]=h[i-1]+pri[i].size();
            for(int j=0;j<pri[i].size();j++){
                add(pri[i][j],1);
            }
        }while(top>1){
            int x=st[top-1],y=st[top];top--;
            g[x].push_back(y);g[y].push_back(x);
        }dfs1(1,0);for(int i=1;i<=n;i++) dp[1]+=1ll*h[i]*w[i];
        dfs2(1,0);ll ans=dp[1];
        for(int i=2;i<=cnt;i++){
            ans=min(ans,dp[i]);
        }printf("%lld\n",ans);
    }
}

C. Domino

​ 给定约束条件$\sum_{i=1}^n\sum_{j=1}^nA_{i,j}x_ix_j\leq1$,使得$\sum_{i=1}^nb_ix_i$最小,求$(\sum_{i=1}^nb_ix_i)^2$的值。(A,b已知,x未知,答案为分数形式对998244353取模)

Waiting for Solve…..

解题思路:

D. Quadratic Form

大致题意:

​ 给定约束条件$\sum_{i=1}^n\sum_{j=1}^nA_{i,j}x_ix_j\leq1$,使得$\sum_{i=1}^nb_ix_i$最小,求$(\sum_{i=1}^nb_ix_i)^2$的值。(A,b已知,x未知,答案为分数形式对998244353取模)

解题思路:

​ 不等式约束优化问题,用拉格朗日乘数法列出KKT方程求解,原问题可化简为求$B^TA^{-1}B$,求出A矩阵的逆矩阵即可。

#include<bits/stdc++.h>
#define rd(a) scanf("%d",&a)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
const int inf=1ll<<30;
const int N=400+5;
const int mod=998244353;
ll qpow(ll a, int b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod){
        if(b&1)res=res*a%mod;
    }
    return res;
}
ll A[N][N],b[N];
ll Gauss_Jordan(int n,int m) {
    ll r=1;
    for(int i=1; i<=n; i++) {
        int row=i;
        for(; row<=n; row++)if(A[row][i])break;
        if(row>n)continue;
        if(row!=i) {
            for(int j=1; j<=m; j++)swap(A[i][j],A[row][j]);
            r=(mod-r)%mod;
        }
        r=r*A[i][i]%mod;
        ll t=qpow(A[i][i],mod-2);
        for(int j=1; j<=m; j++)A[i][j]=A[i][j]*t%mod;
        for(int j=1; j<=n; j++)
            if(j!=i) {
                t=A[j][i];
                for(int k=1; k<=m; k++)A[j][k]=(A[j][k]-t*A[i][k]%mod+mod)%mod;
            }
    }
    return r;
}
int n;
int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%lld",&A[i][j]);
                A[i][j]=(A[i][j]+mod)%mod;
                A[i][j+n]=i==j;
            }
        }
        Gauss_Jordan(n,n<<1);
        for(int i=1;i<=n;i++){
            scanf("%lld",&b[i]);
            b[i]=(b[i]+mod)%mod;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll sum=0;
            for(int j=1;j<=n;j++){
                sum+=A[j][i+n]*b[j]%mod;
                sum%=mod;
            }
            ans+=sum*b[i]%mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

E. Counting Spanning Trees

Waiting for Solve…..

解题思路:

F. Infinite String Comparision

大致题意:

​ 给定约束条件$\sum_{i=1}^n\sum_{j=1}^nA_{i,j}x_ix_j\leq1$,使得$\sum_{i=1}^nb_ix_i$最小,求$(\sum_{i=1}^nb_ix_i)^2$的值。(A,b已知,x未知,答案为分数形式对998244353取模)

解题思路:

​ 不等式约束优化问题,用拉格朗日乘数法列出KKT方程求解,原问题可化简为求$B^TA^{-1}B$,求出A矩阵的逆矩阵即可。

#include<bits/stdc++.h>
#define rd(a) scanf("%d",&a)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
const int inf=1ll<<30;
const int N=400+5;
const int mod=998244353;
ll qpow(ll a, int b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod){
        if(b&1)res=res*a%mod;
    }
    return res;
}
ll A[N][N],b[N];
ll Gauss_Jordan(int n,int m) {
    ll r=1;
    for(int i=1; i<=n; i++) {
        int row=i;
        for(; row<=n; row++)if(A[row][i])break;
        if(row>n)continue;
        if(row!=i) {
            for(int j=1; j<=m; j++)swap(A[i][j],A[row][j]);
            r=(mod-r)%mod;
        }
        r=r*A[i][i]%mod;
        ll t=qpow(A[i][i],mod-2);
        for(int j=1; j<=m; j++)A[i][j]=A[i][j]*t%mod;
        for(int j=1; j<=n; j++)
            if(j!=i) {
                t=A[j][i];
                for(int k=1; k<=m; k++)A[j][k]=(A[j][k]-t*A[i][k]%mod+mod)%mod;
            }
    }
    return r;
}
int n;
int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%lld",&A[i][j]);
                A[i][j]=(A[i][j]+mod)%mod;
                A[i][j+n]=i==j;
            }
        }
        Gauss_Jordan(n,n<<1);
        for(int i=1;i<=n;i++){
            scanf("%lld",&b[i]);
            b[i]=(b[i]+mod)%mod;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll sum=0;
            for(int j=1;j<=n;j++){
                sum+=A[j][i+n]*b[j]%mod;
                sum%=mod;
            }
            ans+=sum*b[i]%mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

G. BaXianGuoHai,GeXianShenTong

Waiting for Solve…..

解题思路:

H. Minmum-cost Flow

解题思路:

I. 1 or 2

解题思路:

J. Easy Integration

解题思路: