所有子序列的逆序对总和_一个数字的所有子串的总和

╰+哭是因爲堅強的太久メ 2023-03-05 12:38 80阅读 0赞

所有子序列的逆序对总和

**Problem statement:**

**问题陈述：**

Given an integer, ***S*** represented as a string, get the **sum of all possible substrings of this string**.

给定一个以字符串形式表示的整数***S*** ，得到该字符串**所有可能的子字符串的和** 。

**Input:**

**输入：**

A string ***S*** that representing the number.

代表数字的字符串***S。***

**Output:**

**输出：**

Print sum of all possible substrings as required result.

根据要求的结果打印所有可能的子字符串的总和。

**Constraints:**

**限制条件：**

1 <= T <= 100
    1 <= S <= 1012

**Example:**

**例：**

Input:
    
    1234
    326
    
    Output:
    1670
    395

**Explanation:**

**说明：**

For the first input 1234, 
    All possible substrings are
    1, 2, 3, 4, 12, 13, 23, 34, 123, 234, 1234
    Total sum = 1 + 2 + 3 + 4 + 12 + 23 + 34 + 123 + 234 + 1234 = 1670
    For the second input 326
    All possible substrings are
    3, 2, 6
    32, 26
    326
    Total sum=3+2+6+32+26+326= 395

**Solution Approach:**

**解决方法：**

The solution approach is by storing the substring sums to compute the exact next substring sum

解决方法是通过存储子字符串和以计算确切的下一个子字符串和

1.  Create dp\[n\]\[n\] to store substring sums;
    
    创建dp \[n\] \[n\]来存储子字符串和；
2.  Initialize sum=0 which will be our final result;
    
    初始化sum = 0，这将是我们的最终结果；
3.  Base case computation (single length substrings),
    
    基本案例计算(单长度子字符串)，
    
        for i=0 to n-1,n= string length
            dp[i][i]=s[i] -'0'; //s[i]-'0' gives the digit actually
            sum+=dp[i][i];
        end for
4.  Till now we have computed all single digit substrings,
    
    到现在为止，我们已经计算了所有个位数的子字符串，
    
        for substring length,len=2 to n
            for start=0 to n-len
                //so basically it's the substring s[start,end]
                int end=start+len-1; 
                dp[start][end]=dp[start][end-1]*10+s[end]-'0';  
                sum+=dp[start][end];
            end for
        end for
5.  Sum is the final result.
    
    总和是最终结果。

All the statements are self-explanatory except the one which is the fundamental idea of the entire storing process. That is the below one,

所有陈述都是不言自明的，只是整个存储过程的基本思想。 那是下一个，

dp[start][end]=dp[start][end-1]*10+s[end]-'0';

Let's check this with an example,

我们来看一个例子，

Say we are computing for string s="1234"
    At some stage of computing,
    Start=1, end= 3
    So
    Dp[start][end]=dp[start][end-1]*10+s[end]-'0'
    
    So basically we are computing value of substring s[start..end] 
    with help of already computed s[start,end-1]
    
    For this particular example
    s[start..end] ="234"
    s[start..end-1] ="23"
    
    Now, dp[1][3]=dp[1][2]*10+'4'-'0'
    
    So, assuming the fact that our algo is correct and thus dp[start][end-1] 
    has the correct value, dp[]1[2] would be 23 then
    So,
    dp[1][3]=23*10+'4'-'0=234
    and that's true
    So, here's the main logic
    Now how dp[1][2] is guaranteed to be correct can be 
    explored if we start filling the Dp table from the base conditions?

Let's start for the same example

让我们开始同样的例子

N=4 here

N = 4这里

So, we need to fill up a 4X4 DP table,

因此，我们需要填写4X4 DP表，

![Sum of all substrings of a number (1)][Sum of all substrings of a number _1]

After filling the base case,

装完基本外壳后，

![Sum of all substrings of a number (2)][Sum of all substrings of a number _2]

Now, I am computing for len=2

现在，我正在计算len = 2

Start=0, end=1

开始= 0，结束= 1

![Sum of all substrings of a number (3)][Sum of all substrings of a number _3]

Start=1, end=2

开始= 1，结束= 2

![Sum of all substrings of a number (4)][Sum of all substrings of a number _4]

Start=2, end=3

开始= 2，结束= 3

![Sum of all substrings of a number (5)][Sum of all substrings of a number _5]

For len =3

对于len = 3

Start=0, end=2

开始= 0，结束= 2

![Sum of all substrings of a number (6)][Sum of all substrings of a number _6]

Start=1, end=3

开始= 1，结束= 3

![Sum of all substrings of a number (7)][Sum of all substrings of a number _7]

Len=4

Len = 4

Start=0, end=3

开始= 0，结束= 3

![Sum of all substrings of a number (8)][Sum of all substrings of a number _8]

At each step we have summed up, so result is stored at sum.

在每一步我们都进行了总结，因此结果被存储在总和中。

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    void print(vector<int> a, int n)
    {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    
    long long int my(string s, int n)
    {
    
        long long int dp[n][n];
        long long int sum = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = s[i] - '0';
            sum += dp[i][i];
        }
    
        for (int len = 2; len <= n; len++) {
            for (int start = 0; start <= n - len; start++) {
                int end = start + len - 1;
                dp[start][end] = dp[start][end - 1] * 10 + s[end] - '0';
                sum += dp[start][end];
            }
        }
    
        return sum;
    }
    int main()
    {
        int t, n, item;
    
        cout << "enter the string: ";
        string s;
        cin >> s;
        
        cout << "sum of all possible substring is: " << my(s, s.length()) << endl;
    
        return 0;
    }

**Output:**

**输出：**

RUN 1:
    enter the string: 17678
    sum of all possible substring is: 29011
    
    RUN 2:
    enter the string: 326
    sum of all possible substring is: 395

> 翻译自: [https://www.includehelp.com/icp/sum-of-all-substrings-of-a-number.aspx][https_www.includehelp.com_icp_sum-of-all-substrings-of-a-number.aspx]

所有子序列的逆序对总和

[Sum of all substrings of a number _1]: /images/20230208/03f5977867484938b9381bdb12e3b4e6.png
[Sum of all substrings of a number _2]: /images/20230208/f6d9b6a58d454649a195e90b07d46645.png
[Sum of all substrings of a number _3]: /images/20230208/1c2c3a46e65e41b1a86063186572da0a.png
[Sum of all substrings of a number _4]: https://www.includehelp.com/icp/Images/sum-of-all-substrings-of-a-number-4.jpg
[Sum of all substrings of a number _5]: /images/20230208/da4148694e8b48849139c05ffd9ad781.png
[Sum of all substrings of a number _6]: /images/20230208/cc7badc6772b4d2daf8d1bde451f5566.png
[Sum of all substrings of a number _7]: /images/20230208/c5c21621276d4d94bebe8c658a743376.png
[Sum of all substrings of a number _8]: /images/20230208/ef5005cf494f4e708f15b1835f723674.png
[https_www.includehelp.com_icp_sum-of-all-substrings-of-a-number.aspx]: https://www.includehelp.com/icp/sum-of-all-substrings-of-a-number.aspx