不想写 CF。
AGC020
D. Min Max Repetition
要令连续的相同字符个数的最大值最小，可以直接贪心将 A 和 B 尽可能分开，得出答案 \(k=\lfloor\frac{A+B}{\min(A,B)+1}\rfloor\)。
接下来要在这个基础上构造字典序最小的答案。
我们显然希望 A 尽量靠前，直到超出限制时再用 B 分开，即靠前部分的答案形如 AAABAAABAAAB...。但是后面大量的 B 还需要用 A 分开，我们希望尽量少的 A 被放在后面，则后面部分的答案形如 BBBABBBABBB...。
也就是说，完整的答案字符串由前后两部分拼成，前半部分每放 \(k\) 个 A 放 \(1\) 个 B；后半部分每放 \(k\) 个 B 放 \(1\) 个 A。
那么我们可以二分这个位置 \(p\)，\(\text{check}\) 时分别求出前后所需的两种字符个数即可。
注意 \(\text{check}\) 的时候别爆 int。
Code
#define int long long
int T,A,B,C,D,k;
il bool check(int x)
{
int cntb=x/(k+1),cnta=cntb*k+x%(k+1);
return (B-cntb)<k*(A-cnta+1);
}
signed main()
{
T=read();
while(T--)
{
A=read(),B=read(),C=read(),D=read();
k=max((A+B)/(B+1),(A+B)/(A+1));
int l=0,r=A+B;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
for(int i=C;i<=D;i++)
{
if(i<=l) printf(i%(k+1)==0?"B":"A");
else printf((A+B-i+1)%(k+1)==0?"A":"B");
}
printf("\n");
}
return 0;
}
E. Encoding Subsets
没发现状态数很少的性质。
考虑区间 dp，设 \(f_{l,r}\) 表示 \([l,r]\) 这段子串压缩成任意段的方案数，\(g_{l,r}\) 表示只压缩成一段的方案数。这样设状态避免了重复计数。
那么有：
\[f_{l,r}\gets \sum_{k=l}^r g_{l,k}\times f_{k+1,r}
\]
\[g_{l,r}\gets\sum_{d\mid r-l+1} [d \text{是循环节}] f_{l,l+d-1}
\]
注意到，即使 \(l,r\) 不同，但区间内的字符串可能是一样的，这样的重复状态无需重复计算。因此我们把 \([l,r]\) 所代表的字符串直接压进状态，记搜转移即可。实际有效的状态数不多，可以通过。
Code
#include<bits/stdc++.h>
#define il inline
using namespace std;
il long long read()
{
long long xr=0,F=1; char cr;
while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
while(cr>='0'&&cr<='9')
xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
return xr*F;
}
#define int long long
const int N=105,mod=998244353;
int n;
string s;
map<string,int> f,g;
int F(string s);
int G(string s)
{
if(g.count(s)) return g[s];
if(s=="0") return 1; else if(s=="1") return 2;
int res=0;
for(int d=1;d<s.size();d++)
{
if(s.size()%d) continue;
string t;
for(int i=0;i<d;i++)
{
bool flag=1;
for(int j=i;j<s.size();j+=d) if(s[j]!='1') flag=0;
t+=flag+'0';
}
res=(res+F(t))%mod;
}
return g[s]=res;
}
int F(string s)
{
if(f.count(s)) return f[s];
int res=G(s);
for(int i=1;i<s.size();i++)
{
(res+=G(s.substr(0,i))*F(s.substr(i,s.size()-i+1))%mod)%=mod;
}
return f[s]=res;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s;
printf("%lld\n",F(s));
return 0;
}