Problem A
Given a prime (P=10^{18}+31) with primitive root (g=42), define array (A) as:
[ A_i=\begin{cases} 795484359100928850 & i=0 \ \log_g A_{i-1} \bmod P & i>0 \end{cases} ]
For multiple queries, output (A_x). Constraints: (1\le T\le 10), (0\le x\le 10^5).
Solution: The value (A_{100000}) is provided in the problem. We can recover all previous values using modular exponentiation in reverse. Since (A_i = \log_g A_{i-1} \pmod{P}), we have (A_{i-1} = g^{A_i} \pmod{P}).
Note: When using long long (64-bit), insure the literal 1000000000000000031 is handled correctly to avoid truncation.
#include<bits/stdc++.h>
#define int64 long long
#define MAX 100010
using namespace std;
int readInt(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
const int64 MOD = 1000000000000000031LL;
const int64 BASE = 42;
int64 multiply(int64 a, int64 b){
return ( (__int128)a * b ) % MOD;
}
int64 powerExp(int64 base, int64 exp){
int64 result = 1;
while(exp > 0){
if(exp & 1) result = multiply(result, base);
base = multiply(base, base);
exp >>= 1;
}
return result;
}
int64 arr[MAX];
signed main(){
arr[100000] = 960002411612632915;
for(int i = 99999; i >= 0; i--)
arr[i] = powerExp(BASE, arr[i+1]);
int T = readInt();
while(T--)
printf("%lld\n", arr[readInt()]);
return 0;
}
Problem B
Given strings (s) (length (n)) and (t) (length (m)), count quadruples ((l,r,i,j)) satisfying:
- (1\le l\le i\le j\le r\le n)
- (s[l:r]) is a palindrome with odd length
- (s[i:j] = t)
Answer modulo (2^{32}).
Solution: Use KMP to find all occurrences of (t) in (s). Mark each occurrence position with 1 and build prefix sumss to query occurrence counts in any interval.
Use Manacher's algorithm (without special separators since only odd-length palindrome are needed) to find maximum palindrome radius for each center. Build a second-order prefix sum over palindrome regions to enable range queries.
For each center (i), a palindrome exists if (2\cdot\text{len}[i]-1 \ge m). Count valid ((l,r,i,j)) by subtracting appropriately positioned query ranges.
#include<bits/stdc++.h>
#define uint unsigned int
#define MAXN 3000010
using namespace std;
int readInt(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n, m;
char str[MAXN], pat[MAXN];
int fail[MAXN], rad[MAXN];
uint pref[MAXN];
void buildPrefix(){
for(int i=2, j=0; i<=m; i++){
while(j && pat[i]!=pat[j+1]) j=fail[j];
if(pat[i]==pat[j+1]) j++;
fail[i]=j;
}
for(int i=1, j=0; i<=n; i++){
while(j && str[i]!=pat[j+1]) j=fail[j];
if(str[i]==pat[j+1]) j++;
if(j==m){ pref[i-j+1]++; j=fail[j]; }
}
}
uint queryRange(int l, int r){
if(l <= 0) return pref[r];
return pref[r] - pref[l-1];
}
void manacher(){
int right=0, center=0;
str[0]='@'; str[n+1]='#';
for(int i=1; i<=n; i++){
if(i < right) rad[i] = min(right-i, rad[2*center-i]);
else rad[i] = 1;
while(str[i+rad[i]]==str[i-rad[i]]) rad[i]++;
if(rad[i]+i > right){
right = rad[i]+i;
center = i;
}
}
}
int main(){
n=readInt(); m=readInt();
scanf("%s%s", str+1, pat+1);
buildPrefix();
manacher();
for(int i=1; i<=n; i++) pref[i] += pref[i-1];
for(int i=1; i<=n; i++) pref[i] += pref[i-1];
int offset = (m+1)/2;
uint ans = 0;
for(int i=offset; i<=n; i++){
if(2*rad[i]-1 < m) continue;
ans += queryRange(i+offset-m, i+rad[i]-m);
ans -= queryRange(i-rad[i], i-offset);
}
printf("%u\n", ans);
return 0;
}
Problem C
Construct a simple connected undirected graph with exactly (C) unordered pairs ((x,y)) such that a Hamiltonian path exists from (x) to (y). Constraints: (1\le n\le 20), (1\le m\le n(n-1)/2), (1\le T, C\le 60).
Solution: Different constructions based on (C):
- (C=1): Edge between two vertices (1 \leftrightarrow 2)
- (C=2): Triangle with a pendant vertex
- (C\le 20): Simple cycle on (C) vertices
- (C = k(k+1)/2): Complete graph on (k+1) vertices
- (C\le 60): Combine a clique with a cycle. Let clique size be (n), cycle size be (m) (excluding 2 shared vertices, with (m\ge 2)). Total contribution:
- Inside cycle: (m+1) (adjacent pairs)
- Inside clique: (n(n-1)/2 - 1) (excluding shared vertices)
- Between cycle and clique: (2n - 4) (accounting for endpoints)
- Formula: (C = m + 2n + n(n-1)/2 - 4)
Search for valid (n, m) values (maximum (n=19)).
#include<bits/stdc++.h>
#define ll long long
#define MAXV 25
using namespace std;
int readInt(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
void solveCase(){
int C = readInt();
if(C == 1){
printf("2 1\n1 2\n");
return;
}
if(C == 2){
printf("4 4\n");
printf("1 2\n2 3\n3 4\n2 4\n");
return;
}
if(C <= 20){
printf("%d %d\n", C, C);
for(int i=1; i<=C; i++)
printf("%d %d\n", i, i%C+1);
return;
}
int triangular = 0;
for(int k=1; k<=C; k++)
if(k*(k+1)/2 == C){ triangular = k; break; }
if(triangular){
triangular++;
printf("%d %d\n", triangular, C);
for(int i=1; i<triangular; i++)
for(int j=i+1; j<=triangular; j++)
printf("%d %d\n", i, j);
return;
}
int cliqueSize = 2, cycleSize;
while(C + 4 - 2*cliqueSize - cliqueSize*(cliqueSize-1)/2 >= 2)
cliqueSize++;
cliqueSize--;
cycleSize = C + 4 - 2*cliqueSize - cliqueSize*(cliqueSize-1)/2;
printf("%d %d\n", cliqueSize+cycleSize, cliqueSize*(cliqueSize-1)/2+cycleSize+1);
for(int i=1; i<cliqueSize; i++)
for(int j=i+1; j<=cliqueSize; j++)
printf("%d %d\n", i, j);
printf("%d %d\n", cliqueSize-1, cliqueSize+1);
for(int i=cliqueSize+2; i<=cliqueSize+cycleSize; i++)
printf("%d %d\n", i-1, i);
printf("%d %d\n", cliqueSize, cliqueSize+cycleSize);
}
int main(){
int T = readInt();
while(T--) solveCase();
return 0;
}
Problem D
Given sequence ({a_n}), construct 2D array (b):
[b_{i,j}=\begin{cases}a_i+a_j & \lfloor\frac{a_i}{2}\rfloor\le a_j<a_i \ 0 & \text{otherwise}\end{cases}]
Answer multiple queries for maximum value in subrectangles with corners ((l_1,l_2)) and ((r_1,r_2)).
Constraints: (n, q \le 2\times 10^5).