严肃补一下上周周赛的题。

A、B略。

$Link$

C.小红的因子幂和

由于相乘后太大不方便运算，考虑分别处理。这里有两个方法。

1. 将$x,y$两个数分别分解质因数，再求出v的因子。

// 这是分解质因数用的函数
void p(ll x){//分解质因数和计算质因数的幂
    ll res=0;
    if(x%2==0){
        while(x%2==0){
            res++;
            x>>=1;
        }
        mp[2]+=res;
    }
    for(ll i=3;i*i<=x;i+=2){
        if(x%i==0){
            res=0;
            while(x%i==0){
                res++;
                x/=i;
            }
            mp[i]+=res;
        }
    }
    if(x>1)mp[x]++;
    return ;
}


//这是主函数中用于求v的因子的部分
for(auto x:mp){
    len=cnt;
    f(k,1,x.second){
        f(i,1,len){
            cnt++;
            a[cnt]=a[cnt-len]*x.first;
        }
    }
}

求v的所有因子的过程就是在一个只有1的集合中用分解出的质因子不断乘这个集合中的每个数并把新得到的数都加到这个集合里。

例如，$30$的质因子为$2,3,5$。

原集合为${1}$。

每个元素乘2之后得到{1,2}。

每个元素乘3之后得到{1,2,3,6}。

每个元素乘5之后得到{1,2,3,6,5,10,15,30}。

就得到了30的所有因子。

当质因数的幂大于$1$时，要注意只乘上这个质因数上次相乘得到的新数。

以$12$为例，$12$的质因子为$2,2,3$。

每个元素乘2之后得到{1,2}。

每个元素乘2之后得到{1,2,4}。

每个元素乘3之后得到{1,2,4,3,6,12}。

明显1这个操作不需要满足有序性，可以用$unordered\_map$存储来省个$map$的$log$。

2. 直接统计$x$和$y$的因子，再使用双重循环得到$v$的所有因子，要去重。

比较简单易懂，直接贴代码。

// 求数x的所有因子
vector<int> p(int x) {
    vector<int>res;
    for (int i=1;i*i<=x;i++) {
        if(x%i==0){
            res.push_back(i);
            if(i*i<x){
                res.push_back(x/i);
            }
        }
    }
    return res;
}

// 求v的所有因子
vector<ll> factors;
for (const auto& a:p(x)) {
    for (const auto& b:p(y)) {
        factors.push_back((ll)a*b);
    }
}
sort(factors.begin(), factors.end());//排序
factors.erase(unique(factors.begin(), factors.end()), factors.end());//去重

然后$d^d$就很简单了快速幂就可以。

‍

$AC Code:$

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const int MX =1e6+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll a[MX];
    ll n,T,k,m,x,ans,cnt;
    unordered_map<ll,ll>mp;

    ll ksm(ll x,ll y){
        ll res=1,tmp=x;
        while(y){
            if(y&1)res=tmp*res%mod;
            tmp=tmp*tmp%mod;
            y>>=1;
        }
        return res%mod;
    }

    void p(ll x){//分解质因数和计算质因数的幂
        ll res=0;
        if(x%2==0){
            while(x%2==0){
                res++;
                x>>=1;
            }
            mp[2]+=res;
        }
        for(ll i=3;i*i<=x;i+=2){
            if(x%i==0){
                res=0;
                while(x%i==0){
                    res++;
                    x/=i;
                }
                mp[i]+=res;
            }
        }
        if(x>1)mp[x]++;
        return ;
    }

    void work(){
        n=rd();m=rd();
        p(n);
        p(m);
        cnt=1;ll len;
        a[1]=1;
        for(auto x:mp){
            len=cnt;
            f(k,1,x.second){
                f(i,1,len){
                    cnt++;
                    a[cnt]=a[cnt-len]*x.first;
                }
            }
        }
        f(i,1,cnt){
            ans+=ksm(a[i]%mod,a[i]);//这里底数不%mod会少得105分
            ans%=mod;
        }
        cout<<ans<<endl;
        return ;
    }

    bool main(){
        T=1;
        while(T--)work();
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

D.小红的最佳区间

‍本质就是个区间加然后求最大值，差分计算即可，但是值域太大了要用$map$存。

（话说题面是不是有点问题，$[L,L+K]$不是长度为$K+1$的区间吗）

区间为$[l\\_i,r\\_i]$的区间如果想要被选上的话我们的$L$的取值范围就是$[l\\_i-K,r]$。

通过差分$mp[l-k]++,mp[r+1]--$然后前缀和求最大值就好了。

‍

$AC Code:$

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const int MX =1e6+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll a[MX];
    ll n,T,k,m,x,ans,cnt;
    map<ll,ll>mp;

    void work(){
        n=rd();k=rd();
        ll l,r;
        f(i,1,n){
            l=rd();r=rd();
            mp[l-k]++;
            mp[r+1]--;
        }
        ll res=0;
        ans=0;
        for(auto x:mp){
            res+=x.second;
            ans=max(ans,res);
        }
        cout<<ans<<endl;
        return ;
    }

    bool main(){
        T=1;
        while(T--)work();
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

E.小红的好矩阵

容易发现合法的矩阵中$0$和$1$的个数都是$3$的倍数，所以当$n$不是$3$的倍数时无解。

然后发现最后结果一定是固定的，只需要统计哪种结果需要的步数最小就好了。

第一种情况长这样：

$000111000...$

$111000111...$

第二种情况长这样：

$111000111...$

$000111000...$

第三种情况长这样：

$0X10X10X1...$

$0X10X10X1...$

由于中间两个位置只需要满足一个是0一个是1就好了，顺序不重要，并且每个块之间独立，需要每次都找操作数最小的方案，情况四也同理。

第四种情况长这样：

$1X01X01X0...$

$1X01X01X0...$

然后四种情况取最小值。

$AC Code:$

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const int MX =1e6+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll a[MX];
    ll n,T,k,m,x,ans,cnt;
    map<ll,ll>mp;
    string s1,s2;

    void work(){
        ll ans1=0,ans2=0,ans3=0,ans4=0,ans5=0,ans6=0;
        n=rd();
        cin>>s1>>s2;
        s1=" "+s1;
        s2=" "+s2;
        if(n%3){
            puts("-1");
            return ;
        }
        for(int i=1;i<=n;i+=3){
            if(i/3 & 1){
                ans1+=((s1[i]-'0')^0) + ((s1[i+1]-'0')^0) + ((s1[i+2]-'0')^0) + ((s2[i]-'0')^1) + ((s2[i+1]-'0')^1) + ((s2[i+2]-'0')^1);
                ans2+=((s1[i]-'0')^1) + ((s1[i+1]-'0')^1) + ((s1[i+2]-'0')^1) + ((s2[i]-'0')^0) + ((s2[i+1]-'0')^0) + ((s2[i+2]-'0')^0);
            }
            else{
                ans2+=((s1[i]-'0')^0) + ((s1[i+1]-'0')^0) + ((s1[i+2]-'0')^0) + ((s2[i]-'0')^1) + ((s2[i+1]-'0')^1) + ((s2[i+2]-'0')^1);
                ans1+=((s1[i]-'0')^1) + ((s1[i+1]-'0')^1) + ((s1[i+2]-'0')^1) + ((s2[i]-'0')^0) + ((s2[i+1]-'0')^0) + ((s2[i+2]-'0')^0);
            }
            ans3+=((s1[i]-'0')^0) + ((s1[i+2]-'0')^1) + ((s2[i]-'0')^0) + ((s2[i+2]-'0')^1) + min(((s1[i+1]-'0')^0) + ((s2[i+1]-'0')^1),((s1[i+1]-'0')^1) + ((s2[i+1]-'0')^0));
            ans4+=((s1[i]-'0')^1) + ((s1[i+2]-'0')^0) + ((s2[i]-'0')^1) + ((s2[i+2]-'0')^0) + min(((s1[i+1]-'0')^1) + ((s2[i+1]-'0')^0),((s1[i+1]-'0')^0) + ((s2[i+1]-'0')^1));
        }
        ans=ans1;ans=min(ans,ans2);ans=min(ans,ans3);
        ans=min(ans,ans4);
        cout<<ans<<endl;
        return ;
    }

    bool main(){
        T=1;
        while(T--)work();
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

F.小红的网格路径 II

今天睡了，看会儿乐理去，明天补。（咕咕咕）

‍

已严肃补上。

一开始以为是个简单DP然后发现$n,m$好大不能直接做，然后看到$k$的范围很小，考虑从$k$转移。

发现这个运动的本质就是一直右移，到达新的一列后可以上下随便移动，所以我们从每个障碍所在的列的方案总和数来考虑转移。

先考虑没有障碍物的情况，发现第一列的方案数为$1$，第二列为$n$，第三列为$n^2$，以此类推，这里可以使用快速幂。

然后分讨遇到障碍物后的情况，$sum$表示当前障碍物的前一列方案数的总和，$up$表示当前障碍物上方格子方案数的总和，$down$表示当前障碍物下方格子方案数的总和，不难得到$up=sum\*(x-1),down=sum\*(n-x)$。

然后还要处理两个障碍物在相邻两列的情况，这里需要分讨。

$AC Code:$

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const ll MX =1e5+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll n,T,k,m,ans,cnt;

    ll ksm(ll x,ll y){
        ll res=1;
        while(y){
            if(y&1)res=res*x%mod;
            x=x*x%mod;
            y>>=1;
        }
        return res;
    }
    pair<ll, ll> step(ll px,ll py,ll up,ll down,ll nx,ll ny){// 现在坐标，上下方案数，目标坐标
        ll gap=ny-py-1;
        if (gap>=1){//中间有空隙
            ll sum=(up*(px-1)+down*(n-px))%mod;//上下求和
            ll v=sum*ksm(n,gap-1)%mod;//向右蠕动
            return {v*(nx-1)%mod,v*(n-nx)%mod};//再分成上下两部分
        }
        else{//两个障碍物所在的列相邻，直接分讨
            if (nx<px){
                ll nu=up*(nx-1)%mod;
                ll nd=(up*(px-nx-1)+down*(n-px))%mod;
                return {nu,nd};
            }
            else if(nx==px){
                ll nu=up*(px-1)%mod;
                ll nd=down*(n-px)%mod;
                return {nu,nd};
            }
            else {
                ll nu=(up*(px-1)+down*(nx-px-1))%mod;
                ll nd=down*(n-nx)%mod;
                return {nu,nd};
            }
        }
    }

    void work(){
        n=rd();m=rd();k=rd();
        vector<pair<ll,ll>>a(k);
        f(i,0,k-1){
            a[i].second=rd();
            a[i].first=rd();
        }
        sort(a.begin(),a.end());//因为默认按第一关键字排序所以反着存
        if (!k) {
            cout<<ksm(n,m-1)<<'\n';
            return ;
        }
        ll x=a[0].second,y=a[0].first;
        ll up,down;
        if(y==1) {
            up=1;
            down=0;
        }
        else{
            ll v=ksm(n,y-2);
            up=v*(x-1)%mod;
            down=v*(n-x)%mod;
        }

        ll px=x,py=y;
        f(i,1,k-1){
            ll nx=a[i].second, ny=a[i].first;
            auto [nu,nd]=step(px,py,up,down,nx,ny);
            up=nu;
            down=nd;
            px=nx;
            py=ny;
        }
        if(py==m){//障碍物在最后一列，只有下面部分合法
            ans=down;
        }
        else{
            ll sum=(up*(px-1)+down*(n-px))%mod;
            ans=sum*ksm(n,m-py-1)%mod;
        }
        cout<<ans<<'\n';
        return ;
    }

    bool main(){
        T=1;
        while(T--)work();
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

这是做题记录的第一篇文章，希望自己以后做题再勤快一下。

我看我更史书的速度比更新这个的速度快多了