新人求助CF506E那题,本地RE提交AC
  • 板块学术版
  • 楼主LebronDurant
  • 当前回复13
  • 已保存回复13
  • 发布时间2020/7/16 11:16
  • 上次更新2023/11/6 23:02:34
查看原帖
新人求助CF506E那题,本地RE提交AC
84564
LebronDurant楼主2020/7/16 11:16

应该是编译器之类的事吧?这个矩阵结构体里的数组开代码中的大小在本地就会输入之前就RE,开112×112112\times 112就能正常运行,请问为什么?难道是我哪里UB了么?有大佬帮我看看么?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
#define N 100002
const int p=10007;
int D;
struct node
{
	int s[312][312];
}st,md,dw,s2;
node operator*(node a,node b)
{
	node ret;memset(ret.s,0,sizeof(ret.s));
	for(int i=1;i<=D;i++)for(int j=i;j<=D;j++)for(int k=i;k<=j;k++)
	ret.s[i][j]=(ret.s[i][j]+a.s[i][k]*b.s[k][j]%p)%p;return ret;
}
int n,m,dp[202][202][202],f[N],ans;
char ch[N];
inline node ksm(node d,int k){node ret=dw;while(k){if(k&1)ret=ret*d;d=d*d;k>>=1;}return ret;}
int main()
{
	//cout<<sizeof(st)/(1<<18)<<endl;
	scanf("%s%d",ch+1,&m);n=strlen(ch+1);
	if(ch[1]==ch[n])dp[1][n][0]=1;
	else dp[1][n][1]=1;
	for(int i=1;i<=n;i++)for(int j=n;j>=i;j--)
	{
		for(int k=0;k<=n;k++)if(dp[i][j][k])
		{
			if(ch[i]==ch[j])
			{
				if(i+1<j)
				{
					if(ch[i+1]==ch[j-1])(dp[i+1][j-1][k]+=dp[i][j][k])%=p;
					else (dp[i+1][j-1][k+1]+=dp[i][j][k])%=p;
				}
				else f[k]=(f[k]+dp[i][j][k])%p;
			}
			else
			{
				if(ch[i]==ch[j-1])(dp[i][j-1][k]+=dp[i][j][k])%=p;
				else (dp[i][j-1][k+1]+=dp[i][j][k])%=p;
				if(ch[i+1]==ch[j])(dp[i+1][j][k]+=dp[i][j][k])%=p;
				else (dp[i+1][j][k+1]+=dp[i][j][k])%=p;
			}
		}
	}D=n+(n+1)/2+1;
	for(int i=1;i<=D;i++)dw.s[i][i]=1;
	for(int i=1;i<=n;i++)
	{
		md.s[i][i]=24;if(i<n)md.s[i][i+1]=1;
		int to=(n-i+1)/2;
		md.s[i][D-to]=f[i];
	}
	for(int i=n+1;i<D;i++)md.s[i][i+1]=1,md.s[i][i]=25;
	md.s[D][D]=26;
	st.s[1][1]=1;st.s[1][D-(n+1)/2]=f[0];
	if((n+m)%2==0)
	{
		st=st*ksm(md,(n+m)/2);
		printf("%d\n",st.s[1][D]);return 0;
	}
	st=st*ksm(md,(n+m+1)/2);ans=st.s[1][D];
	for(int i=0;i<=n;i++)f[i]=0;
	for(int i=1;i<n;i++)if(ch[i]==ch[i+1])for(int j=0;j<=n;j++)f[j]=(f[j]+dp[i][i+1][j])%p;
	memset(md.s,0,sizeof(md.s));memset(st.s,0,sizeof(st.s));
	for(int i=1;i<=n;i++)
	{
		md.s[i][i]=24;if(i<n)md.s[i][i+1]=1;
		int to=(n-i+1)/2;
		md.s[i][D-to]=f[i];
	}for(int i=n+1;i<D;i++)md.s[i][i+1]=1,md.s[i][i]=25;
	st.s[1][1]=1;st.s[1][D-(n+1)/2]=f[0];
	st=st*ksm(md,(n+m+1)/2);
	printf("%d\n",(ans-st.s[1][D]+p)%p);
}

2020/7/16 11:16
加载中...