链接
题意：
t 组数据，每组数据给定 nn 个操作,每个操作为以下两者之一：
x = a + b表示将变量 b 和 a 中的字符串拼接后赋给 x。x := s表示将字符串 s 赋给 x。
对于每组数据，求最后一次操作中变量 x 中的字符串所含有子串 haha 的个数。
$t\leq 10^3,n\leq 50t$。给出的所有变量名或字符串的长度均 $\leq 5$，且所有字母都是小写字母。
分析：
首先我们想到直接模拟这个合并的过程记录下最后一步的字符串，我们用map标记字符串等于多少。然后经过n次次操作后，我们最后扫一遍有多少haha，很明显如果最后那个长度很大一定会超时的。
然后我们发现，如果我们是x := s那么我们只需记录下来s中有多少haha即可。然后x = a + b每次拼凑的时候，合并a和b只需要把a中的haha加上b中的haha数量，再加上中间合并产生的haha（只需要考虑a的最后三个字符和b的前三个字符）。
这样我们会发现他会爆内存，为什么那，我们看超时那个地方是因为字符串过长，但是如果一个字符串每次重复性的增长他就会很长，以至于暴内存。所以我们也要优化内存。
我们通过上哪超时那段发现他的代价是a中的haha加上b中的haha数量，再加上中间合并产生的haha，a和b中的代价已经在我们预处理种解决了，我们现在只需考虑中间合并产生的haha就好了。而我们合并的两个串只需要用到前三个字符和后三个字符，所以我们只需要维护一个长度为6的字符串即可，每次都维护一个字符串的前三个字符和后三个字符就好了，这样字符串长度最长就是6，我们在x := a中记录完a中的haha 直接将a转化成前三个字符+后三个字符即可。
注 过题后发现有用hash过得，感兴趣可以与看看。
ll n, m;
string str;
map<string,string> a;
map<string,ll> res;
void solve()
{
cin>>n;
a.clear();
res.clear();
string ans;
while(n--){
string ch;
cin>>ch;
cin>>str;
if(str=="="){
string b,c,q;
cin>>b>>q>>c;
ll sum=res[b]+res[c];
ll len1=a[b].size();
ll len2=a[c].size();
if(len1>=3){
if(a[b][len1-3]=='h'&&a[b][len1-2]=='a'&&a[b][len1-1]=='h'&&len2>=1&&a[c][0]=='a') sum++;
}
if(len1>=2){
if(a[b][len1-2]=='h'&&a[b][len1-1]=='a'&&len2>=2&&a[c][0]=='h'&&a[c][1]=='a') sum++;
}
if(len1>=1)if(a[b][len1-1]=='h'&&len2>=3&&a[c][0]=='a'&&a[c][1]=='h'&&a[c][2]=='a') sum++;
res[ch]=sum;
string s="";
for(ll i=0;i<min(3ll,len1);i++) s+=a[b][i];
for(ll i=(0ll,len2-3);i<len2;i++) s+=a[c][i];
a[ch]=s;
ans=ch;
}else {
cin>>str;
ll sum=0;
ll len=str.size();
for(int i=3;i<str.size();i++){
if(str[i]=='a'&&str[i-1]=='h'&&str[i-2]=='a'&&str[i-3]=='h')
sum++;
}
string s="";
if(str.size()<=6) s=str;
else {
s+=str[0];s+=str[1];s+=str[2];s+=str[len-3];s+=str[len-2];s+=str[len-1];
}
res[ch]=sum;
a[ch]=s;
ans=ch;
}
}
cout<<res[ans]<<endl;
}
链接
题意：
给出n,m求满足以下条件的方案数
- $a_i \in [l_i,r_i] (i\in[1,n])$
- $\sum_{i=1}^na_i\leq m$
- $\gcd(a_1,a_2,...,a_n)=1$
结果对998244353取模
分析：
首先我们抛开第三个条件$gcd$不看，那么这个就可以$O(nm)$求，$n\leq50,m\leq 1e5$所以不会超时。但是有了这个限制条件，我们就需要看看如果才能实现这个限制条件。
首先我们定义$f(a_1,a_2,...an)=\sum{i=1}^na_i<=m$
$$\sum_{a_i=l_1}^{r_1}\sum_{a_i=l_2}^{r_2}\sum_{a_i=l_3}^{r_3}....\sum_{a_i=l_n}^{r_n}f(a_1,a_2,....a_n)[\gcd(a_1,a_2,...,a_n)=1]$$
这里我们看到$[gcd(a_1,a_2.....a_n)=1]$我们想到莫比乌斯反演。
$$\sum_{a_i=l_1}^{r_1}\sum_{a_i=l_2}^{r_2}\sum_{a_i=l_3}^{r_3}....\sum_{a_i=l_n}^{r_n}f(a_1,a_2,....a_n)\sum_{d|\gcd(a_1,a_2,...,a_n)}\mu(d)$$
$d|\gcd(a_1,a_2,...,a_n)$说明 $a_1,a_2...a_n$都是d的倍数。
$$\sum_{a_i=l_1}^{r_1}\sum_{a_i=l_2}^{r_2}\sum_{a_i=l_3}^{r_3}....\sum_{a_i=l_n}^{r_n}f(a_1,a_2,....a_n)\sum_{d|a_1\&d|a_2,...\&d|a_n}\mu(d)$$
提取d,发现d最大是m。
$$\sum_{d=1}^{m}\mu(d)\sum_{a_i=\frac{l_1}{d}}^{\frac{r_1}{d}}\sum_{a_i=\frac{l_2}{d}}^{\frac{r_2}{d}}.........\sum_{a_i=\frac{l_n}{d}}^{\frac{r_n}{d}}f(a_1,a_2,....a_n)$$
综上，我们会发现，如果$\mu(d)$等于0，后面的也就不用计算了。
$f()$用DP来做就好了.
注意莫比乌斯反演最终形式不一定有整除分块的形式。
int prime[maxn],mu[maxn],l[maxn],r[maxn];
bool isprime[maxn];
int n,m, cnt;
ll a[maxn],b[maxn];
void init()
{
mu[1]=isprime[1]=1;
for(int i = 2; i < maxn; i++)
{
if(!isprime[i]) prime[++cnt] = i,mu[i]=-1;
for(int j = 1; j <= cnt && prime[j]*i < maxn; j++)
{
isprime[i * prime[j]] = true;
if(i % prime[j] == 0) break;
mu[i*prime[j]]=-mu[i];
}
}
}
int dp[maxn],f[maxn];
void solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
ll ans=0;
for(int i=1;i<=m;i++){
if(mu[i]==0) continue;
for(int j=1;j<=n;j++){
a[j]=(l[j]+i-1)/i;
b[j]=r[j]/i;
}
int sum=m/i;
for(int j=0;j<=sum;j++) dp[j]=1;
for(int j=1;j<=n;j++){
for(int k=1;k<=sum;k++) f[k]=0;
for(int k=a[j];k<=sum;k++){
f[k]=dp[k-a[j]];
if(k-b[j]-1>=0) f[k]=(f[k]-dp[k-b[j]-1]+mod)%mod;
}
dp[0]=0;
for(int k=1;k<=sum;k++) dp[k]=(dp[k-1]+f[k])%mod;
}
ans+=dp[sum]*mu[i]%mod;
ans=(ans+mod)%mod;
}
cout<<ans<<endl;
}
