THUSC2017口胡 | wzf2000's blog

THUSC2017口胡

THUSC2017口胡


day1

T1

  • 如果是 $k$ 种颜色,就相当于一个最小斯坦纳树的问题。
  • 考虑每次随机将所有颜色分成 $k$ 类,然后跑最小斯坦纳树,正确率大概有 $\dfrac{k!}{k^k}$。
  • 跑个几百次大概就能保证正确率了。

T2

  • 先考虑 $L=1$,令 $pri(n)$ 代表 $\le n$ 的质数个数,那么答案就是 $2^{n-pri(n)}$。
  • 考虑从小到大加入数,一个数可以有 $2$ 的贡献,需要他奇数次的质因子构成的一个向量不能被之前的数线性表示。
  • 也就是可以暴力维护 $[L,R]$ 的质数向量的线性基,这样复杂度大概 $O(\frac{(R-L+1)\times pri(R-L+1)}{\omega})$。(显然只有出现至少两次的质数有意义)
  • 再分析一下,也就是 $2^n$ 再除以 $2$ 的线性无关向量数(不算空)。
  • 然后考虑两个质数不能被分离(同属一个线性向量)显然只有当区间长度比较小时才能做到,大概可以估计区间长度在 $O(\sqrt{L})$时,就必然分离。
  • 我大概取了 $2\sqrt{L}$,可能可以被叉掉。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=700009;
const int M=42600;
int pd[N],pri[N],cnt,L,R,vis[N],chk[N],n,id[N],num=0,pri_num=0;
map<int,int> mp;
vector<int> q[N];
bitset<M> A,xb[M];
int ksm(int x,int y,int ret=1)
{
    for (;y;y>>=1,x=(ll)x*x%mod)
        if (y&1) ret=(ll)ret*x%mod;
    return ret;
}
void add(bitset<M> x)
{
    for (int j=n-1;~j;j--)
        if (x[j])
        {
            if (!xb[j][j])
            {
                xb[j]=x;
                num++;
                return;
            }
            else x^=xb[j];
        }
}
bool qry(bitset<M> x)
{
    if (num==n) return 1;
    for (int j=n-1;~j;j--)
        if (x[j])
        {
            if (!xb[j][j]) return 0;
            else x^=xb[j];
        }
    return 1;
}
void get(int x)
{
    int now=x-L+1;
    for (int i=1;pri[i]*pri[i]<=x;i++)
    {
        if (x%pri[i]) continue;
        int tmp=0;
        while (!(x%pri[i])) x/=pri[i],tmp++;
        if (tmp&1)
        {
            q[now].push_back(pri[i]);
            vis[pri[i]]++;
        }
    }
    if (x>1)
    {
        if (x<N) q[now].push_back(x),vis[x]++;
        else
        {
            chk[now]=1;
            if (!mp.count(x)) mp[x]=1,pri_num++;
        }
    }
}
int main()
{
    scanf("%d%d",&L,&R);
    int ttt=clock();
    pd[1]=1;
    for (int i=2;i<N;i++)
    {
        if (!pd[i]) pri[++cnt]=i;
        for (int j=1;j<=cnt&&pri[j]*i<N;j++)
        {
            pd[pri[j]*i]=1;
            if (i%pri[j]==0) break;
        }
    }
    for (int i=L;i<=R;i++) get(i);
    for (int i=1;i<=cnt;i++)
        if (vis[pri[i]]>1) xb[n].reset(),id[pri[i]]=n++;
        else if (vis[pri[i]]) pri_num++;
    if (R-L+1>=2*sqrt(L))
    {
        pri_num+=n;
        printf("%d\n",ksm(2,R-L+1-pri_num));
        cerr<<"time="<<clock()-ttt<<endl;
        return 0;
    }
    int ret=1;
    int tmp=0;
    for (int i=1;i<=R-L+1;i++)
    {
        bool flag=1;
        A.reset();
        for (int j:q[i])
            if (vis[j]==1)
            {
                flag=0;
                break;
            }
            else A[id[j]]=1;
        if (!chk[i]&&flag&&qry(A)) ret=ret*2%mod;
        else tmp++;
        if (!chk[i]&&flag&&num<n) add(A);
    }
    printf("%d\n",ret);
    cerr<<"time="<<clock()-ttt<<endl;
    return 0;
}

T3

  • 显然就是一个费用流模型,然后线段树优化一下建边即可。

day2

T1

  • 将现在的 $A,B,C$ 数组表示为原来的 $xA+yB+zC$的形式。
  • 然后标记下传什么乱搞一下即可。

T2

  • 显然需要 $\rm polya$ 定理。
  • 然后就变成几个 $n$ 的约数规模的问题。
  • 然后可能可以矩阵乘法,然而我还不会构造和判断环的边界情况。

T3

  • 可以先枚举 $k$ 个点,算他们的公切面上的公切点。
  • 大概通过取出两个球心跟两个切点可以列出一个方程。
  • 然后直接设球心连向切点的单位法向量,就可以变出一个 $k-1$ 元 $2$ 次方程组,恰好 $k-1$ 个方程。
  • 然后我就不会了。