618模拟赛

T1

过于沙雕，直接跳过

T2

有一棵二叉树，我们定义如下：
每个结点都有两个孩子：左孩子与右孩子；
如果结点的值为整数 X,那么左孩子的值为 2X，右孩子的值为 2X+1；
根的值定义为 1。
现在，小 Y 同学在这棵二叉树上模拟步行。步行时由大写字母 L,R,P 来描述：
字母 L 表示走到左孩子上；
字母 R 表示走到右孩子上；
字母 P 表示停留。
步行结束时所在的结点的值即是步行的值，例如：LRP 的值是 5，RPP 的值是 3。
步行过程用一段包含字符 L,R,P 和的串表示，则可以表示三种移动的任意一种。
我们可以把分裂出的3个点整体考虑
也就是说L是总值2，R总值2+1，而则是*5+当前个数

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
    long long tot=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') ch=getchar(),fs=-1;
    while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
    return tot*fs;  
}
char s[10009];
int lens=1;
int len=1;
int cnt[100009],lencnt=1;
int num[100009];
int main ()
{
    scanf("%s",s);
    num[1]=1;
    cnt[1]=1;
    lens=strlen(s);
    for(int i=0;i<lens;i++)
    {
        if(s[i]=='L')
        {
            for(int i=1;i<=len;i++)
            {
                num[i]*=2;  
            }
            for(int i=1;i<=len;i++)
            {
                if(num[i]>9)
                {   
                    num[i+1]+=num[i]/10;
                    num[i]%=10; 
                }
                while(num[len+1]!=0) len++;
            }
        }
        if(s[i]=='R')
        {
            for(int i=1;i<=len;i++)
            {
                num[i]*=2;  
            }
            for(int i=1;i<=lencnt;i++)
            {
                num[i]+=cnt[i]; 
            }
            for(int i=1;i<=len;i++)
            {
                if(num[i]>9)
                {   
                    num[i+1]+=num[i]/10;
                    num[i]%=10; 
                }
                while(num[len+1]!=0) len++;
            }   
        }
        if(s[i]=='*') 
        {
            for(int i=1;i<=len;i++)
            {
                num[i]*=5;  
            }
            for(int i=1;i<=lencnt;i++)
            {
                num[i]+=cnt[i]; 
            }
            for(int i=1;i<=len;i++)
            {
                if(num[i]>9)
                {   
                    num[i+1]+=num[i]/10;
                    num[i]%=10; 
                }
                while(num[len+1]!=0) len++;
            }   
            for(int i=1;i<=lencnt;i++)
            {
                cnt[i]*=3;  
            }
            for(int i=1;i<=lencnt;i++)
            {
                if(cnt[i]>9)
                {   
                    cnt[i+1]+=cnt[i]/10;
                    cnt[i]%=10; 
                }
                while(cnt[lencnt+1]!=0) lencnt++;
            }
        }
    }
    for(int i=len;i>=1;i--)
    {
        printf("%d",num[i]);
    }
    return 0;
}

T3

过于沙雕，直接跳过

T4

有 n 个正整数 x1~xn，初始时状态均为未选。
有 m 个操作，每个操作给定一个编号 i，将 xi 的选取状态取反。
每次操作后，你需要求出选取的数中有多少个互质的无序数对。

·f(i)表示GCD为i的数对个数

·g(i)表示GCD为i的倍数的数对个数

·s(i)表示为i的倍数的数的个数

则有g(i)=s(i)*(s(i)-1)/2
g(i)=sigama(f(d))(i|d)
莫比乌斯反演即可
那么修改怎么办呢？
修改影响s
s影响g
g影响f
去掉旧的加上新的即可

   #include<stdio.h>
#define ll long long
#define go(i,a,b) for(int i=a;i<=b;i++)
const int N=500003;
int n,m,a[N],I,x,d,Mob[N];
ll s[N],g[N],f[N],ans;bool get[N];
struct Sieve
{
    int prime[N],t;bool no[N];
    void Mobius_Sieve()
    {
        Mob[1]=1;
        go(i,2,500000){if(!no[i])Mob[prime[++t]=i]=-1;
        go(j,1,t){if(1ll*prime[j]*i>500000)break;
        Mob[i*prime[j]]=i%prime[j]?-Mob[i]:0;
        no[i*prime[j]]=1;if(i%prime[j]==0)break;}}
    }
}Tool;
int main()
{    
    Tool.Mobius_Sieve();
    scanf("%d%d",&n,&m);
    go(i,1,n)scanf("%d",a+i);
    while(m--)
    {
        scanf("%d",&I);x=a[I];
        d=(get[I]^=1)?1:-1;
        go(i,1,x)if(x%i==0&&i*i<=x)
        {
            s[i]+=d;if(i!=x/i)
            s[x/i]+=d;

            ans-=Mob[i]*g[i];if(i!=x/i)
            ans-=Mob[x/i]*g[x/i];

            g[i]=s[i]*(s[i]-1)/2;if(i!=x/i)
            g[x/i]=s[x/i]*(s[x/i]-1)/2;

            ans+=Mob[i]*g[i];if(i!=x/i)
            ans+=Mob[x/i]*g[x/i];
        }
        else if(i*i>x)break;
        printf("%lld\n",ans);
    }
    return 0;
}