2021牛客多校第二场题解

K题

题目大意：给出n,k，表示一共n个数，生成单调栈序列b，接下来k行每行输入p和v表示b[p] = v，请写出一个满足要求的序列。n<1e6。

思路：k可能小于n，那么将b数组都填满，按如下的规则：若当前b有值，则从此位置到前一个有值的b之间填充b[i]-1,b[i]-2......，最后一个有值的b右边都用最后一个b的值填充。比如已知b[2]=2,b[5]=4,则完整的填充序列为1,2,2,3,4。
接下来按从小到大，从右到左的原则排序并赋值。

ac代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 5e6+6;
int b[N],a[N];
bitset<N> vis;
struct node{
    int id,v,ans;
    bool operator<(const node&t)const{
        if(v == t.v)return id > t.id;
        return v < t.v;
    }
}c[N];
bool cmp(node t1,node t2){
    return t1.id<t2.id;
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= k;i++){
        int p,v;
        scanf("%d%d",&p,&v);
        b[p] = v,vis[p] = true;
    }
    for(int i = 1;i <= n;i++)
        if(vis[i])
            for(int j = i - 1;j >= 1&&!vis[j];j--)
                b[j] = max(1,b[j + 1] - 1);
    for(int i = 1;i <= n;i++)
        if(!b[i])b[i] = b[i - 1];
    int f = 0;
    for(int i = 2;i <= n;i++)    
        if(b[i] >1 + b[i - 1]){
            f = 1;
            break;
        }
    if(b[1]>1)f = 1;
    if(f){
        cout << "-1" << endl;
    }
    else{
        for(int i = 1;i <= n;i++)
            c[i].id = i,c[i].v = b[i];
        sort(c+1,c+n+1);
        int idx = 1;
        for(int i = 1;i <= n;i++)c[i].ans = idx++;
        sort(c+1,c+1+n,cmp);
        for(int i = 1;i <= n;i++)printf("%d ",c[i].ans);
        printf("\n");
    }
    return 0;
}

p.s. 当时没有想到填满b数组，其实如果不填满b数组，b[2]=2和b[2]=3得到的序列可能一样，这并不是我们想要的答案。

J题

题目大意：t组输入，每组给出s,k,p,有s个数，求所有大小为k的子集中，每个子集的所有元素的最大公约数，输出它们的乘积。t<=60,s<=4e4,k<=30,1e6<=p<=1e14.

思路：用容斥原理求出每个数作为最大公约数可以出现在几个集合中。如i作为最大公约数出现在ki个集合中，则本题要求的是∏(i=1,i=maxn)(i ^ ki)，其中maxn为s个数中的最大值。由于p较大且不一定为质数，考虑用欧拉降幂(a ^ b(mod m)=a ^ (b mod phi + phi) mod m)，其中phi为b的欧拉函数值。

ac代码（玄学，同样的代码有可能1001ms也有可能800ms，看评测机发挥了）

#include <bits/stdc++.h>

using namespace std;

const int N = 8e4+4;

typedef long long LL;

LL cnt[N];
LL c[N][35],dp[N];
LL S,k,res,phi;
int T;
LL P;
LL total = 0,factor[100];
//LL euler_phi(LL n) {
//  LL ans = n;
//  for (LL i = 2; i * i <= n; i++)
//    if (n % i == 0) {
//      ans = ans / i * (i - 1);
//      while (n % i == 0) n /= i;
//    }
//  if (n > 1) ans = ans / n * (n - 1);
//  return ans;
//}

LL ksc(LL a, LL b, LL mod) {
    return ((a * b - (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod;
}
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}
//LL ksc(LL a,LL b,LL c){
//    LL res = 0;
//    while(b){
//        if(b&1)res = (res + a)%c;
//        a = (a + a)%c;
//        b>>=1;
//    }
//    return res%c;
//}
LL ksm(LL a,LL b,LL c){
    LL res = 1;
    while(b){
        if(b&1)res =ksc(res,a,c);
        b >>= 1;
        a = ksc(a,a,c);
    }
    return res%c;
}
//LL ksm(LL a,LL b,LL c){
//    LL res = 1;
//    while(b){
//        if(b&1)res = ksc(res,a,c);
//        b >>= 1;
//        a = ksc(a,a,c);
//    }
//    return res%c;
//}


int a[] = { 2, 3, 5, 7, 11 };
bool miller_rabin(LL n) {
    if (n == 1) return 0;
    for (int i = 0; i < 5; ++i) {
        if (n == a[i]) return 1;
        if (!(n % a[i])) return 0;
    }
    LL d = n - 1;
    while (!(d & 1)) d >>= 1;
    for (int i = 1; i <= 5; ++i) {
        LL a = rand() % (n - 2) + 2;
        bool tmp_k = false;
        LL tmp_d = d;
        LL tmp = ksm(a, tmp_d, n);
        if (tmp == 1)    tmp_k = true;
        // 先把所有的2给提出来，然后在一个一个乘上去，这样比直接做快
        while (tmp != 1 && tmp != n - 1 && tmp_d != n - 1) {
            tmp = ksc(tmp, tmp, n);
            tmp_d <<= 1;
        }// 二次探测
        if (tmp == n - 1)    tmp_k = true;

        if (!tmp_k)
            return 0;
    }
    return 1;
}
// 找出n的一个因数
const int M = (1 << 7) - 1;// 一个玄学值

LL pollard_rho(LL n) {
    for (int i = 0; i < 5; ++i) if (n % a[i] == 0) return a[i];
    LL x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;
    for (int k = 2; ; k <<= 1, y = x) {
        LL q = 1;
        // k用于倍增
        for (int i = 1; i <= k; ++i) {
            x = (ksc(x, x, n) + a) % n;// f(x) = x^2+a
            q = ksc(q, abs(x - y), n);// 每一次的|x-y|累加
            // 如果次数超过M
            if (!(i & M)) {
                t = gcd(q, n);
                if (t > 1) break;
            }
        }
        if (t > 1 || (t = gcd(q, n)) > 1) break;
    }
    return t;
}
// 找出x的所有因数
void find(LL x) {
    if (x == 1 || x <= 0) return;
    if (miller_rabin(x)) {
        factor[++total] = x;
        return;
    }
    LL p = x;
    while (p == x) p = pollard_rho(x);
    while (x % p == 0) x /= p;
    find(p);// 递归遍历所有的因数
    find(x);
}
LL C(LL n,LL k){
    if (n < k)return 0;
    return c[n][k];
}
inline LL read() {
    LL s = 0;
    char ch = getchar();
    while (ch < 48 || ch>57)ch = getchar();
    while (ch > 47 && ch < 58)s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
int main(){
//    scanf("%d",&T);
    T = read();
    while(T--){
        memset(cnt,0,sizeof cnt);        
//        scanf("%lld%lld%lld",&S,&k,&P);
        S = read(),k = read(),P = read();
        int maxn = 0;
        for(int i = 1;i <= S;i++){
            int tm;
//            scanf("%d",&tm);
            tm = read();
            cnt[tm]++;
            maxn = max(maxn,tm);
        }
        res = 1;
        total = 0;
        find(P);// 寻找p的约数
        phi = P;// 计算phi(p)
        for (int i = 1; i <= total; i++) {
            phi = phi / factor[i] * (factor[i] - 1);
        }
        c[0][0] = 1;
        for (int i = 1; i <= S; i++) {
            c[i][0] = 1;
            if (i <= 31)    c[i][i] = 1;
            // k的值不会超过30，不需要计算更多位
            for (int j = 1; j < i && j <= 31; j++) {
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]);// 组合数的递推公式
                while (c[i][j] - phi >= phi) c[i][j] -= phi;
            }

        }
//        for (int i = 0; i <= S; i ++ )
//            for (int j = 0; j <= 30&&j<=i; j ++ )
//                if (!j) c[i][j] = 1;
//                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1])%phi;
        for(int i = maxn;i >= 1;i--){
            int tp = 0;
            for(int j = i;j <= maxn;j+=i){
                tp+=cnt[j];
            }
            dp[i] = C(tp,k)%phi;
            for(int j = i + i;j <= maxn;j+=i){
                dp[i]-=dp[j];
            }
            if(dp[i]<0)dp[i] = (dp[i]%phi + phi)%phi;
            if(dp[i]>phi)res = ksc(res,(ksm(i,dp[i]%phi+phi,P)),P);
            else res = ksc(res,(ksm(i,dp[i],P)),P);        
        }
        printf("%lld\n",res);
    }
    return 0;
}

p.s. 真的是一言难尽，从写完第一份到debug完，前前后后四个小时。factor数组记得开long long；快速乘的玄学写法，很快；米勒罗宾素数筛当板子用了，求某个大数的欧拉函数；大体思路都没问题了就慢慢调整细节，尝试各种写法，说不定就快个几十ms就卡过了。

F题

题目大意：给出三维的四个点ABCD的坐标和k1,k2，要求求出同时满足|AP|>=k1|BP|,|CP|>=k2|DP|的点P的可取的区域的体积。

思路：推式子，设A(x1,y1,z1),B(x2,y2,z2),p(x,y,z),则有(x-x1)²+(y-y1)²+(z-z1)²>=k1²[(x-x2)²+(y-y2)²+(z-z2)²],整理可得(k1² - 1)(x² + y² + z²)-(2k1²x2 - 2x1)x - (2k1²y2 - 2y1)y - (2k1²z2 - 2z1)z <= 0，我们发现这是形如x²+y²+z²+Ax+By+Cz+D<=0的球面方程，而该方程的几何意义是P为该球体内部(含边界)的点。该球体半径为sqrt((A² + B² + C² - 4*D)/4)，球心为(-A/2,-B/2,-C/2)。接下来分情况讨论：两球相切、包含、相交。

ac代码：

#include <bits/stdc++.h>

using  namespace std;

const int N = 1010;
const double pi = acos(-1);
int t;
double x[4],y[4],z[4],k1,k2;
int main(){
    scanf("%d",&t);
    while(t--){
        for(int i = 0;i < 4;i++)scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
        scanf("%lf%lf",&k1,&k2);
        double k11 = k1*k1-1,c1x,c1y,c1z,r1;
        c1x = (k1*k1*x[1]-x[0])/k11,c1y = (k1*k1*y[1]-y[0])/k11,c1z = (k1*k1*z[1]-z[0])/k11;
        r1 = sqrt(c1x*c1x+c1y*c1y+c1z*c1z-(k1*k1*((x[1]*x[1])+(y[1]*y[1])+(z[1]*z[1]))-x[0]*x[0]-y[0]*y[0]-z[0]*z[0])/k11);
        double k22 = k2*k2-1,c2x,c2y,c2z,r2;
        c2x = (k2*k2*x[3]-x[2])/k22,c2y = (k2*k2*y[3]-y[2])/k22,c2z = (k2*k2*z[3]-z[2])/k22;
        r2 = sqrt(c2x*c2x+c2y*c2y+c2z*c2z-(k2*k2*((x[3]*x[3])+(y[3]*y[3])+(z[3]*z[3]))-x[2]*x[2]-y[2]*y[2]-z[2]*z[2])/k22);
        double dis = sqrt((c1x-c2x)*(c1x-c2x)+(c1y-c2y)*(c1y-c2y)+(c1z-c2z)*(c1z-c2z));
        double ans = 0.000;
        if(dis>=r1+r2)ans = 0;
        else if(dis + r1 <= r2)ans = (4.000/3.000)*pi*r1*r1*r1;
        else if(dis + r2 <= r1)ans = (4.000/3.000)*pi*r2*r2*r2;
        else{
            double h1 = r1*(1-(r1*r1+dis*dis-r2*r2)/(2.000*dis*r1));//余弦定理求角度，再算h
            double h2 = r2*(1-(r2*r2+dis*dis-r1*r1)/(2.000*dis*r2));
            ans+=(1.000/3.000)*pi*((3.000*r1-h1)*h1*h1+(3.000*r2-h2)*h2*h2); 
        }
        printf("%.3f\n",ans);
    }
    return 0;
}

p.s. 赛场上没来得及看这个题...补题的时候感觉挺可做的。学习了球缺的计算公式：V=pih²(3R-h)/3，其中h为球缺（那个小片）的高，R为球的半径。注意求h的时候要用余弦定理间接求一下，不能草率的直接用(r1+r2-dis)/2，因为球的半径是不一定一样大，不一定能均分滴~