2018河北省省赛

E. K Multiple Longest Commom Subsequence

题意

两个数组 $1\le k,n,m\le 1e3$, 问最长 $k$ 倍公共子序列是多少, $k$ 倍子序列指的是, 将子序列等分, 每份为 $k$ 个数, 且这 $k$ 个数相同. 如 $1,1,2,2$ 是一个 $2$ 倍子序列

题解

$\text{pre_a[i]}$ 表示从 $i$ 开始往前数, 第 $k$ 个 $a[i]$ 的下标

代码

int pre_a[N],pre_b[N];
int t,k,n,m,x,a[N],b[N],cnt[N],dp[N][N];
queue<int>que[N];

int main() {
    in(t);
    while(t--){
        in(k,n,m);
        mem0(pre_a);
        mem0(pre_b);
        for1(i,1000)while(que[i].size())que[i].pop();
        for1(i,n){
            in(x);
            a[i]=x;
            que[x].push(i);
            if(que[x].size()==k){
                int qw=que[x].front();
                que[x].pop();
                pre_a[i]=qw;
            }
        }
        for1(i,1000)while(que[i].size())que[i].pop();
        for1(i,m){
            in(x);
            b[i]=x;
            que[x].push(i);
            if(que[x].size()==k){
                int qw=que[x].front();
                que[x].pop();
                pre_b[i]=qw;
            }
        }
        mem0(dp);
        for1(i,n)
        for1(j,m){
            dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
            if(a[i]==b[j]){
                if(pre_a[i]&&pre_b[j])
                dp[i][j]=max(dp[i][j],dp[ pre_a[i]-1 ][ pre_b[j]-1 ]+1);
            }
        }
        outln(dp[n][m]*k);
    }
    return 0;
}

F. Defending Plan Support

题意

给一棵树, 每个点有权值 $\omega(i)$, 每条边有权值 $d(i,j)$, 找一个点 $x$ 使 $F(x)=\sum \omega(i)\times d(x,i)$ 最小

题解

以 $1$ 为根节点画出这棵树, 设 $j$ 的父节点为 $i$, $tot=\sum\omega(i)$, $sum[i]$ 表示以 $i$ 为根节点的子树的权值和

$$F(j)=F(i)+d(i,j)\times(tot-2*sum[j])$$

代码

ll dp[N],ans,tot;
int sum[N],n,w[N],x,y,z;
bool vis[N];
vector<pii>v[N];
int dfs(int rt,ll len){
    ans+=len*w[rt];
    int tmp=w[rt];
    for(auto i:v[rt]){
        if(vis[i.fi]==0){
            vis[i.fi]=1;
            tmp+=dfs(i.fi,len+i.se);
        }
    }
    return sum[rt]=tmp;
}
void dfs2(int rt){
    for(auto i:v[rt]){
        if(vis[i.fi]==0){
            vis[i.fi]=1;
            dp[i.fi]=dp[rt]+i.se*tot-2ll*i.se*sum[i.fi];
            ans=min(ans,dp[i.fi]);
            dfs2(i.fi);
        }
    }
}
int main() {
    in(n);
    for0(i,n-1){
        in(x,y,z);
        // tot+=z;
        v[x].pb(pii(y,z));
        v[y].pb(pii(x,z));
    }
    for1(i,n){
        in(w[i]);
        tot+=w[i];
    }
    vis[1]=1;
    dfs(1,0);
    mem0(vis);
    vis[1]=1;
    dp[1]=ans;
    dfs2(1);
    outln(ans);
    return 0;
}

K. Bitmap

题意

给一个 $n\times n(1 \leq n \leq 2000)$, 一个 $m\times m(1 \leq m \leq 1000,m\le n)$ 的矩阵, 值的范围为 $[0,255]$, 问 $A$ 中有几个 $B$, 只要每个元素相差一个定值就视为相同

题解

hash, 枚举 $A$ 中 $B$ 的左上角

代码

const int M=1.1e3;
ull Pow[2][M],Hash[2][N][N],seed[2]={131,233},hash_b,hash2[M][M],offset;
int a[N][N],b[M][M],n,m;

void init(){
    Pow[0][0]=Pow[1][0]=1;
    ull tmp[2];
    tmp[0]=tmp[1]=0;
    for0(i,2)
    for1(j,m){
        Pow[i][j]=Pow[i][j-1]*seed[i];
        tmp[i]+=Pow[i][j-1];
    }
    offset=tmp[0]*tmp[1];
    for1(i,n)
    for1(j,n){
        Hash[0][i][j]=Hash[0][i][j-1]*seed[0]+a[i][j];
        Hash[1][i][j]=Hash[1][i-1][j]*seed[1]+Hash[0][i][j];
    }
    for1(i,m){
        for1(j,m)hash2[i][j]=hash2[i][j-1]*seed[0]+b[i][j];
        hash_b=hash_b*seed[1]+hash2[i][m];
    }
    hash_b-=b[1][1]*offset;
}

ull get2(int x1,int y1,int x2,int y2){
    return Hash[1][x2][y2]-Hash[1][x1-1][y1]*Pow[1][m]; 
}
ull get(int x1,int y1,int x2,int y2){
    return get2(x1,y2,x2,y2)-get2(x1,y1-1,x2,y1-1)*Pow[0][m]-a[x1][y1]*offset;
}
int main() {
    in(n,m);
    for1(i,n)
    for1(j,n)in(a[i][j]);
    for1(i,m)
    for1(j,m)in(b[i][j]);
    init();
    int ans=0;
    for(int i=1;i+m-1<=n;i++)
    for(int j=1;j+m-1<=n;j++){
        if(get(i,j,i+m-1,j+m-1)==hash_b)ans++;
    }
    outln(ans);
    return 0;
}

I. Beautiful Array

题意

长度为 $y$, 乘积为 $x$ 的序列的个数

如 $x=2,y=2$, $[1,2],[2,1],[-1,-2],[-2,-1]$

题解

分解 $x$,

$$x=p_1^{a_1}*p_2^{a_2}\cdots p_m^{a_m}$$

对方案数来说, 不同素因子是独立的, 对于 $p_i$, 其贡献相当于将 $a_i$ 个相同的球放进不同的盒子, 且允许有空, 为

$$\large C_{a_i+y-1}^{y-1}$$

再考虑负数, 负号只能为偶数个, 其贡献为

$$\large C_y^0+C_y^2+C_y^4+\cdots=2^{y-1}$$

代码

ll qPow(ll a, ll b, ll c) {  //求(a^b) % c
    ll ret = 1;
    while (b) {
        if (b & 0x1) ret = ret * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ret;
}
bool notPrime[N+1];
int prime[N+1],num_prime=0;
void get_prime(){
  	notPrime[1]=1;
    for(int i=2;i<=N;i++){
        if(!notPrime[i]) prime[num_prime++]=i;
        for(int j=0;j<num_prime&&(ll)i*prime[j]<=N;j++){
            int k = i*prime[j];
            notPrime[k] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
const int M =2.1e6;
ll fac[M],inv[M];
ll C(ll a,ll b){
    if(b>a)return 0;
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void init(){//快速计算阶乘的逆元
    fac[0]=fac[1]=1;
    for(int i=2;i<M;i++)fac[i]=fac[i-1]*i%mod;
    inv[M-1] = qPow(fac[M-1], mod - 2, mod);
  	for (int i = M - 2; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mod;
}
int main() {
    int t,x,y;
    in(t);
    get_prime();
    init();
    while(t--){
        in(x,y);
        if(y==0){
            puts("0");
            continue;
        }else if(x==0){
            puts("1");
            continue;
        }
        ll ans=1;
        for(int i=0;i<num_prime&&x!=1;i++){
            if(x%prime[i]==0){
                int cnt=0;
                while(x%prime[i]==0){
                    x/=prime[i];
                    cnt++;
                }
                ans=ans*C(cnt+y-1,y-1)%mod;
            }
        }
        if(x!=1)ans=ans*y%mod;
        ans=ans*qPow(2,y-1,mod)%mod;
        outln(ans);
    }

    return 0;
}