LG5337/BZOJ5508 「TJOI2019」甲苯先生的字符串线性动态规划+矩阵加速

问题描述

LG5337

BZOJ5508

题解

设\(opt_{i,j}(i \in [1,n],j \in [1,26])\)代表区间\([1,i]\)，结尾为\(j\)的写法。

设\(exist_{i,j}(i,j \in [1,26])\)代表\((i,j)\)能否前后相邻，如果为\(1\)，则不能。

则有

\[opt_{i,j}=\sum_{k=1}^{26} opt_{i-1,k}(exist_{k,j}=0)
\]

发现\(n \le 10^{15}\)，就这样递推肯定不行，所以矩阵优化

矩阵\(base\)为\(26 \times 26\)的，\(base_{i,j}=1-exist_{i,j}\)

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

const int mod=1000000007LL;

char s[100007];

int len,n;

int exist[27][27];

int chk(char c){

	return c-'a'+1;

}

struct Mat{

	int a[27][27],n;

	Mat(){

		n=26;memset(a,0,sizeof(a));

	}

}base,ans;

Mat Mul(Mat a,Mat b){

	int q=a.n;

	Mat ret;

	for(int i=1;i<=q;i++){

		for(int j=1;j<=q;j++){

			for(int k=1;k<=q;k++){

				ret.a[i][j]=(ret.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;

			}

		}

	}

	return ret;

}

Mat ksm(Mat x,int p){

	Mat ret;

	for(int i=1;i<=26;i++) ret.a[i][i]=1;

	while(p){

		if(p&1) ret=Mul(ret,x);p>>=1;

		x=Mul(x,x);

	}

	return ret;

}

int sum;

signed main(){

	ios::sync_with_stdio(false);

	cin>>n>>(s+1);

	if(n==1){

		puts("1");return 0;

	}

	len=strlen(s+1);

	for(int i=2;i<=len;i++){

		int xx=chk(s[i]),yy=chk(s[i-1]);

		exist[yy][xx]=1;

	}

	for(int i=1;i<=26;i++){

		ans.a[1][i]=1;

		for(int j=1;j<=26;j++){

			if(!exist[i][j]) base.a[i][j]=1;

		}

	}

	ans=Mul(ans,ksm(base,n-1));

	for(int i=1;i<=26;i++){

		sum=(sum+ans.a[1][i])%mod;

	}

	cout<<sum<<endl;

	return 0;

}

巴特西

LG5337/BZOJ5508 「TJOI2019」甲苯先生的字符串线性动态规划+矩阵加速

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG5337/BZOJ5508 「TJOI2019」甲苯先生的字符串 线性动态规划+矩阵加速

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

LG5337/BZOJ5508 「TJOI2019」甲苯先生的字符串线性动态规划+矩阵加速