百度2021校招笔试真题

1、后缀变换

【题目描述】
牛牛定义一种字符串操作为: 对于任意字符串S,可以将其划分为两个非空子串x和y且满足S=xy，通过交换x和y子串的位置得到新字符串W且满足W=yx.例如对于字符串S="helloworld"，将其划分为两个部分x="hello"和y="world",经过操作后得到新字符串W="worldhello"。
在给定初始字符串S和结束字符串T以及进行操作次数k,问有多少种不同的操作方案使得将S转化成T？因为答案很大，所以需要模上1000000007后输出。
两种操作方案被视为不同当且仅当存在第i次操作时刻(1≤i≤k)，前者得到两部分子串为x1和y1，后者得到两部分子串为x2和y2时, x1≠x2成立。
输入描述：
第一行输入一个仅由小写字母构成的字符串S
第二行输入一个仅由小写字母构成的字符串T
第三行输入操作次数k
2≤|S|=|T|≤1000
1≤k≤100000
输出描述：
输出一个整数表示答案
输入样例：
aaca
caaa
2
输出样例：
2
说明：
"aaca" - "aaac" - "caaa"
"aaca" - "acaa" - "caaa"

【解题思路】
S串首尾相连转换成环的形式,那么对于每次操作的本质就是将下-轮起点转移到除当前的其他位置。考虑设dp[i[j]表示在第i次操作时处于环上第j个节点的方案，转移就是将dp[i-1][j]的值转移到除j以外的其他位置，直接修改复杂度是O(kn2),考虑到只有一个位置不被修改，将转移转化成全局修改以及单点修改两个部分，然后在O(nk)的复杂度内解决问题，进一步优化转移可以发现能将dp求解复杂度降为O(k)。对于最后答案的计算，将T串在S串上确定起点位置，然后将dp所得到对应起点的值求和即可。

【参考代码】
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define link(x) for (edge *j = h[x]; j; j = j->next)
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, r, l) for (int i = r; i >= l; i--)
const int MAXN = 3e5 + 10;
const double eps = 1e-8;
const int mod = 1e9 + 7;
#define ll long long
using namespace std;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
int n, k;
char s1[MAXN];
char s2[MAXN];
int dp2[2][MAXN];
int dp1[2];
int main() {
    scanf("%s", s1 + 1);
    n = strlen(s1 + 1);
    scanf("%s", s2 + 1);
    k = read();
    int now = 0;
    dp1[now] = 1;
    inc(i, 2, n) dp2[now][i] = 1;
    inc(i, 1, k) {
        inc(j, 1, n) {
            int x = (dp1[now] - dp2[now][j] + mod) % mod;
            dp1[now ^ 1] += x;
            dp1[now ^ 1] %= mod;
            dp2[now ^ 1][j] += x;
            dp2[now ^ 1][j] %= mod;
        }
        dp1[now] = 0;
        inc(j, 1, n) dp2[now][j] = 0;
        now ^= 1;
    }
    inc(i, n + 1, 2 * n) s1[i] = s1[i - n];
    ll ans = 0;
    inc(i, 1, n) {
        bool flag = 0;
        inc(j, 1, n) if (s1[i + j - 1] != s2[j]) {
            flag = 1;
            break;
        }
        if (!flag)
            ans += (dp1[now] - dp2[now][i] + mod) % mod, ans %= mod;
    }
    printf("%lld\n", ans);
    return 0;
}

2、选角色

【题目描述】 牛牛任职于一家演艺公司，这一天，他率领着一