HDU Multi-University Training Contest 1

快来打我* 2021-09-30 08:38 218阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>Sloved</th> 
   <th align="center">A</th> 
   <th align="center">B</th> 
   <th align="center">C</th> 
   <th align="center">D</th> 
   <th align="center">E</th> 
   <th align="center">F</th> 
   <th align="center">G</th> 
   <th align="center">H</th> 
   <th align="center">I</th> 
   <th align="center">J</th> 
   <th align="center">K</th> 
   <th align="center">L</th> 
   <th align="center">M</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>6/13</td> 
   <td align="center">·</td> 
   <td align="center">Ø</td> 
   <td align="center">·</td> 
   <td align="center">Ø</td> 
   <td align="center">O</td> 
   <td align="center">!</td> 
   <td align="center">.</td> 
   <td align="center">Ø</td> 
   <td align="center">!</td> 
   <td align="center">·</td> 
   <td align="center">Ø</td> 
   <td align="center">!</td> 
   <td align="center">Ø</td> 
  </tr> 
 </tbody> 
</table>

*  O for passing during the contest
 *  Ø for passing after the contest
 *  ! for attempted but failed
 *  · for having not attempted yet

upsolve:I  
G题放弃

仅作记录

## A.Blank ##

## B.Operation ##

线性基

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 1e6+100;
    
    struct LB
    { 
        ll p[33];
        int g[33];
        void ins(ll x,int pos)
        { 
             per(i,0,30)
             { 
                 if((x>>i) & 1)
                 { 
                     if(p[i])
                     { 
                         if(g[i] <= pos)
                         { 
                             x ^= p[i];
                             p[i] ^= x;
                             swap(g[i],pos);
                         }
                         else
                             x ^= p[i];
                     }
                     else
                     { 
                         p[i] = x;
                         g[i] = pos;
                         break;
                     }
                 }
             }
        }    
        ll query(int l)
        { 
            ll res = 0;
            per(i,0,30)
            { 
                if(g[i] >= l)
                { 
                    res = max(res,res^p[i]);
                }
            }
            return res;
        }
    } base[maxn];
    
    int n,m;
    
    int gao(int x,int lastans)
    { 
        return (x^lastans)%n+1;
    }
    
    int T;
    int x;
    
    int main(int argc, char const *argv[])
    { 
        // ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        scanf("%d",&T);
        while(T--)
        { 
            scanf("%d%d",&n,&m);
            rep(i,1,n+1)
            { 
                scanf("%d",&x);
                base[i] = base[i-1];
                base[i].ins(x,i);
            }
            ll ans = 0;
            int l,r;
            while(m--)
            { 
                int op;
                scanf("%d",&op);
                if(!op)
                { 
                    scanf("%d%d",&l,&r);
                    l = gao(l,ans);r=gao(r,ans);
                    if(l>r) swap(l,r);
                    ans = base[r].query(l);
                    printf("%lld\n",ans);
                }
                else
                { 
                    n++;
                    scanf("%d",&l);
                    base[n] = base[n-1];
                    base[n].ins(l^ans,n);
                }
            }
        }
        return 0;
    }

## C.Milk ##

## D. Vacation ##

贪心

## E. Path ##

最小割

## F. Typewriter ##

## K. Function ##

∑ i = 1 n g c d ( ⌊ i 3 ⌋ , i ) % 998244353 \\sum\_\{i = 1\}^\{n\} gcd(⌊\\sqrt\[3\]\{i\}⌋,i)\\%998244353 i=1∑ngcd(⌊3i⌋,i)%998244353

由 x = ⌊ i 3 ⌋ 显 然 分 块 ⇒ ∑ i = 1 ⌊ n 3 ⌋ ∑ j = i 3 m i n ( n , ( i + 1 ) 3 + 1 ) g c d ( i , j ) 由x = \\lfloor\\sqrt\[3\]\{i\}\\rfloor 显然分块 \\Rightarrow \\sum\_\{i = 1\}^\{\\lfloor\\sqrt\[3\]\{n\}\\rfloor\}\\sum\_\{j = i^3\}^\{min(n,(i+1)^3+1)\}gcd(i,j) 由x=⌊3i⌋显然分块⇒i=1∑⌊3n⌋j=i3∑min(n,(i\+1)3\+1)gcd(i,j)

设 f ( i , j ) = ∑ x = 1 m g c d ( i , x ) ⇒ f ( i , j ) = ⌊ j i ⌋ f ( i , i ) + f ( i , j % i ) 设f(i,j)=\\sum\_\{x=1\}^\{m\}gcd(i,x)\\Rightarrow f(i,j) = \\lfloor\\frac\{j\}\{i\}\\rfloor f(i,i)+f(i,j\\%i) 设f(i,j)=x=1∑mgcd(i,x)⇒f(i,j)=⌊ij⌋f(i,i)\+f(i,j%i)

易 得 出 f ( i , i ) = ∑ d ∣ i d ϕ ( i d ) , f ( i , j ) = ∑ d ∣ i j d ϕ ( d ) 易得出f(i,i)=\\sum\_\{d|i\}d\\phi(\\frac\{i\}\{d\}),f(i,j)=\\sum\_\{d|i\}\\frac\{j\}\{d\}\\phi(d) 易得出f(i,i)=d∣i∑dϕ(di),f(i,j)=d∣i∑djϕ(d)

对 于 ∑ j = i 3 ( i + 1 ) 3 + 1 g c d ( i , j ) , 通 过 差 分 有 f ( i , ( i + 1 ) 3 + 1 ) − f ( i , i 3 ) = 3 ∗ ( i + 1 ) f ( i , i ) + g c d ( i , i 3 ) = 3 ∗ ( i + 1 ) f ( i , i ) + i , 显 然 f ( i , i ) 通 过 线 性 欧 拉 筛 可 以 O ( n + n log ⁡ n ) 预 处 理 . 对于\\sum\_\{j=i^3\}^\{(i+1)^3+1\}gcd(i,j),通过差分有f(i,(i+1)^3+1)-f(i,i^3)=3\*(i+1)f(i,i)+gcd(i,i^3)=3\*(i+1)f(i,i)+i,显然f(i,i)通过线性欧拉筛可以O(n+\\sqrt\{n\}\\log\{n\})预处理. 对于j=i3∑(i\+1)3\+1gcd(i,j),通过差分有f(i,(i\+1)3\+1)−f(i,i3)=3∗(i\+1)f(i,i)\+gcd(i,i3)=3∗(i\+1)f(i,i)\+i,显然f(i,i)通过线性欧拉筛可以O(n\+nlogn)预处理.

所 以 显 然 只 需 要 考 虑 上 界 为 n 时 的 情 况 , O ( n ) 的 跑 一 边 f ( i , n ) 即 可 所以显然只需要考虑上界为n时的情况,O(\\sqrt\{n\})的跑一边f(i,n)即可 所以显然只需要考虑上界为n时的情况,O(n)的跑一边f(i,n)即可

这 题 卡 常 很 严 ， 所 以 离 线 查 询 ( \_ \_ i n t 128 长 见 识 了 ) 这题卡常很严，所以离线查询(\\\_\\\_int128长见识了) 这题卡常很严，所以离线查询(\_\_int128长见识了)

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e7 + 7;
    const int inf = 0x3f3f3f3f;
    const int mod = 998244353;
    mt19937 mrand(random_device{ }());
    int rnd(int x) {  return mrand() % x;}
    ll gcd(ll a,ll b){ return b ? gcd(b,a % b) : a;}
    int lcm(int a,int b){ return a / gcd(a,b) * b;}
    ll fpow(ll a,ll b)
    { 
        ll res = 1;
        while(b){ 
            if(b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    void read(__int128 &x) { 
        static char ch;static bool neg;
        for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
        for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
        x=neg?-x:x;
    }
    int phi[N],prime[N],cnt;
    bool isprime[N];
    ll f[N];
    void get_phi()
    { 
       phi[1] = 1;
       for(int i = 2;i < N;++i){ 
           if(!isprime[i]){ 
                 prime[++cnt] = i;
                 phi[i] = i - 1;
            }
           for(int j = 1;j <= cnt && i * prime[j] < N;++j){ 
              isprime[i * prime[j]] = 1;
              if(i % prime[j] == 0){ 
                 phi[i * prime[j]] = phi[i] * prime[j];
                 break;
              }
              else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
           }
       }
       for(int i = 1;i * i < N;++i){ 
           int p = i * i;
           for(int j = i * i;j < N;j += i){ 
               f[j] = (f[j] + i * phi[j / i]) % mod;
               if(p < j) f[j] = (f[j] + (j / i) * phi[i]) % mod;
           }
       }
    }
    struct node{ 
        __int128 n;
        int id;
    }a[20];
    bool cmp(node a,node b)
    { 
        return a.n < b.n;
    }
    //ll n;
    ll ans[20],pos[20];
    int main()
    { 
        //freopen("in.txt","r",stdin);
        get_phi();
        int t;
        scanf("%d",&t);
        for(int i = 0;i < t;++i){ 
            read(a[i].n);
            a[i].id = i;
            //scanf("%lld",&n);
        }
        sort(a,a + t,cmp);
        for(__int128 i = 1,cnt = 0;i * i * i < a[t - 1].n;++i){ 
            if((i + 1) * (i + 1) * (i + 1) > a[cnt].n){ 
                if(cnt == t - 1){ 
                    pos[cnt] = i;
                    break;
                }
                while((i + 1) * (i + 1) * (i + 1) > a[cnt].n){ 
                    pos[cnt] = i;
                    cnt++;
                    ans[cnt] = ans[cnt - 1];
                }
    
            }
            ans[cnt] = (ans[cnt] + 3LL * (i + 1) * f[i] + i) % mod;
            if((i + 1) * (i + 1) * (i + 1) == a[cnt].n) ans[cnt] = (ans[cnt] + i + 1) % mod,pos[cnt] = 0;
        }
        for(int jq = 0;jq < t;++jq){ 
            if(pos[jq]){ 
                ll rnt = a[jq].n % pos[jq],ret = a[jq].n / pos[jq] % mod;
                for(ll i = 1;i * i <= pos[jq];++i){ 
                    ll l = pos[jq] / i;
                    if(pos[jq] % i == 0){ 
                        ans[jq] = (ans[jq] + (rnt / i) * phi[i]) % mod;
                        if(i * i < pos[jq]) ans[jq] = (ans[jq] + (rnt / l) * phi[l]) % mod;
                    }
                    i = pos[jq] / l;
                }
                ans[jq] = (ans[jq] + (ret - (pos[jq] * pos[jq])) % mod * f[pos[jq]] % mod + pos[jq] + mod) % mod;
            }
        }
        for(int i = 0;i < t;++i){ 
            for(int j = 0;j < t;++j)
                if(a[j].id == i)printf("%lld\n",ans[j]);
        }
        return 0;
    }

## L. Sequence ##

## M. Code ##

//二维凸包求交集，d<=2必然成立（之前没注意被坑了好久）
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e6 + 7;
    const int inf = 0x3f3f3f3f;
    const int mod = 998244353;
    const double eps = 1e-10;
    mt19937 mrand(random_device{ }());
    int rnd(int x) {  return mrand() % x;}
    ll gcd(ll a,ll b){ return b ? gcd(b,a % b) : a;}
    int lcm(int a,int b){ return a / gcd(a,b) * b;}
    ll fpow(ll a,ll b)
    { 
        ll res = 1;
        while(b){ 
            if(b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    int dcmp(double x){ 
        if(x > eps) return 1;
        if(x < -eps) return -1;
        return 0;
    }
    struct point{ 
        double x, y;
        point(double _x = 0, double _y = 0){ 
            x = _x; y = _y;
        }
        point operator + (const point &q){ 
            return point(x + q.x, y + q.y);
        }
        point operator - (const point &q){ 
            return point(x-q.x, y-q.y);
        }
        bool operator < (const point &q){ 
            if(x == q.x) return y < q.y;
            return x < q.x;
        }
        point operator *(const int rhq){ 
            return point(x*rhq,y*rhq);
        }
        bool operator == (const point &q){ 
            return dcmp(x-q.x) == 0 && dcmp(y -q.y) == 0;
        }
        point rotate(point p, double ang){ 
            point v = (*this) - p;
            double c = cos(ang), s = sin(ang);
            return point(p.x + v.x * c- v.y * s,p.y + v.x * s + v.y * c);
        }
        void read(){ 
            scanf("%lf%lf",&x,&y);
        }
    };
    double sqr(double a){ 
        return a * a;
    }
    double dot(point p, point q){ 
        return p.x * q.x + p.y * q.y;
    }
    double det(point p, point q){ 
        return p.x*q.y - p.y*q.x;
    }
    double cross(point p, point q){ 
        return det(p, q);
    }
    double cross(point p1, point p2, point q1, point q2){ 
        return det(p1 - p2,q1 - q2);
    }
    double dis(point p, point q){ 
        return sqrt(sqr(p.x - q.x) + sqr(p.y - q.y));
    }
    double dis2(point p, point q){ 
        return sqr(p.x-q.x) + sqr(p.y-q.y);
    }
    double ang(point p, point q){ 
        point t;
        return acos(dot(p,q)/dis(p,t)/dis(q,t));
    }
    int ConvexHull(point* P, int cnt, point* res) {  //求凸包
        sort(P, P + cnt);//x1 < x1 || (x1 == x2 && y1 < y2)
        cnt = unique(P, P + cnt) - P;
        int m = 0;
        for(int i = 0; i < cnt; i++) { 
            while (m > 1 && cross(res[m - 1] - res[m - 2], P[i] - res[m - 2]) <= 0) m--;
            res[m++] = P[i];
        }
        int k = m;
        for (int i = cnt - 2; i >= 0; i--) { 
            while (m > k && cross(res[m - 1] - res[m - 2], P[i] - res[m - 2]) <= 0) m--;
            res[m++] = P[i];
        }
        if(cnt > 1) m--;
        return m;
    }
    
    bool OnSegment(point p, point &a1, point a2) { 
        return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
    }
    
    bool Intersection(point a1, point a2, point b1, point b2) { 
        double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
        double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
        return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
    }
    int ispoint(point p, point* pp,int cnt)
    { 
        int wn = 0;
        for (int i = 0; i < cnt; i++) { 
            point p1 = pp[i];
            point p2 = pp[(i + 1) % cnt];
            if (p1 == p || p2 == p || OnSegment(p, p1, p2)) return -1;
            int k = dcmp(cross(p2 - p1, p - p1));
            int d1 = dcmp(p1.y - p.y);
            int d2 = dcmp(p2.y - p.y);
            if (k > 0 && d1 <= 0 && d2 > 0) wn++;
            if (k < 0 && d2 <= 0 && d1 > 0) wn--;
        }
        if (wn != 0) return 1;
        return 0;
    }
    
    bool judge(point *p1,int c1,point *p2,int c2) { 
        for (int i = 0; i < c1; i++) { 
            if (ispoint(p1[i], p2,c2) != 0) return false;
        }
        for (int i = 0; i < c2; i++) { 
            if (ispoint(p2[i], p1,c1) != 0) return false;
        }
        for (int i = 0; i < c1; i++) { 
            for (int j = 0; j < c2; j++) { 
                if (Intersection(p1[i], p1[(i + 1) % c1], p2[j], p2[(j + 1) % c2]))
                    return false;
            }
        }
        return true;
    }
    point za[100],fa[100],tu1[100],tu2[100];
    int a[N];
    int main()
    { 
        //freopen("in.txt","r",stdin);
        int t;
        scanf("%d",&t);
        while(t--){ 
            int n,x1,y1,f,cnt1 = 0,cnt2 = 0,c1,c2;
            scanf("%d",&n);
            for(int i = 0;i < n;++i){ 
                scanf("%d%d%d",&x1,&y1,&f);
                if(f == 1)za[cnt1].x = x1,za[cnt1++].y = y1;
                else fa[cnt2].x = x1,fa[cnt2++].y = y1;
            }
            c1 = cnt1,c2 = cnt2;
            if(cnt1 > 1){ 
                c1 = ConvexHull(za,cnt1,tu1);
            }
            if(cnt2 > 1){ 
                c2 = ConvexHull(fa,cnt2,tu2);
            }
            if(judge(tu1,c1,tu2,c2) || c1 < 2 || c2 < 2) printf("Successful!\n");
            else printf("Infinite loop!\n");
        }
        return 0;
    }