|
1 | 1 | packageg3301_3400.s3337_total_characters_in_string_after_transformations_ii; |
2 | 2 |
|
3 | 3 | // #Hard #String #Hash_Table #Dynamic_Programming #Math #Counting |
4 | | -// #2024_10_29_Time_67_ms_(99.31%)_Space_45.4_MB_(45.83%) |
| 4 | +// #2025_05_14_Time_80_ms_(72.97%)_Space_45.62_MB_(24.32%) |
5 | 5 |
|
6 | 6 | importjava.util.List; |
7 | 7 |
|
8 | 8 | publicclassSolution { |
9 | | -publicstaticfinalintMOD =1000000007; |
10 | | -publicstaticfinallongM2 = (long)MOD *MOD; |
11 | | -publicstaticfinallongBIG =8L *M2; |
| 9 | +privatestaticfinalintMOD =1_000_000_007; |
12 | 10 |
|
13 | | -publicintlengthAfterTransformations(Strings,intt,List<Integer>nums) { |
14 | | -int[][]m =newint[26][26]; |
15 | | -for (inti =0;i <26;i++) { |
16 | | -for (intj =1;j <=nums.get(i);j++) { |
17 | | -m[(i +j) %26][i]++; |
18 | | - } |
19 | | - } |
20 | | -int[]v =newint[26]; |
| 11 | +publicintlengthAfterTransformations(Strings,intt,List<Integer>numsList) { |
| 12 | +int[][]localT =buildTransformationMatrix(numsList); |
| 13 | +int[][]tPower =matrixPower(localT,t); |
| 14 | +int[]freq =newint[26]; |
21 | 15 | for (charc :s.toCharArray()) { |
22 | | -v[c -'a']++; |
| 16 | +freq[c -'a']++; |
23 | 17 | } |
24 | | -v =pow(m,v,t); |
25 | | -longans =0; |
26 | | -for (intx :v) { |
27 | | -ans +=x; |
| 18 | +longresult =0; |
| 19 | +for (inti =0;i <26;i++) { |
| 20 | +longsum =0; |
| 21 | +for (intj =0;j <26;j++) { |
| 22 | +sum = (sum + (long)freq[j] *tPower[j][i]) %MOD; |
| 23 | + } |
| 24 | +result = (result +sum) %MOD; |
28 | 25 | } |
29 | | -return (int) (ans %MOD); |
| 26 | + |
| 27 | +return (int)result; |
30 | 28 | } |
31 | 29 |
|
32 | | -// A^e*v |
33 | | -privateint[]pow(int[][]a,int[]v,longe) { |
34 | | -for (inti =0;i <v.length;i++) { |
35 | | -if (v[i] >=MOD) { |
36 | | -v[i] %=MOD; |
37 | | - } |
38 | | - } |
39 | | -int[][]mul =a; |
40 | | -for (;e >0;e >>>=1) { |
41 | | -if ((e &1) ==1) { |
42 | | -v =mul(mul,v); |
| 30 | +privateint[][]buildTransformationMatrix(List<Integer>numsList) { |
| 31 | +int[][]localT =newint[26][26]; |
| 32 | +for (inti =0;i <26;i++) { |
| 33 | +intsteps =numsList.get(i); |
| 34 | +for (intj =1;j <=steps;j++) { |
| 35 | +localT[i][(i +j) %26]++; |
43 | 36 | } |
44 | | -mul =p2(mul); |
45 | 37 | } |
46 | | -returnv; |
| 38 | +returnlocalT; |
47 | 39 | } |
48 | 40 |
|
49 | | -// int matrix*int vector |
50 | | -privateint[]mul(int[][]a,int[]v) { |
51 | | -intm =a.length; |
52 | | -intn =v.length; |
53 | | -int[]w =newint[m]; |
54 | | -for (inti =0;i <m;i++) { |
55 | | -longsum =0; |
56 | | -for (intk =0;k <n;k++) { |
57 | | -sum += (long)a[i][k] *v[k]; |
58 | | -if (sum >=BIG) { |
59 | | -sum -=BIG; |
60 | | - } |
| 41 | +privateint[][]matrixPower(int[][]matrix,intpower) { |
| 42 | +intsize =matrix.length; |
| 43 | +int[][]result =newint[size][size]; |
| 44 | +for (inti =0;i <size;i++) { |
| 45 | +result[i][i] =1; |
| 46 | + } |
| 47 | +while (power >0) { |
| 48 | +if ((power &1) ==1) { |
| 49 | +result =multiplyMatrices(result,matrix); |
61 | 50 | } |
62 | | -w[i] = (int) (sum %MOD); |
| 51 | +matrix =multiplyMatrices(matrix,matrix); |
| 52 | +power >>=1; |
63 | 53 | } |
64 | | -returnw; |
| 54 | +returnresult; |
65 | 55 | } |
66 | 56 |
|
67 | | -// int matrix^2 (be careful about negative value) |
68 | | -privateint[][]p2(int[][]a) { |
69 | | -intn =a.length; |
70 | | -int[][]c =newint[n][n]; |
71 | | -for (inti =0;i <n;i++) { |
72 | | -long[]sum =newlong[n]; |
73 | | -for (intk =0;k <n;k++) { |
74 | | -for (intj =0;j <n;j++) { |
75 | | -sum[j] += (long)a[i][k] *a[k][j]; |
76 | | -if (sum[j] >=BIG) { |
77 | | -sum[j] -=BIG; |
78 | | - } |
| 57 | +privateint[][]multiplyMatrices(int[][]a,int[][]b) { |
| 58 | +intsize =a.length; |
| 59 | +int[][]result =newint[size][size]; |
| 60 | +for (inti =0;i <size;i++) { |
| 61 | +for (intk =0;k <size;k++) { |
| 62 | +if (a[i][k] ==0) { |
| 63 | +continue; |
| 64 | + } |
| 65 | +for (intj =0;j <size;j++) { |
| 66 | +result[i][j] = (int) ((result[i][j] + (long)a[i][k] *b[k][j]) %MOD); |
79 | 67 | } |
80 | | - } |
81 | | -for (intj =0;j <n;j++) { |
82 | | -c[i][j] = (int) (sum[j] %MOD); |
83 | 68 | } |
84 | 69 | } |
85 | | -returnc; |
| 70 | +returnresult; |
86 | 71 | } |
87 | 72 | } |