T1

暴力肯定是不行的，考虑如何对这个 $x$ 计数，考虑算术唯一分解定理，对于 $\gcd$ 来说就是所有质数上指数取 $\min$ ，那么对 $\gcd(a+x,m)=\gcd(a,m)$ 可以把 $x$ 以质因数分解的形式看待的话，就是加上 $x$ 之后取 $\min$ 的值不变，可以分析出几个性质：

$x$ 不会添加新的质数，质数取集只在 $a,m$ 之间。
$x$ 不会改变 $a$ 取到 $\min$ 指数的质数贡献。

那么有 $\gcd(x,m)=\gcd(a,m)$ ，除掉 $\gcd(a,m)$ ， $\gcd(\frac{x}{\gcd(a,m)},\frac{m}{\gcd(a,m)})=1$ ，求有多少满足这个的 $x$ ，显然这是欧拉函数的定义，答案就是 $\varphi(\frac{m}{\gcd(a,m)})$ ， $\sqrt{m}$ 直接做即可。

显然我们没有看数据，数据中有一个及其 nb 的地方在于多测且 $t\le 2 \times 10^6$ ，而 $m$ 在 $10^7$ 根号显然会炸掉，需要线性筛预处理不然只有 60 分也是无敌了，下次多留心以下数据吧 www。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e7+15;
int a,m,phi[MN];
vector<int> prime;
vector<bool> notp(1e7+15);

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

void euler(int n){
    phi[1]=1;
    notp[1]=1;
    for(int i=2;i<=n;i++){
        if(!notp[i]){
            prime.push_back(i);
            phi[i]=i-1;
        }
        for(auto p:prime){
            if(i*p>n) break;
            notp[i*p]=1;
            if(i%p==0){
                phi[i*p]=phi[i]*p;
                break;
            }
            phi[i*p]=phi[i]*(p-1);
        }
    }
}

int phii(int n){
    if(n<=1e7) return phi[n];
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>=2){
        ans=ans/n*(n-1);
    }
    return ans;
}



void solve(){
    read(a,m);
    put(phii(m/__gcd(a,m)));
}

signed main(){
    #ifndef ONLINE_JUDGE
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    #endif
    euler(1e7);
    int T;
    read(T);
    while(T--){
        solve();
    }

    return 0;
}

T2

PAM？PAM？Manacher？其实不是。

正着做及其困难，因为我也不知道这玩意到底怎么做，反正我们正难则反，那么答案就是 $\dfrac{n\times n-1}{2}-\text{坏子串个数}$ 。让后现在问题在于怎么求后面的坏子串个数。

考虑坏子串有没有什么性质，手摸不难发现坏子串只可能有如下四种情况：

$\dots AAAAB$
$\dots BBBBA$
$ABBBB\dots$
$BAAAA\dots$

只有一端端头字符不同的子串不合法。可以 $O(n)$ 扫一遍乘两边贡献就可以了，但是我是唐诗我 $O(n^2 \log n)$ 暴力拿下 80 分，剪枝高手有点无敌。

反思：做完题目之后要正确分析复杂度，而不是靠着虚无的剪枝骗分。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=5e6+15;
int a[MN],n,ans;
string s;


namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;


signed main(){
    #ifndef ONLINE_JUDGE
    freopen("palin.in","r",stdin);
    freopen("palin.out","w",stdout);
    #endif
    read(n,s);
    for(int i=0,r;i<n;i=r){
        r=i;
        while(r<n&&s[i]==s[r]) r++;
        if(i>0) ans+=r-i;
        if(r<n) ans+=r-i-1;
    }
    put(n*(n-1)/2-ans);
    return 0;
}

T3

给定一个仅包含小写英文字母的字符串 $S$ ，你需要以最小代价编辑出完全等于 $S$ 的字符串。
初始时，你手中并没有任何字符。你可以使用以下操作：
购买操作：你可以一次性购买 $S$ 的任意前缀。若购买的是长度为 $L$ 的前缀，则需花费 $a \times L$ 万元。
复制操作：你可以将当前已有的字符串整体复制一遍并接在末尾，花费 $b$ 万元。
切割操作：你可以在当前字符串的任意位置切开，只保留前缀部分，花费 $c$ 万元。
你可以多次使用这些操作，顺序任意。请计算：最少需要花费多少万元才能编辑出字符串 $S$ 。
$1\le x,y,z \le 10,1\le |S| \le 2\times 10^5$ 。

好题，因为我真不太会拓展 kmp www。

设 $f(i)$ 表示编辑出前缀 $i$ 的最小花费，有三种转移：

直接购买： $f(i)=x\times i$ ；
倍长 $f(2i)=f(i)+y$ ，当且仅当 $s[1,i]=s[i+1,2i]$ 。
倍长后剪切： $f(i+k)=f(i)+y+z$ ，当且仅当 $s[1,k]=s[i+1,i+k]$ 。

显然要用拓展 kmp 求出 $s[i:n]$ 与 $s$ 的 LCP，那么第三个转移的限制就是 $k\in [1,\min(z_{i+1},i)]$ ，这是 $O(n^2)$ ，用一个后缀 min 的树状数组维护转移可以做到 $O(n\log n)$ 。

反思：我们仅需要保留与状态计算有关的量，尽量做到所谓的状态 “最小化”，在场上自行设计状态的时候设计了二维状态（从哪里倍长过来），导致时间复杂度来到了 $O(n^3)$ 。在 DP 设计状态的时候应当需要保留和状态计算有关的量，这里倍长完全可以正解设一维转移过来。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e5+15,INF=0x3f3f3f3f3f3f3f3f;
int n,X,Y,Z,nxt[MN],f[MN];
string s;

struct BIT{
    int t[MN];

    BIT(){
        memset(t,0x3f,sizeof(t));
    }

    int lowbit(int x){return x&-x;}

    void modify(int x,int k){
        while(x){
            t[x]=min(t[x],k);
            x-=lowbit(x);
        }
    }

    int query(int x){
        int ret=INF;
        while(x<MN){
            ret=min(ret,t[x]);
            x+=lowbit(x);
        }
        return ret;
    }

}bit;

void qnxt(string s){
    int l=-1,r=-1;
    nxt[0]=n;
    for(int i=1;i<n;i++){
        if(i<r) nxt[i]=min(nxt[i-l],r-i);
        while(i+nxt[i]<n&&s[i+nxt[i]]==s[nxt[i]]) ++nxt[i];
        if(i+nxt[i]>r){
            l=i;
            r=i+nxt[i];
        }
    }
}

signed main(){
    #ifndef ONLINE_JUDGE
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    #endif
    cin>>s>>X>>Y>>Z;
    n=s.length();
    qnxt(s);
    for(int i=1;i<=n;i++){
        f[i]=min(bit.query(i),X*i);
        if(i%2==0&&nxt[i/2]>=i/2) f[i]=min(f[i],f[i/2]+Y);
        int r=i+min(nxt[i],i-1);
        bit.modify(r, f[i]+Y+Z);
    }
    cout<<f[n];

    return 0;
}

T4

CF1538E

啊哈，我已经在 GF 被骗过了，所以不会再骗啦，只需要计算跨段的贡献就可以了，合并时可能增加的 haha 数量只会在边界字符拼接产生。只需要记录开头和结尾的字符串，拼接的时候暴力模拟就可以了，常熟是 $5$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string lst;

struct Node{
    string ls,rs;
    int ans;

    Node(){
        ans=0,ls="",rs="";
    }

    Node(const string &st){
        ans=(st.find("haha"))!=string::npos;
        ls=st.substr(0,min(4ll,(int)st.length())),rs=st.substr(max(0ll,(int)st.length()-4));
    }

    friend Node operator +(const Node &x,const Node &y){
        Node ret=x;
        ret.ls+=y.ls;
        ret.rs+=y.rs;
        ret.ls=ret.ls.substr(0,min(4ll,(int)ret.ls.length()));
        ret.rs=ret.rs.substr(max(0ll,(int)ret.rs.length()-4));
        ret.ans+=y.ans;
        int rss=(x.rs.find("haha")!=string::npos),lss=((y.ls.find("haha"))!=string::npos),res=0;
        string st=x.rs+y.ls;
        for(int i=0;i<=(int)st.length()-4;i++){
            if(st.substr(i,4)=="haha") res++;
        }
        ret.ans+=res-rss-lss;
        return ret;
    }

};
map<string,Node> mp;

void solve(){
    cin>>n;
    string lst;
    for(int i=1;i<=n;i++){
        string x,y,z;
        string op,tmp;
        cin>>x>>op;
        if(op==":="){
            cin>>y;
            mp[x]=Node(y);
            lst=x;
        }else{
            cin>>y>>tmp>>z;
            mp[x]=mp[y]+mp[z];
            lst=x;
        }
    }
    cout<<mp[lst].ans<<'\n';
    mp.clear();
}

signed main(){
    freopen("haha.in","r",stdin);
    freopen("haha.out","w",stdout);
    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}