牛客多校第四场

补题进度: 5/8(10)
自闭了啊，感觉脑子不行了

---

A

题意

给一个字符串s，由0,1,2组成，每一秒都会在1后面加一个0, 2后面加一个1，并且第一个字符消失，问多少秒钟s变为空。答案%$（10^9+7）$ , $(|s|≤2·10^6)$

题解

分析可得出

• 考虑0，直接删掉即可 ，1次
• 考虑1，假设前面操作了x次，那么删除它以及它生成的1所需要 $2·x+2$次
• 考虑2，暴力打表，观察可得 $3·2^{x+1}$

直接快速幂从左向右递推的话相当于很多个log相乘肯定不行

考虑欧拉函数降幂

一个经典的问题：
$$a^{b^c……..} \% p$$

可用欧拉函数降幂解决

$$a^b=a^{ b \ \% \ \phi(p) } \%p \ \ \ \ \ (gcd(a,p)=1)$$

但需要不断模数是变化的， 即不断的迭代 $phi(…phi(mod))$

考虑欧拉降幂公式，$mod$是从小到大的，即后面模数大于前面的模数，预处理$phi(…phi(mod))$,反向迭代$mod$即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+100;
const int mod = 1e9+7;
char s[maxn];
int n,T;

int p[maxn];

ll quick_pow(ll a, ll b, ll mod){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

int phi(int n){
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n && n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0)
                n/=i;

        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

void init(){  // 预处理phi
    p[0]=mod;
    int k=1;
    while( k < 30){
        p[k] = phi(p[k-1]);
        k++;
    }
    for(int i=k;i<maxn;i++)
        p[i]=1;
}

int main(){
    init();
    scanf("%d", &T);
    while(T--){
        scanf("%s", s+1);
        ll ans=0;
        int len=strlen(s+1);
        int cnt=0;
        for(int i=1;i<=len;i++)
            if(s[i]=='2') cnt++;
        for(int i=1;i<=len;i++){
            if(s[i]=='1') ans= (2*ans+2)%p[cnt];
            else if(s[i]=='0')  ans=(ans+1)%p[cnt];
            else{
                --cnt;
                 ans = ( (3 * quick_pow(2, (ans+1)%p[cnt], p[cnt]))%p[cnt] - 3 + p[cnt] ) % p[cnt];
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

---

B

题意

给一个大区间$[1,m]$, n个小区间$[l_i, r_i]$,每个小区间都有一个权重$w_i$, 现要从这n个区间选择几个小区间使得覆盖[1,m]，每个位置的权重$s_i$等于这个位置上小区间的权重$w_i$的和，问所有$s_i$最大的最小的值

题解

待补

dp+线段树

---

C

题意

$$a_n=0 (n=1)$$
$$a_n=a_{n/2}+(-1)^{n(n+1)/2} (n>=2)$$
问
$$\sum_{i=1}^{n} |a_i|$$
答案%$（10^9+7）$，$(T≤10^5, n≤10^{18})$

题解

待补
找规律

---

D

题意

给一个$n$，输出一个只由$-1,0,1$构成的每一行的和以及每一列的和都不相同，行和列也不相同，$n·n$的矩阵，不存在$-1$

题解

找几个数玩玩发现

• n为奇数不存在
• n为偶数瞎构造构造

  1  1  1  1
  0 -1  1  1
  0  0  1  1
  0  0  0 -1

---

E

题意

平⾯上n个点，每个点出现概率是$p_i$，⼀个点被⽀配，当且仅当存在⼀个点在其右上⽅, 求期望被⽀配的点数。$(n ≤ 1e5)$

题解

待补
概率dp

---

F

模拟即可

---

G

题意

给一个长度为n序列的a， 问你删除m后，出现次数最多(不能出现次数最多的数大于一个)且最大的数是几，不存在-1

题解

暴力枚举每个数，check每个数要最少删除的数量

check方法: priority_queue，从大最小弹即可

pq 默认从大到小弹出
pq<int> = pq<int, vector<int>, greater<int> >; 从小到大
pq<int, vector<int>, less<int> >; 从大到小

---

H

题意

给一个字符串s，问有多少对(i,j),交换$(s_i, s_j)$后，s是两个回文串

题解

---

I

留坑

---

J

题意

给一个长度为 $n$ 的$hash$表，位置为$[0，n-1]$， $h(x)=x \% n$, 若这个位置已经被其他的数占据，则位置$+1$， 直至找到合法的位置，现给出$hash$表，问你原来的字典序最小的序列，$hash$表不合法输出$-1$

题解

这种有明显的先后关系，可以转化为有向图后拓扑排序，一个很直白的建边方式是，一个点和它$[h(x)\% n ，i]$，之间的所有点建边，这样最坏情况下是$n^2$的
，可以用线段树优化建图后跑拓扑排序即可。

解法二：并查集

考虑每个点安放顺序，一个点应安放$[h(x)\% n ，i]$之后，考虑并查集，每个点安放好后把这个点的$father$设为右边一个点的$father$，这样原本不能建的点会变的合法，不断check下一个位置即可，那么这个点合法安放的条件是$father[i]=father[a[i]\%n]$, 字典序最小的话用优先队列优先弹出小的值即可。

Trick：注意每次的下一个位置不一定是(pos+1)%n， 而是findfa((pos+1)%n)

#include<bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
const int maxn = 2e5+100;
const int mod = 1e9+7;
int n,T;

int fa[maxn], a[maxn], ans[maxn];
bool vis[maxn];

int findfa(int x){
    if(fa[x]==x) return x;
    else return fa[x]=findfa(fa[x]);
}

void init(){
    memset(vis, false, sizeof(vis));
    for(int i=0;i<maxn;i++)
     fa[i]=i;

}

struct node{
    int a, pos;
    friend bool operator < (node x, node y){
        return x.a > y.a;
    }
};

int main()
{
    scanf("%d",&T);
    while(T--){
        init();
        priority_queue<node>q;
        scanf("%d",&n);
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d", &a[i]);
            if(a[i]%n==i && a[i]!=-1) q.push({a[i], i}), vis[i]=1;
            if(a[i]!=-1) ++cnt;
        }
        int num=0;
        while(sz(q))
        {
            node now = q.top();
            q.pop();
            ans[++num]=now.a;
            fa[findfa(now.pos)] = findfa((now.pos+1)%n);
            int k=fa[now.pos];
            if(findfa(a[k]%n) == k && (!vis[k]) && a[k]!=-1)
            {
                q.push({a[k], k});
                vis[k]=1;
            }
        }
        if(cnt==0)
            cout<<endl;
        else if(num == cnt){
            for(int i=1;i<=num;i++){
                printf("%d%c", ans[i], i==num?'\n':' ');
            }
        }
        else
            cout<<"-1"<<endl;
    }
}

---