{"id":22,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-07\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-07","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-07\/","title":{"rendered":"2020-09-07"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2564&pid=7<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n

You are working with a strange text editor for texts consisting only of open and close parentheses. The editor accepts the following three keys as editing commands to modify the text kept in it.<\/p>\n

\u00b7\u2018(\u2019 appends an open parenthesis (\u2018(\u2019) to the end of the text.
\u00b7\u2018)\u2019 appends a close parenthesis (\u2018)\u2019) to the end of the text.
\u00b7\u2018-\u2019 removes the last character of the text.
A balanced string is one of the following.<\/p>\n

\u00b7\u201c()\u201d
\u00b7\u201c(X)\u201d where X is a balanced string
\u00b7\u201cXY\u201d where both X and Y are balanced strings
Initially, the editor keeps an empty text. You are interested in the number of balanced substrings in the text kept in the editor after each of your key command inputs. Note that, for the same balanced substring occurring twice or more, their occurrences should be counted separately. Also note that, when some balanced substrings are inside a balanced substring, both the inner and outer balanced substrings should be counted.<\/p>\n

<\/a>\u8f93\u5165<\/h6>\n

The input consists of a single test case given in a line containing a number of characters, each of which is a command key to the editor, that is, either \u2018(\u2019, \u2018)\u2019, or \u2018-\u2019. The number of characters does not exceed 200 000. They represent a key input sequence to the editor.<\/p>\n

It is guaranteed that no \u2018-\u2019 command comes when the text is empty.<\/p>\n

<\/a>\u8f93\u51fa<\/h6>\n

Print the numbers of balanced substrings in the text kept in the editor after each of the key command inputs are applied, each in one line. Thus, the number of output lines should be the same as the number of characters in the input line.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n

\u3010\u6837\u4f8b1\u3011
(()())\u2014)
\u3010\u6837\u4f8b2\u3011
()\u2013()()—-)(()()))<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n

\u3010\u6837\u4f8b1\u3011
0
0
1
1
3
4
3
1
1
2
\u3010\u6837\u4f8b2\u3011
0
1
0
0
0
1
1
3
1
1
0
0
0
0
0
1
1
3
4
4<\/p>\n

<\/a>\u89e3\u6790<\/h6>\n

DP\u52a8\u6001\u89c4\u5212+\u5806\u6808+\u79bb\u6563\u5316\u5904\u7406<\/p>\n

#include<\/span> <\/span><\/span>\n\nusing<\/span> namespace<\/span> std;<\/span>\nchar<\/span> a[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nstack<<\/span>int<\/span>><\/span>w;<\/span>\nint<\/span> dp[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> flag[<\/span>300500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>a+<\/span>1<\/span>)<\/span>;<\/span>\n    long<\/span> long<\/span> sum=<\/span>0<\/span>;<\/span>\n    long<\/span> long<\/span> s=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>a[<\/span>i]<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'('<\/span>)<\/span>\n        {<\/span>\n            s++<\/span>;<\/span>\n            w.<\/span>push<\/span>(<\/span>s)<\/span>;<\/span>\n            dp[<\/span>s]<\/span>=<\/span>flag[<\/span>s]<\/span>=<\/span>0<\/span>;<\/span>\n        }<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>')'<\/span>)<\/span>\n        {<\/span>\n            s++<\/span>;<\/span>\n            if<\/span>(<\/span>!<\/span>w.<\/span>empty<\/span>(<\/span>)<\/span>)<\/span>\n            {<\/span>\n                int<\/span> u=<\/span>w.<\/span>top<\/span>(<\/span>)<\/span>;<\/span>\n                w.<\/span>pop<\/span>(<\/span>)<\/span>;<\/span>\n                dp[<\/span>s]<\/span>=<\/span>dp[<\/span>u-<\/span>1<\/span>]<\/span>+<\/span>1<\/span>;<\/span>\n                flag[<\/span>s]<\/span>=<\/span>u;<\/span>\n                sum+<\/span>=<\/span>dp[<\/span>s]<\/span>;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                dp[<\/span>s]<\/span>=<\/span>flag[<\/span>s]<\/span>=<\/span>0<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'-'<\/span>)<\/span>\n        {<\/span>\n            sum-<\/span>=<\/span>dp[<\/span>s]<\/span>;<\/span>\n            while<\/span>(<\/span>!<\/span>w.<\/span>empty<\/span>(<\/span>)<\/span>&&<\/span>w.<\/span>top<\/span>(<\/span>)<\/span>>=<\/span>s)<\/span>\n                w.<\/span>pop<\/span>(<\/span>)<\/span>;<\/span>\n            if<\/span>(<\/span>flag[<\/span>s]<\/span>!=<\/span>0<\/span>)<\/span>\n                w.<\/span>push<\/span>(<\/span>flag[<\/span>s]<\/span>)<\/span>;<\/span>\n            s--<\/span>;<\/span>\n        }<\/span>\n        printf<\/span>(<\/span>\"%lldn\"<\/span>,<\/span>sum)<\/span>;<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n
It\u2019s easy for ACMer to calculate A^X mod P. Now given seven integers n, A, K, a, b, m, P, and a function f(x) which defined as following.
 f(x) = K, x = 1
 f(x) = (a*f(x-1) + b)%m , x > 1<\/p>\n
Now, Your task is to calculate
 ( A^(f(1)) + A^(f(2)) + A^(f(3)) + \u2026 + A^(f(n)) ) modular P.<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
In the first line there is an integer T (1 < T <= 40), which indicates the number of test cases, and then T test cases follow. A test case contains seven integers n, A, K, a, b, m, P in one line.
 1 <= n <= 10^6
 0 <= A, K, a, b <= 10^9
 1 <= m, P <= 10^9<\/p>\n
<\/a>\u8f93\u51fa<\/h6>\n
For each case, the output format is \u201cCase #c: ans\u201d.
 c is the case number start from 1.
 ans is the answer of this problem.<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
2\n3 2 1 1 1 100 100\n3 15 123 2 3 1000 107\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
Case #1: 14\nCase #2: 63\n<\/code><\/pre>\n
\u53c2\u7167\u4e8e
 https:\/\/blog.csdn.net\/Little_boy_z\/article\/details\/80042689<\/a><\/p>\n
#include<\/span> <\/span><\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> unsigned<\/span> long<\/span> long<\/span> ll;<\/span>\nint<\/span> n,<\/span>A,<\/span>K,<\/span>a,<\/span>b,<\/span>m,<\/span>p;<\/span>\nll dp1[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll dp2[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> db<\/span>(<\/span>)<\/span>\n{<\/span>\n    dp1[<\/span>0<\/span>]<\/span>=<\/span>dp2[<\/span>0<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n    dp1[<\/span>1<\/span>]<\/span>=<\/span>A%<\/span>p;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>2<\/span>;<\/span>i<=<\/span>100000<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        dp1[<\/span>i]<\/span>=<\/span>(<\/span>dp1[<\/span>i-<\/span>1<\/span>]<\/span>*<\/span>dp1[<\/span>1<\/span>]<\/span>)<\/span>%<\/span>p;<\/span>\n    }<\/span>\n    dp2[<\/span>1<\/span>]<\/span>=<\/span>dp1[<\/span>100000<\/span>]<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>2<\/span>;<\/span>i<=<\/span>100000<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        dp2[<\/span>i]<\/span>=<\/span>(<\/span>dp2[<\/span>i-<\/span>1<\/span>]<\/span>*<\/span>dp2[<\/span>1<\/span>]<\/span>)<\/span>%<\/span>p;<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t;<\/span>\n    cin>><\/span>t;<\/span>\n    for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>t;<\/span>j++<\/span>)<\/span>\n    {<\/span>\n        cin>><\/span>n>><\/span>A>><\/span>K>><\/span>a>><\/span>b>><\/span>m>><\/span>p;<\/span>\n        cout<<<\/span>\"Case #\"<\/span><<<\/span>j<<<\/span>\": \"<\/span>;<\/span>\n        ll ans=<\/span>0<\/span>;<\/span>\n        ll ans2=<\/span>K;<\/span>\n        db<\/span>(<\/span>)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            ans+<\/span>=<\/span>dp1[<\/span>ans2%<\/span>100000<\/span>]<\/span>*<\/span>dp2[<\/span>ans2\/<\/span>100000<\/span>]<\/span>;<\/span>\n            ans%<\/span>=<\/span>p;<\/span>\n            ans2=<\/span>(<\/span>ans2*<\/span>a+<\/span>b)<\/span>%<\/span>m;<\/span>\n        }<\/span>\n        cout<<<\/span>ans%<\/span>p<<<\/span>endl;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-22","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/22","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=22"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/22\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=22"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=22"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=22"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
http:\/\/icpc.upc.edu.cn\/problem.php?cid=2573&pid=2<\/a><\/p>\n