牛客多校2025 R6

B Base Conversion Master

 

题目大意

有一个初始 $s \in[2,m]$ ， 目标结果，还有 $n$ 个数组 $A$（每一个数组的第一个元素一定不是 $0$） ， 从第一数组依次往下看下一个数组，对于第一个数组，我们把它的表现形式看作 $s$ 进制的形式 , 假设 $s = 2$，$A_1 = {1,0,0,1}$ ，进而算出实际值为 $9$，让 $s_2 = 9$ , 接着我们把第二个数组看作 $s_2$ 进制形式，依次类推一直算到最后一个数，得到 $s_{n + 1}$ ，问当 $s$ 的取值范围 $[l,r]$ 中 $l,r$ 分别取什么值时才能使 $s_{n + 1} = y$ 。

思路

我们很容易发现如果 $n$ 个数组中不存在长度为 $1$ 的数组，呢么 $s1(初始s),s_2,s_3\dots s_{n+1}$ 是单调不减的，并且$s_i$ 越大也就可以越让计算的数组满足进制形式，也就是数组的每一个元素都小于当前进制形式，因此我们就可以直接二分我们的初始取值范围的 $l,r$（注意计算新的 $s$ 时，数据会很大，但实际上这个值只会和 $y$ 比较，所以说在计算过程中如果只要出现大于 $y$ 的 $s_i$ ，那么最后结果一定也是大于 $y$ 的）。

对于出现长度为 $1$ 的数组的情况，因为 此时 $s$ 不会对这个数组计算来的进制数造成影响，也就影响了$s$ 的单调性，先要找到最后一个长度为 $1$ 的数组的位置，因为这个位置确定了最后 $s_{n+1}$ 的结果，如果计算结果不是 $y$，那么一定不合法，反之我们二分左边界即可。

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define PII pair<int,int>
#define F first 
#define S second 
#define int long long
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>   
using namespace std;
const int N = 5e5+10 ;
const int M = 1e3+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q, y ;
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1){
            if( a > 1e9 || res * a > 1e9) return 1e9 + 10 ;
            res = res * a ;
        }
        b >>= 1 ;
        a = a * a ;

    }
    return res ;
}
void solve(){
    cin >> n >> y >> m ;
    vii a(n) ;
    int len, x ;
    int me = -1 ;
    for(int i = 0 ; i < n ; ++ i){
        cin >> len ;
        if(len == 1){
            me = i ;
        }
        for(int j = 0 ; j < len ; ++ j){
            cin >> x ;
            a[i].push_back(x) ;
        }
    }
    if(me != -1){// 说明无论初始如何选一定会从 me 的 值开始
        int s =   a[me][0] ;
        int la = 0 ;
        for(int i = me + 1 ; i < n ; ++ i){
            la = s ;
            s = 0 ;
            for(int j = 0 ; j < a[i].size() ; ++ j){
                if(a[i][j] >= la){
                    cout << -1 << " " << -1 << endl ;
                    return ;
                }
                s = min(s * la + a[i][j],1000000010LL);
            }
        }
        if(s == y){//但是要保证之前的位置都是合法的
            int l = 2 , r = m ;
            int l1 = m + 1 ;
            auto check3 = [&](int x) -> bool {// s 越大月能满足
                int s = 0 ;
                int la = x ;
                for(int i = 0 ; i <= me ; ++ i){
                    for(int j = 0 ; j < a[i].size() ; ++ j ){
                        if(a[i][j] >= la ) return false ;
                        s = min(s * la + a[i][j],1000000010LL);
                    }
                    la = s ;
                    s = 0 ;
                }
                return true ;
            };
            while(l <= r){
                int mid = l + r >> 1 ;
                if(check3(mid)){
                    l1 = mid ;
                    r = mid -1 ;
                }else{
                    l = mid + 1 ;
                }
            }
            if(l1<=m){
                cout << l1 << " " << m << endl ;
            }else{
                cout << -1 << " " << -1 << endl ;
            }
        }else{
            cout << -1 << " " << -1 << endl ;
        }
        return ;
    }
    auto check1 = [&](int x) -> bool {// s 越大月能满足
        int s = 0 ;
        int la = x ;
        for(int i = 0 ; i <  n ; ++ i){
            for(int j = 0 ; j < a[i].size() ; ++ j ){
                if(a[i][j] >= la ) return false ;
                s = min(s * la + a[i][j],1000000010LL);
                if(s > y){
                    return true;
                }
            }
            la = s ;
            s = 0 ;
        }
        return la >= y ;
    };
    auto check2 = [&](int x) -> bool {
        int s = 0 ;
        int la = x ;
        for(int i = 0 ; i <  n ; ++ i){
            for(int j = 0 ; j < a[i].size() ; ++ j ){
                if(a[i][j] >= la ) return true ;
                s = min(s * la + a[i][j],1000000010LL);
                if(s > y){
                    return false;
                }
            }
            la = s ;
            s = 0 ;
        }
        return la <= y ;
    };
    int l1 = m + 1 ;
    int l = 2, r = m ;
    while(l <= r){
        int mid = l + r >> 1 ;
        if(check1(mid)){
            l1 =mid ; 
            r = mid - 1 ;
        }else{
            l = mid + 1 ;
        }
    }
    int r1 = 1 ;
    l = 2, r = m ;
    while(l <= r){
        int mid = l + r >> 1 ;
        if(check2(mid)){
            r1 = mid ; 
            l = mid + 1 ;
        }else{
            r = mid - 1 ;
        }
    }
    auto check4 = [&](int x) -> bool {
        int s = 0 ;
        int la = x ;
        for(int i = 0 ; i <  n ; ++ i){
            for(int j = 0 ; j < a[i].size() ; ++ j ){
                if(a[i][j] >= la ) return false ;
                s = min(s * la + a[i][j],1000000010LL);
                if(s > y){
                    return false;
                }
            }
            la = s ;
            s = 0 ;
        }
        return la == y ;
    };
    if(l1 > r1 || l1 > m || r1 < 2 || !check4(l1) || !check4(r1)){
        cout << -1 << " " << -1 << endl ;
        return ;
    }
    cout << l1 << " " << r1 << endl ;
}

signed main(){
    IOS ;
    cin >> _ ;
    while(_ --){
        solve() ;
    }
    return 0;
}

 

---

C Stack

题目大意

$p$ 表示长度为 $n$ 的一种排列，$f(p)$ 表示对这个排列进行单调栈运算后的栈长度的，题目问所有的排列的 $(f(p))^3$ 的和。

思路

我们设 $dp[n][k]$ 吧，表示对于长度 $n$ 的排列中单调栈长度为 $k$ 的排列的数量，我们的转移可以看作向长度为$n-1$的排列中项添加新元素 $n$，我们可以发现只有把 $n$ 放到排列的最后一个位置才能让单调栈的长度增加 $1$，因此递推如下

第一项表示放在最后一个位置，第二项表示放在除最后一个位置的其$(n-1)$个位置。

那么 $\sum f(p) = \sum_{k=0}^n [^{n}_{k}] * k$

设 $F(n) = \sum_{k=0}^n k * [^{n}_{k}]$ 表示长度为 $n$ 的所有排列的单调栈的长度之和

设 $G(n) = \sum_{k=0}^n k^2 * [^{n}_{k}]$

设 $H(n) = \sum_{k=0}^n k^3 * [^{n}_{k}]$

$f(n)$ 变换得

$G(n)$ 变换得

$h(n)$ 变换得

综上

以此直接递推即可

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define double long double
#define PII pair<int,int>
#define F first 
#define S second 
#define int long long
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>   
using namespace std;
const int N = 5e5+10 ;
const int M = 1e3+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q ;
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b & 1) res = res * a % MOD2 ;
        b >>= 1  ;
        a = a * a % MOD2 ; 
    }
    return res ;
}
int f[N], g[N], h[N] ;
int fac[N] ;
void init(){
    fac[1] = 1;
    for(int i = 2 ; i< N ; ++ i){
        fac[i] = fac[i-1] * i % MOD2 ;
    }
    f[1] = 1 ;
    g[1] = 1 ;
    h[1] = 1 ;
    for(int i = 2; i < N ; ++ i){
        f[i] = (i * f[i-1] % MOD2 + fac[i-1]) % MOD2 ;
        g[i] = (i * g[i-1] % MOD2 + 2 * f[i-1] + fac[i-1]) % MOD2 ;
        h[i] = (((i * h[i-1] % MOD2 + 3 * g[i-1] % MOD2) % MOD2 + 3 * f[i-1] % MOD2) % MOD2 + fac[i-1]) % MOD2 ;
    }
}
void solve(){
    cin >> n ;
    cout << h[n] << endl ;
}

signed main(){
    IOS ;
    init() ;
    cin >> _ ;
    while(_ --){
        solve() ;
    }
    return 0;
}

 

---

D Beautiful Matrix

思路

因为 $A_{i,j}+A_{k,l}≤A_{i,l}+A_{k,j}$， $1 \leq i < k \leq n,1 \leq j < l \leq n$

所以

我们设 $B_{i,j} = A_{i,j + 1} - A_{i,j}$，实质就是$A$ 的每一行的差分，接着我们保证只要每一行的的 $B$ 都为正数并且和 小于等于 $m$ 就可以满足 $A_{i,j}≤A{i,j + 1}$，$A_{i,j} \in[0,m]$ 这两个条件。我们的 $n * n$ 矩阵就转化成了 $n*(n-1)$ 矩阵，并且对于 $B$ 的每一列从上到小单调不增。

我们假设 $B_{1,j} = x$， 因为列上单调不增，我们可以看作对这一列的从下到上的差分的和等于$x$ ,也就就可以看作把 $x$ 分成 $n$ 份，每一份可以为空集，这样就保证了满足 $A_{i,j}+A_{i + 1,j + 1} ≤ A_{i,j + 1}+A_{i + 1,j}$， 计算公式就是 $C_{n+ x - 1}^{n-1}$，也即是说 $B_{1,j} = x$ 时，这一列的方案书就是 $C_{n+ x - 1}^{n-1}$。

$F(x) = \sum_{i \geq 0} C_{n+ i - 1}^{n-1} x^i$

答案就是 $(F(x))^{n-1}$ 中的前 $m$ 项的系数之和

由广义牛顿二项式定理得

所以说

所以答案就是 $\sum_{i = 0} ^ {m} C_{n*(n-1)+ i - 1}^{i} = C_{n*(n-1) + m}^{m}$

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define PII pair<int,int>
#define F first 
#define S second 
#define int long long
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>   
using namespace std;
const int N = 5e5+10 ;
const int M = 1e3+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q, y ;
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1) res = res * a % MOD2 ;
        b >>= 1 ;
        a = a * a % MOD2;

    }
    return res ;
}
void solve(){
    ans =  0 ;
    cin >> n >> m ;
    int a1 = 1 , a2 = 1 ;
    for(int i = 1 ; i <= m ; ++ i){ 
        a1 = a1 * ((n * (n-1) + m - i + 1) % MOD2) % MOD2 ;
        a2 = a2 * i % MOD2 ;
    }
    ans = a1 * qmi(a2,MOD2 - 2) % MOD2 ;
    cout << ans << endl ;

}

signed main(){
    IOS ;
    while(_ --){
        solve() ;
    }
    return 0;
}

 

---

D Maximum GCD

题目大意

给定一个长度为 $n$ 的数组， 你可以选择一个区间，让这个区间的数都增加 $X$， 问你最大能使得这个数组的 $gcd$ 为多大。

思路

当区间选择就是整个数组时，根据上式吗实质上就是 $a_1 + x$ 和后续差分的 $gcd$ ，我们一定能够让 $a_1 + x$ 变为后续差分 $gcd$ 的倍数，此时答案就是后续差分的 $gcd$

当选择的区间不包含第一个数 $a_1$ 时，我们可以发现最终的 $gcd$ 一定是 $a_1$ 的因子，因此我们枚举 $a_1$ 的因子，然后我们查看数组的差分中有哪些位置上的数不是当前枚举的 $gcd$ 的倍数，

如果数量只有零个，呢么就不用选择区间 $+ x$，初始区间的 $gcd$ 就是当前枚举的 $gcd$ 的倍数。
如果数量只有一个，那么就是在这个位置到最后的位置的区间都加 x，
如果数量只有两个，还需要判断这两个数是不是关于 当前枚举 $gcd$ 互补 $(a + b) % c = 0$，设两个位置分别为 $p_1,p_2$ ,那么区间就是 $[p_1,p_2-1]$。
如果数量大于两个，呢么一定没有合法答案。

因为我们枚举的的答案中也包含了最大答案的 $gcd$ ，所以取最大值即可得到答案。

当选择的区间不包含最后数 $a_n$ 时同理

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define double long double
#define PII pair<int,int>
#define F first 
#define S second 
#define int long long
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>   
using namespace std;
const int N = 5e5+10 ;
const int M = 1e3+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q ;

void solve(){
    ans = 1 ;
    cin >> n ;
    vi a(n + 1,0) ;
    vi b(n + 1,0) ;
    bool f1 = true ;
    for(int i = 1; i <= n ; ++ i){
        cin >> a[i] ;
        if(i >= 2 && a[i] != a[i-1]) f1 = false ;
        b[i] = a[i] - a[i-1] ;
    }
    if(f1){
        cout << 0 << endl ;
        return ;
    }
    int t1 = 0 ;
    for(int i = 2 ; i <= n ; ++ i){
        t1 = gcd(t1, b[i]) ;
    }
    ans = abs(t1) ;

    auto clac = [&]() -> void {
        vi vec1 ;
        for(int i = 1 ; i * i <= a[1] ; ++ i){
            if(a[1] % i == 0){
                vec1.push_back(i) ;
                if(a[1] / i != i){
                    vec1.push_back(a[1] / i) ;
                }
            }
        }

        for(auto e : vec1){
            vi vecte ;
            bool f =true ;
            int cnt = 0 ;
            int la = 0 ;
            for(int i = 2 ; i <= n ; ++ i){
                if(b[i] % e != 0){ 
                    if(cnt == 0){
                        la = b[i] ;
                        f = true ;
                    }else if(cnt == 1){
                        if((b[i] + la) % e == 0){
                            f = true ;
                        }else{
                            f = false ;
                        }
                    }else{
                        f = false ;
                        break ; 
                    }
                    cnt ++ ;
                }

            }
            if(f) ans = max(ans,e) ;
        }
    };
    clac() ;
    reverse(a.begin() + 1, a.end()) ;
    for(int i = 1; i <= n ; ++ i){
        b[i] = a[i] - a[i-1] ;
    }
    clac() ;
    cout << ans << endl ;
}

signed main(){
    IOS ;
    cin >> _ ;
    while(_ --){
        solve() ;
    }
    return 0;
}

 

---