时间戳

首页 > 解决方案 > 解决方案中的值 x 表示什么？

c++ - 解决方案中的值 x 表示什么？

问题描述

问题陈述：：

给定一个由大写字母组成的字符串“s”，即从“A”到“Z”。你的任务是找出有多少长度等于 's' 的字符串 't'，也由大写字母组成，满足以下条件：

  • 字符串 't' 在字典上比字符串 's' 大。
  • 当你以相反的顺序写's'和't'时，'t'仍然比's'大。

找出这样的字符串 't' 的数量。由于答案可能非常大，取模 10^9 + 7。

解决方案：：：

#include <bits/stdc++.h>
using namespace std;
#define m 1000000007

int main() {
    // your code goes here
    string s;cin>>s;
    long long int x=0,ans=0;
    int n=s.size();
    for(int i=0;i<n; i++){
        ans+=((x+1)%m)*('Z'-s[i]);
        x= ((26*x)%m)+('Z'-s[i]);
    }
    cout<<ans%m;
    return 0;
}

我无法理解变量的意义x。
它实际上代表什么？

标签： c++algorithmlogic

解决方案

Let D[i]be 'Z'-s[i]- 比较大于的可能字符数s[i]（始终使用从零开始的索引）。

让是长度按字典顺序大于X[i]的字符串的数量。显然，- 一个空字符串小于任何其他字符串。对于长度大于的字符串，必须满足以下两个条件之一：isX[0] == 0i+1s

  • 它的前缀长度i大于s，最后一个字符可以是任何字符。有X[i]*26这样的字符串。
  • 它的长度前缀i正好等于对应的前缀s，并且最后一个字符大于s[i]。有D[i]这样的字符串。

把这个放在一起，X[i+1] = X[i]*26 + D[i]。

在程序中，变量x代表序列——循环迭代开始时X等于，结束时更新为；在这两种情况下，减少模数以避免溢出。X[i]X[i+1]m

现在，这对答案有何贡献？t考虑一个满足问题陈述中两个条件的字符串。让我们k成为最后（最右边）的位置，其中t[k] > s[k]; 对于所有职位z > k，t[z] == s[z]. 这个位置k必须存在，reverse(t) > reverse(s)才能持有。换句话说，当s和t被反向读取时，它们可能有几个（可能为零）共同的字符，后跟一个字符 fromt大于一个字符 from s。

进一步地，t长度的前缀k必须大于或等于对应的前缀s，t > s才能成立。换句话说，当s和t被向前读取时，之前的所有字符k都相等，或者其中有一些较早的字符t大于s.

设Y[k]为 a) 满足问题条件的字符串的数量，并且 b)k作为最右边的位置t和s不同；也就是最右边的位置t[k] > s[k]。很容易看出这一点Y[k] = (X[k] + 1) * D[k]。实际上，存在X[k]+1大于 ( X[k]) 或等于 ( 1) 的相应前缀的可能前缀s。它们中的任何一个都可以跟任何D[k]大于 的字符，s[k]然后跟一个与 的对应后缀完全相等的后缀s。

t最后，满足问题条件的字符串总数是Y[i]所有位置的总和i。

在程序中，变量ans累加的和Y[i]，减少的模m，以避免溢出。

推荐阅读