第20屆上海大學(xué)程序設(shè)計(jì)聯(lián)賽春季賽（同步賽） 簽到題6題

文章目錄

A 如何才能穿過傳送門

C 古老的恩尼格瑪機(jī)

D 并不智能的卡牌 AI

G 多吃蘑菇

H 差不多得了

I 數(shù)學(xué)題真難啊

題號(hào) 標(biāo)題 已通過代碼 通過率 我的狀態(tài)

A 如何才能穿過傳送門 點(diǎn)擊查看 537/2713 通過

B 逃離魔爪 點(diǎn)擊查看 47/341 未通過

C 古老的恩尼格瑪機(jī) 點(diǎn)擊查看 709/1004 通過

D 并不智能的卡牌 AI 點(diǎn)擊查看 832/2679 通過

E 林蔭小徑 點(diǎn)擊查看 3/10 未通過

F 到底是多少分啊 點(diǎn)擊查看 13/51 未通過

G 多吃蘑菇 點(diǎn)擊查看 229/926 通過

H 差不多得了 點(diǎn)擊查看 670/1300 通過

I 數(shù)學(xué)題真難啊 點(diǎn)擊查看 174/306 通過

A 如何才能穿過傳送門

鏈接：https://ac.nowcoder.com/acm/contest/33785/A

來源：?？途W(wǎng)

題目描述

你走入了一條布滿了傳送門和墻的小巷。

小巷可以視為一條位于XX 軸上的線段，從 00 點(diǎn)開始，到 nn 點(diǎn)結(jié)束。你一次只能向左或者向右走一格。在小巷里面有若干對(duì)傳送門，你不可以越過傳送門而不進(jìn)行傳送。你從傳送門的左側(cè)一格進(jìn)入，會(huì)從對(duì)應(yīng)傳送門出來并且下一次只能往右走；從傳送門的右側(cè)一格進(jìn)入，會(huì)從對(duì)應(yīng)傳送門出來并且下一次只能往左走。同時(shí)中間現(xiàn)在有若干面墻，你不能走到墻上。保證所有的墻和傳送門不會(huì)重合。你現(xiàn)在位于 00 點(diǎn)，請(qǐng)問你能否到達(dá) nn 點(diǎn)？

輸入描述:

第一行包含三個(gè)整數(shù) nn, mm, qq (0 \le n, m, q \le 1000, 2 \times m + q \le n)(0≤n,m,q≤1000,2×m+q≤n) ，分別表示小巷的長(zhǎng)度、傳送門的對(duì)數(shù)和墻的數(shù)量。

接下來 mm 行，第 ii 行包含兩個(gè)整數(shù) x_ix

i

, y_iy

i

(0 \lt x_i \lt y_i \lt n)(0

i

i

接下來一行包含 qq 個(gè)整數(shù) a_j (0 \lt a_j \lt n)a

j

(0

j

輸出描述:

如果你能能穿過小巷（即到達(dá)n點(diǎn)），則在一行輸出 “YES”，否則輸出 “NO”（不包含引號(hào)，不區(qū)分大小寫）。

示例1

輸入

復(fù)制

10 2 2

1 3

4 6

2 5

輸出

復(fù)制

YES

示例2

輸入

復(fù)制

100 0 1

50

輸出

復(fù)制

NO

思路：

因?yàn)槟悴豢梢栽竭^傳送門而不進(jìn)行傳送，所以直接往右走，遇到傳送門就傳送，然后再往右走就可以了。遇到墻就掛了。

#include using namespace std; const int maxn = 1010; int mp[maxn], no[maxn]; int main(){ memset(mp,-1,sizeof(mp)); int n, m, q; cin>>n>>m>>q; for(int i = 1; i <= m; i++){ int x, y; cin>>x>>y; mp[x] = y, mp[y] = x; } for(int i = 1; i <= q; i++){ int x; cin>>x; no[x] = 1; } int ok = 1; for(int i = 0; i <= n; i++){ if(mp[i]!=-1)i = mp[i]; else if(no[i]==1)ok = 0; } if(ok)cout<<"YES\n"; else cout<<"NO\n"; return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

開始想復(fù)雜了，寫了個(gè)dfsWA了，過了94%的點(diǎn)

//dfs, 94% #include using namespace std; const int maxn = 1050; int n, m, q; vectorG[maxn]; int no[maxn]; int ans, vis[maxn]; void dfs(int u, int fa){ // cout<2 && (to==u+1 || to==u-1))continue; if(fau+1 && to==u+1 )continue; // cout<<"xxx"<>n>>m>>q; for(int i = 0; i < n; i++){ G[i].push_back(i+1); if(i!=0)G[i].push_back(i-1); } for(int i = 1; i <= m; i++){ int x, y; cin>>x>>y; G[x].push_back(y); // G[y].push_back(x); } for(int i = 1; i <= q; i++){ int x; cin>>x; no[x] = 1; } dfs(0, 0); if(ans)cout<<"YES\n"; else cout<<"NO\n"; return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

然后改成bfs過的

//bfs, ac #include using namespace std; #define PII pair const int maxn = 1010; PII b[maxn]; int a[maxn]; int n, m, q; int vis[maxn][2],no[maxn],to[maxn]; struct node{ int p,cur;}; int main(){ cin>>n>>m>>q; for(int i = 1; i <= m; i++) { int x,y; cin>>x>>y; to[x] = y; to[y] = x; } for(int i = 1; i <= q; i++) { cin>>a[i]; no[a[i]] = 1; } queueq; q.push({0,0}); while(q.size()){ node now = q.front();q.pop(); if(now.p == n){ cout<<"YES\n"; return 0; } if(no[now.p])continue; if(now.p < 0 || now.p > n)continue; if(now.cur != 0) { if(now.cur == 1){ if(vis[now.p][1])continue; if(to[now.p+1]) q.push({to[now.p+1],1}); else q.push({now.p+now.cur,0}); vis[now.p][1] = 1; } else{ if(vis[now.p][0])continue; if(to[now.p-1]) q.push({to[now.p-1],-1}); else q.push({now.p + now.cur,0}); vis[now.p][0] = 1; } }else{ if(vis[now.p][0]); else if(to[now.p-1])q.push({to[now.p-1],-1}); else q.push({now.p-1,0}); if(vis[now.p][1]); else if(to[now.p+1])q.push({to[now.p+1],1}); else q.push({now.p+1,0}); vis[now.p][1] = vis[now.p][0] = 1; } } cout<<"NO"; return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

C 古老的恩尼格瑪機(jī)

鏈接：https://ac.nowcoder.com/acm/contest/33785/C

來源：?？途W(wǎng)

題目描述

你順利入了城，看見了古老的恩尼格瑪機(jī)。

恩尼格瑪機(jī)（Enigma Machine）是第二次世界大戰(zhàn)期間德國(guó)使用的信息加解密設(shè)備，其每次 Reflector 過程定義如下：

輸入一個(gè)大寫字母;

根據(jù)轉(zhuǎn)換關(guān)系，輸出該字母對(duì)應(yīng)的輸出字母。

其中的轉(zhuǎn)換關(guān)系通過 1313 個(gè)字符對(duì)（共 2626 個(gè)字母，其中兩兩不重復(fù)）給出。

以下是一次 Reflector 過程的舉例：

對(duì)輸入的一段字符串 “ABC“，假定存在轉(zhuǎn)換關(guān)系 A-B 和 C-D，則其對(duì)應(yīng)的輸出字符串為 ”BAD’'。

你需要實(shí)現(xiàn)一個(gè) Reflector 模塊，在給定一系列轉(zhuǎn)換關(guān)系的情況下，對(duì)每個(gè)輸入的字符串，給出其對(duì)應(yīng)的輸出字符串。

輸入數(shù)據(jù)保證：

每個(gè)字符串長(zhǎng)度 |s|\leq 255∣s∣≤255；

所有字符串總長(zhǎng)度 \sum |s| \leq 10^5∑∣s∣≤10

5

；

所有字符串中僅包含大寫字母。

輸入描述:

第一行包含 2626 個(gè)不重復(fù)大寫字母，以空格分隔，其中第 2i-12i?1 和 2i2i 個(gè)字母表示一對(duì)轉(zhuǎn)換關(guān)系 (1 \leq i \leq 131≤i≤13)。

第二行包含一個(gè)整數(shù) kk (1 \leq k \leq 10^51≤k≤10

5

)，表示輸入的字符串個(gè)數(shù)。

接下來一行包含 kk 個(gè)由空格分隔的非空字符串。

輸出描述:

僅一行，表示每個(gè)輸入字符串對(duì)應(yīng)的輸出結(jié)果，字符串間以空格分隔。

示例1

輸入

復(fù)制

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

4

ABC QWQ HELLO WORLD

輸出

復(fù)制

BAD RXR GFKKP XPQKC

思路：

直接開個(gè)映射存起來，輸出即可。

#include using namespace std; int e[500]; int main(){ for(int i = 1; i <= 13; i++){ char a, b; cin>>a>>b; e[a] = b; e[b] = a; } int k; cin>>k; for(int i = 0; i < k; i++){ string s; cin>>s; for(char ch : s){ cout<<(char)e[ch]; } cout<<" "; } return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

D 并不智能的卡牌 AI

鏈接：https://ac.nowcoder.com/acm/contest/33785/D

來源：?？途W(wǎng)

題目描述

公元 2202 年，你漫步在元宇宙的世界中，遇見了守著 SHU 城門的 Foxity AI。Foxity AI 正被一個(gè)翻牌問題困擾著，并請(qǐng)求你幫幫他。

Foxity AI 面前存在 mm 張背面朝上的卡牌。在一步里，F(xiàn)oxity AI 可以將至多 nn 張牌翻面，F(xiàn)oxity AI 想知道他能不能通過若干步操作，使面前的所有卡牌都變?yōu)檎娉系臓顟B(tài)（即不存在牌背面朝上）。如果能的話，請(qǐng)告訴他至少需要多少步。

輸入描述:

輸入僅一行，包含兩個(gè)整數(shù) mm, nn (0\le m,n \le 10^8)(0≤m,n≤10

8

) ，含義如題目背景所述。

輸出描述:

如果 Foxity AI 能做到將面前的所有卡牌都變?yōu)檎娉系臓顟B(tài)，則在一行一個(gè)整數(shù)，表示 Foxity AI 最少需要的步數(shù)；否則在一行輸出 -1 ,表示不能做到。

示例1

輸入

復(fù)制

8 6

輸出

復(fù)制

2

示例2

輸入

復(fù)制

8 0

輸出

復(fù)制

-1

示例3

輸入

復(fù)制

0 8

輸出

復(fù)制

0

思路：

直接m/n即可，注意特判一下n=m=0的情況

#include using namespace std; int main(){ int m, n; cin>>m>>n; if(n==0 && m==0){ cout<<"0\n"; return 0; } if(n==0){ cout<<"-1\n"; return 0; } int x = m/n; if(m%n!=0)x++; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

G 多吃蘑菇

鏈接：https://ac.nowcoder.com/acm/contest/33785/G

來源：牛客網(wǎng)

題目描述

Crazycth 看見了穿過傳送門的你，他邀請(qǐng)你幫助他的室友。

Crazycth 的室友經(jīng)常深夜看馬里奧錄播，現(xiàn)在他正夢(mèng)到自己被庫(kù)巴追，被迫逃進(jìn)了一個(gè)迷宮。

迷宮可以視為一棵 nn 個(gè)節(jié)點(diǎn)的樹，在第 ii 個(gè)節(jié)點(diǎn)有一個(gè)大小 w_iw

i

，顏色為 c_ic

i

的蘑菇。

Crazycth 的室友喜歡吃蘑菇，但是相同顏色的蘑菇他只想吃一個(gè)，同時(shí)每個(gè)節(jié)點(diǎn)只能經(jīng)過一次。他可以瞬間算出以任一節(jié)點(diǎn)為終點(diǎn)時(shí)他所能吃的蘑菇大小總和的最大值。不過他此時(shí)忙于在迷宮入口（11 號(hào)節(jié)點(diǎn)）吃蘑菇，聰明的你能幫忙解決這個(gè)問題嗎？

輸入描述:

第一行包含一個(gè)正整數(shù) n (2\le n \le 10^5)n(2≤n≤10

5

)，表示迷宮節(jié)點(diǎn)的個(gè)數(shù)。

第二行包含 nn 個(gè)正整數(shù) w_1,w_2, \ldots, w_nw

1

,w

2

,…,w

n

(1 \le w_i \le 10^8)(1≤w

i

≤10

8

) ，分別表示第 ii 個(gè)節(jié)點(diǎn)的蘑菇的大小。

第三行包含 nn 個(gè)正整數(shù) c_1,c_2, \ldots, c_n (1 \le c_i \le n)c

1

,c

2

,…,c

n

(1≤c

i

≤n)，分別表示第 ii 個(gè)節(jié)點(diǎn)的蘑菇的顏色。

接下來 n - 1n?1 行，每行兩個(gè)正整數(shù) u_i,v_i (1 \le u_i \lt v_i \le n)u

i

,v

i

(1≤u

i

i

≤n)，表示連接 u_iu

i

和 v_iv

i

的一條邊 。

輸入數(shù)據(jù)保證不存在重邊，并且每個(gè)節(jié)點(diǎn)都可以由起點(diǎn)唯一到達(dá)，11 號(hào)節(jié)點(diǎn)為起點(diǎn)。

輸出描述:

輸出 nn 行，第 ii 行包含一個(gè)整數(shù)，即從 11 號(hào)點(diǎn)出發(fā)最終到達(dá) ii 號(hào)點(diǎn)時(shí)，能吃到的蘑菇的大小總和的最大值。

示例1

輸入

復(fù)制

5

1 4 5 5 9

1 2 2 3 4

1 2

2 3

3 5

1 4

輸出

復(fù)制

1

5

6

6

15

思路：

直接dfs遍歷每個(gè)點(diǎn)，開個(gè)數(shù)組維護(hù)一下到當(dāng)前為止每個(gè)顏色最大的蘑菇，然后回溯的時(shí)候改回去就行。

注意蘑菇大小1e8加起來會(huì)爆int，要開ll

#include using namespace std; typedef long long LL; const LL maxn = 2e5+10; LL w[maxn], c[maxn]; vectorG[maxn]; // mapmp; LL cc[maxn]; LL now = 0; LL ans[maxn]; void dfs(LL u, LL fa){ // if(!mp.count(c[u]))mp[c[u]] = 0; LL t = cc[c[u]], ok = 0; if(w[u] > cc[c[u]]){ cc[c[u]] = w[u]; now -= t; now += w[u]; ok = 1; } ans[u] = now; for(LL to : G[u]){ if(to != fa)dfs(to, u); } if(ok==1){ now += t; now -= w[u]; } cc[c[u]] = t; } int main(){ LL n; cin>>n; for(LL i = 1; i <= n; i++)cin>>w[i]; for(LL i = 1; i <= n; i++)cin>>c[i]; for(LL i = 1; i < n; i++){ LL u, v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1, -1); for(LL i = 1; i <= n; i++){ cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

H 差不多得了

鏈接：https://ac.nowcoder.com/acm/contest/33785/H

來源：?？途W(wǎng)

題目描述

Auggie 非常喜歡說差不多，而 Crazycth 非常喜歡說得了，于是他們?cè)谝黄鹜鏁r(shí)經(jīng)常發(fā)出差不多得了的聲音。

對(duì)于一個(gè)由正整數(shù)組成的數(shù)組 aa，定義 ss 為 aa 數(shù)組所有元素之和，即\displaystyle s=\sum_{i=1}^{n} a_{i}s=

i=1

∑

n

a

i

。Auggie 會(huì)將數(shù)組中的一些數(shù)取出并按原來順序拼接成一個(gè)新的子數(shù)組 bb，即 bb 是 aa 的一個(gè)子序列，而一個(gè)數(shù)組的子序列被稱為差不多得了的當(dāng)且僅當(dāng)它的所有元素之和等于 s-1s?1。

Crazycth 想知道數(shù)組 aa 有多少種本質(zhì)不同的差不多得了的 bb。你能幫他解答嗎？

對(duì)于數(shù)組 xx 與 yy，它們是本質(zhì)不同的當(dāng)且僅當(dāng)它們長(zhǎng)度不同或存在 ii 使得 x_i \neq y_ix

i



=y

i

。

輸入描述:

第一行包含一個(gè)整數(shù) T (1 \le T \le 1000)T(1≤T≤1000)，表示測(cè)試數(shù)據(jù)的組數(shù)。對(duì)于每組數(shù)據(jù)：

第一行包含一個(gè)整數(shù) n (1 \le n \le 30)n(1≤n≤30)，表示數(shù)組元素的個(gè)數(shù)。

第二行包含 nn 個(gè)整數(shù) a_1,a_2,\ldots,a_n (1 \le a_i \le 10^9)a

1

,a

2

,…,a

n

(1≤a

i

≤10

9

)，表示數(shù)組的每個(gè)元素。

輸出描述:

對(duì)于每組數(shù)據(jù)，在一行輸出一個(gè)整數(shù)表示有多少種本質(zhì)不同的差不多得了的數(shù)組 bb 的數(shù)量。

示例1

輸入

復(fù)制

3

3

1 2 3

2

100 4

5

3 4 2 1 1

輸出

復(fù)制

1

0

1

備注:

子數(shù)列，又稱子序列，在數(shù)學(xué)中，某個(gè)序列的子序列是從最初序列通過去除某些元素但不破壞余下元素的相對(duì)位置（在前或在后）而形成的新序列，如空數(shù)組， {(1,2,4)}(1,2,4) 和 {(1,2,3,4)}(1,2,3,4) 是 {(1,2,3,4)}(1,2,3,4) 的子序列， 而 {(1,4,3)}(1,4,3) 不是。

思路：

統(tǒng)計(jì)一下有多少段連續(xù)的1即可。

#include using namespace std; int main(){ int T; cin>>T; while(T--){ int n; cin>>n; int cnt = 0, ok = 0; for(int i = 1; i <= n; i++){ int x; cin>>x; if(x==1){ if(ok==0)cnt++; ok = 1; }else{ ok = 0; } } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

I 數(shù)學(xué)題真難啊

鏈接：https://ac.nowcoder.com/acm/contest/33785/I

來源：牛客網(wǎng)

題目描述

你告別了 Crazycth 繼續(xù)上路，又遇到了不喜歡數(shù)學(xué)的 DavidXu_JJ 講故事。

DavidXu_JJ 有一天和他的隊(duì)友在訓(xùn)練時(shí)，遇到這么一道題：

有一個(gè)長(zhǎng)度為 nn 的數(shù)組 a = [a_1, a_2, \ldots, a_n]a=[a

1

,a

2

,…,a

n

]，數(shù)組中的每個(gè)元素可以是 0 \sim 90～9 中的任意一個(gè)整數(shù)。如果它所有元素之和 \sum a∑a 是 33 的倍數(shù)，那么就稱它為有趣的數(shù)組，你需要求出所有長(zhǎng)度為 nn 的數(shù)組中有多少種數(shù)組是有趣的。

DavidXu_JJ 和他的隊(duì)友決定構(gòu)造它的 生成函數(shù) 并使用 快速傅立葉變換 來計(jì)算這個(gè)值，但在復(fù)盤時(shí)發(fā)現(xiàn)這題有極其簡(jiǎn)單的方法能夠算出答案，導(dǎo)致他們當(dāng)場(chǎng)腦淤血暈倒過去。

DavidXu_JJ 從病床上想到了一個(gè)更加困難的問題，但他因?yàn)樾睦黻幱皩?dǎo)致無法獨(dú)立解決這個(gè)問題，請(qǐng)問你能否幫助他解決？題目描述如下：

有一個(gè)長(zhǎng)度為 nn 的數(shù)組 a = [a_1, a_2, \ldots, a_n]a=[a

1

,a

2

,…,a

n

]，數(shù)組中的每個(gè)元素可以是 0 \sim 90～9 中的任意一個(gè)整數(shù)。現(xiàn)將其下標(biāo)為奇數(shù)的元素和偶數(shù)的元素分別取出，組成兩個(gè)數(shù)組 a^{\text{odd}}a

odd

和 a^{\text{even}}a

even

。例如：數(shù)組 a = [1, 2, 3, 4, 5, 6, 7]a=[1,2,3,4,5,6,7] 被分為數(shù)組 a^{\text{odd}} = [1, 3, 5, 7]a

odd

=[1,3,5,7] 和數(shù)組 a^{\text{even}} = [2, 4, 6]a

even

=[2,4,6]。

如果 \sum a^{\text{odd}}∑a

odd

是 33 的倍數(shù)且 \sum a^{\text{even}}∑a

even

數(shù)組是 99 的倍數(shù)，那么就稱 aa 為"不有趣的數(shù)組’'，請(qǐng)求出所有長(zhǎng)度為 nn 的不有趣數(shù)組的個(gè)數(shù)。由于答案可能很大，你只需要輸出答案對(duì) 998244353998244353 取模后的結(jié)果。

輸入描述:

第一行包含一個(gè)整數(shù) nn (1 \le n \le 3 \times 10^5)(1≤n≤3×10

5

)，表示數(shù)組 aa 的長(zhǎng)度。

輸出描述:

在一行輸出一個(gè)整數(shù)，表示所有長(zhǎng)度為 nn 的不有趣數(shù)組的個(gè)數(shù)對(duì) 998244353998244353取模后的結(jié)果。

示例1

輸入

復(fù)制

2

輸出

復(fù)制

8

示例2

輸入

復(fù)制

5

輸出

復(fù)制

4008

示例3

輸入

復(fù)制

114514

輸出

復(fù)制

549375874

思路：

打個(gè)表再思考一下，不難發(fā)現(xiàn)，3和9是獨(dú)立考慮的，相當(dāng)于奇數(shù)位加起來%3=0，偶數(shù)位加起來%3=0。

因?yàn)?和9的特殊性，加起來%3=0等價(jià)于這個(gè)數(shù)本身%3=0，所以問題轉(zhuǎn)化為求1位數(shù)，2位數(shù)，3位數(shù)，，，n位數(shù)，里面%3=0的數(shù)的個(gè)數(shù)。 3和9都是n/2位數(shù)，如果有多的位數(shù)就加到3上。

考慮100%3=0的數(shù)的個(gè)數(shù)，就是個(gè)小學(xué)生問題直接/3即可。注意這里0也被算到%3=0上，所以/3后要+1。

然后就 ( 1 0 n / 2 + 1 ? 1 3 + 1 ) ? ( 1 0 n / 2 ? 1 9 + 1 ) (\frac{10^{n/2+1} -1}{3}+1)*(\frac{10^{n/2}-1}{9}+1) (310n/2+1?1 +1)?(910n/2?1 +1)即可，注意做除法的時(shí)候要用逆元，取模要多取一下。

關(guān)于+1-1的問題，舉個(gè)例子：題目輸入n=6, 所以3是三位數(shù)，9也是三位數(shù)，然后三位數(shù)是從000-999的，10^3 = 1000，所以要-1。999/3=333，但是0%3=0，所以是334。

#include using namespace std; typedef long long LL; const LL mod = 998244353; LL pows(LL a, LL x) { if(x==0)return 1; LL t = pows(a, x>>1); if(x%2==0)return t*t%mod; return t*t%mod*a%mod; } LL pows(LL a, LL x, LL p) { if(x==0)return 1; LL t = pows(a, x>>1, p); if(x%2==0)return t*t%p; return t*t%p*a%p; } LL exgcd(LL a, LL b, LL &x, LL &y){ if(!b){ x = 1, y = 0; return a; }else{LL r = exgcd(b, a%b, x, y); LL t = x; x = y; y = t-a/b*y; return r; }} void exgcd(LL a, LL b, LL &d, LL &x, LL & y, LL MOD) { if (b==0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x, MOD); y -= x * (a / b); } } LL inv(LL a, LL MOD) { LL d=0, x=0, y=0; exgcd(a, MOD, d, x, y, MOD); return d == 1 ? (x + MOD) % MOD : -1; } int main(){ LL n; cin>>n; LL x = n/2, y = n/2; if(n%2==1)x++; LL xx = (pows(10,x,mod)-1+mod)%mod*inv(3,mod)%mod+1, yy = (pows(10,y,mod)-1+mod)%mod*inv(9,mod)%mod+1; cout<<(xx*yy+mod)%mod<<"\n"; return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

AI 區(qū)塊鏈 數(shù)據(jù)結(jié)構(gòu)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。