今日得分：20+100+39（終于在考場上A題了）

T1

題目大意：給你一個長度為n的01字串，定義(A*k)(k>=2)為S=A+A+…+A(k個A)的合法壓縮，可壓縮一個合法壓縮串，兩個合法壓縮串連在一起也是一個合法壓縮串，求給定01字串的子集（與原串的與等于自身的串）的合法壓縮方案之和對998244353取模的結果，n<=100，

題解：每次列舉最后一段壓縮的串，記憶化搜索強制全壓縮的串和不強制全壓縮的串，dp即可，狀態數可以證明不是很多（上界是O(n^3+2^(n/8))，但這個上界非常非常的松），

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<ctime>
#include<map>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int mo=998244353;
string s;
map<string,int> mp[2];
int f(int now,string x)
{
	if(mp[now][x])return mp[now][x];
	register int i,j,k,n=x.length(),ret=0;//cout<<now<<" "<<n<<" "<<x<<endl;
	if(now)
	{
	for(i=0;i<n;++i)ret=(ret+1ll*f(1,x.substr(0,i))*f(0,x.substr(i,n))%mo)%mo;
	return mp[now][x]=ret;
	}
	else
	{
	for(i=1;i<n;++i)
	{
	if(n%i)continue;
	string t="";for(j=0;j<i;++j)t+='1';
	for(j=0;j<n;j+=i)
	for(k=0;k<i;++k)if(x[j+k]=='0')t[k]='0';
	ret=(ret+f(1,t))%mo;
	}
	return mp[now][x]=ret;
	}
}
int main()
{
	freopen("str.in","r",stdin);
	freopen("str.out","w",stdout);
	register int i,j,k;
	cin>>s;
	mp[0][""]=mp[1][""]=mp[0]["0"]=mp[1]["0"]=1;
	mp[1]["1"]=mp[0]["1"]=2;
	cout<<f(1,s)<<endl;
	return 0;
}

T2

題目大意：定義f[0]=f[1]=1,f[i]=x*f[i-1]+y*f[i-2](i>=2)，給定n=∏i=1 w p[i]^a[i]，求Σ i|n Σ d1|i Σ d2|d1 μ(d1)μ(d2)f[d2]，答案對1e9+7取模，w<=17,1<=x,y,p,a<=1e9,p為質數，

題解：先考慮d2部分，容易發現只有2^w種情況有貢獻，狀壓+矩陣快速冪得到每個μ(d2)f[d2]，用FMT得到Σ d1|i Σ d2|d1 μ(d1)μ(d2)f[d2]，再對每個d1計算貢獻即可，時間復雜度O((2^w)*(8*logp+w))，

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<ctime>
#include<cstdlib>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int mo=1000000007;
int w,p[20],a[20],base[35];
int num[300000],mmu[300000];
struct node{int a[3][3];}bz,gl;
inline void cheng1(node x,node y,node &z)
{
	register int i,j,k;memset(z.a,0,sizeof(z.a));
	for(i=1;i<=2;++i)for(j=1;j<=2;++j)for(k=1;k<=2;++k)
	z.a[i][k]=(z.a[i][k]+1ll*x.a[i][j]*y.a[j][k]%mo)%mo;
}
inline node ksm(node x,int y)
{
	register node ret=x,tmp;--y;
	while(y)
	{
	if(y&1)cheng1(ret,x,tmp),ret=tmp;
	y>>=1;cheng1(x,x,tmp),x=tmp;
	}
	return ret;
}
inline void cheng2(node x,node y,node &z)
{
	register int i,j,k;memset(z.a,0,sizeof(z.a));
	for(i=1;i<=1;++i)for(j=1;j<=2;++j)for(k=1;k<=2;++k)
	z.a[i][k]=(z.a[i][k]+1ll*x.a[i][j]*y.a[j][k]%mo)%mo;
}
void dfs(int x,int zt,int mu,node jz)
{
	if(x==w)
	{
	node now=gl,tmp;cheng2(now,jz,tmp);
	num[zt]=mu*tmp.a[1][2];mmu[zt]=mu;
	return;
	}
	dfs(x+1,zt,mu,jz);
	jz=ksm(jz,p[x]);
	dfs(x+1,zt|base[x],-mu,jz);
}
long long ans;
int main()
{
	freopen("mobius.in","r",stdin);
	freopen("mobius.out","w",stdout);
	register int i,j,now;
	w=re_ad();bz.a[1][1]=re_ad();bz.a[2][1]=re_ad();bz.a[1][2]=1;bz.a[2][2]=0;gl.a[1][1]=gl.a[1][2]=1;
	base[0]=1;for(i=1;i<=30;++i)base[i]=base[i-1]<<1;
	for(i=0;i<w;++i)p[i]=re_ad(),a[i]=re_ad();
	dfs(0,0,1,bz);
	for(i=0;i<w;++i)
	for(j=0;j<base[w];++j)
	{if(j&base[i])num[j]=(num[j]+num[j^base[i]])%mo;}
	for(j=0;j<base[w];++j)num[j]*=mmu[j];
	for(i=0;i<base[w];++i)
	{
	now=1;
	for(j=0;j<w;++j)if(i&base[j])now=1ll*now*a[j]%mo;else now=1ll*now*(a[j]+1)%mo;
	ans=(ans+1ll*now*num[i]%mo)%mo;
	}
	ans=(ans+mo)%mo;cout<<ans<<endl;return 0;
}

T3

題目大意：給定一個僅包含ACGT四種字母的字串，滿足對于任意1<i<n，有si=g(si-1,si+1)，其中g(x,y)如下表所示，

求每種字母數與該字串都相等的字串集合中該字串的字典序排名，對1e9+7取模，n<=2e6，

題解：觀察該表可以發現，一個合法的字串一定是CG交替，在其中輪流插入A和T得到，于是我們列舉與原串的前綴相等的部分，剩下的部分可以通過組合數得到答案，時間復雜度O(N)，

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<ctime>
#include<cstdlib>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int mo=1000000007;
char s[2000010];
int n,a[2000010];long long ans;int nu[4][2000010];
int pre[4000010],ni[4000010];
inline int ksm(int x,int y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%mo;y>>=1;x=1ll*x*x%mo;}return ret;}
inline int ab(int x){return x<0?-x:x;}
inline int C(int x,int y){if(x<0||y<0)return 0;if(x<y)return 0;return 1ll*pre[x]*ni[y]%mo*ni[x-y]%mo;}
int main()
{
	freopen("win.in","r",stdin);
	freopen("win.out","w",stdout);
	register int i,j,k,num[4];
	scanf("%s",s+1);n=strlen(s+1);
	for(i=1;i<=n;++i)
	{
	if(s[i]=='A')a[i]=0;else if(s[i]=='C')a[i]=1;else if(s[i]=='G')a[i]=2;else a[i]=3;
	++nu[a[i]][i];for(j=0;j<4;++j)nu[j][i]+=nu[j][i-1];
	}
	if(n==2)
	{
	cout<<1<<endl;
	return 0;
	}
	pre[0]=pre[1]=1;for(i=2;i<=2*n;++i)pre[i]=pre[i-1]*1ll*i%mo;
	ni[2*n]=ksm(pre[2*n],mo-2);
	for(i=2*n;i>=1;--i)ni[i-1]=1ll*ni[i]*i%mo;
	for(i=1;i<=n;++i)
	{
	if(0<a[i]&&(a[i-1]==0||a[i-1]==2||i==1))
	{
	for(j=0;j<4;++j)num[j]=nu[j][n]-nu[j][i-1];--num[0];
	if(ab(num[1]-num[2])<=1&&num[2]<=num[1]){(ans+=1ll*C(num[2]+num[0],num[0])*C(num[1]+num[3]-1,num[1]-1))%=mo;}
	}
	if(1<a[i]&&(a[i-1]==0||a[i-1]==2||i==1))
	{
	for(j=0;j<4;++j)num[j]=nu[j][n]-nu[j][i-1];--num[1];
	if(ab(num[1]-num[2])<=1&&num[2]>=num[1]){(ans+=1ll*C(num[2]+num[0]-1,num[2]-1)*C(num[1]+num[3],num[1]))%=mo;}
	}
	if(2<a[i]&&(a[i-1]==1||a[i-1]==3||i==1))
	{
	for(j=0;j<4;++j)num[j]=nu[j][n]-nu[j][i-1];--num[2];
	if(ab(num[1]-num[2])<=1&&num[2]<=num[1]){(ans+=1ll*C(num[2]+num[0],num[2])*C(num[1]+num[3]-1,num[1]-1))%=mo;}
	}
	}cout<<(ans+1)%mo<<endl;
}