JSOI2017 代码

标签：10 ll JSOI2017 int 代码 sum rightarrow

\(\text{JSOI2017 day1t1 代码}\)

题解

设\(d_i\)表示长度为\(i\)的库函数数量，\(h_i\)表示长度为\(i\)的可编译代码的数量，\(f_{i,j}\)表示寄存器初始值为\(j\)、终值为\(0\)的代码数量，\(F_{i,j}\)表示寄存器初值为\(0\)、终值为\(j\)的代码数量，\(g_{i,j}\)表示长度为\(i\)可以加上\(j\)的一个真约数、不包含括号的代码数量
\(d,h,g\)易求，考虑\(f,F\)怎样转移
对于\(f\)，首先有一个最简单的转移，在开头加上\(+\)或\(-\)

\[f_{i-1,j-1}+f_{i-1,j+1}\rightarrow f_{i,j} \]

在开头加上库函数

\[\sum_{k=2}^{i}f_{i-k,j}d_k\rightarrow f_{i,j} \]

在开头加上括号
若\(j=0\)，括号中可以是任何可编译代码

\[\sum_{k=2}^{i}f_{i-k,j}h_{k-2}\rightarrow f_{i,j} \]

若\(j\not =0\)，括号中代码需要再一次或若干次执行后将\(j\)变为\(0\)

\[\sum_{k=2}^{i}f_{i-k,j}(g_{k-2,j}+f_{k-2,j})\rightarrow f_{i,j} \]

这里也可以意识到前面将\(g\)定义为真约数是为了避免算重
\(F\)的转移类似，不过由于定义不同，考虑在结尾加东西

\[F_{i-1,j-1}+F_{i-1,j+1}\rightarrow F_{i,j} \]

\[\sum_{k=2}^{i}F_{i-k,j}d_k\rightarrow F_{i,j} \]

若\(j=0\)，考虑在结尾加括号

\[\sum_{k=2}^i[F_{i-k,0}h_{k-2}+\sum_{w\not =0}F_{i-k,w}(g_{k-2,w}+f_{k-2,w})]\rightarrow F_{i,j} \]

答案即为\(\sum_{i}F_{n,i}\)

\(\text{code}\)

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=3e2+10,C=1e2+50;
const ll mod=1e9+7;
int n,k,d[N+10];
ll h[N+10],g[N+10][N+10],f[N+10][N+10],F[N+10][N+10];
void Add(ll &a,ll b){a+=b,a%=mod;}
int main()
{
	freopen("code.in","r",stdin);
	freopen("code.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i=1,l=1;l<=k;i++,l=l*10) d[i+1]=min(9*l,k-l+1);
//	for(int i=1;i<=n;i++) printf("%d ",d[i]);puts("");
	h[0]=1;
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1]*2%mod;
		for(int j=2;j<=i;j++)
			Add(h[i],h[i-j]*h[j-2]%mod),
			Add(h[i],h[i-j]*d[j]%mod);
	}
//	for(int i=1;i<=n;i++) printf("%lld ",h[i]);puts("");
	g[0][0+C]=1;
	for(int i=1;i<=n;i++)
		for(int j=-n+C;j<=n+C;j++)
		{
			g[i][j]=g[i-1][j-1]+g[i-1][j+1],g[i][j]%=mod;
			for(int k=2;k<=i;k++)
				Add(g[i][j],g[i-k][j]*d[k]%mod);
		}
//	printf("%lld\n",g[3][3+C]);
//	return 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=-n;j<0;j++)
		{
			for(int k=2;-n<=j*k;k++)
				Add(g[i][j*k+C],g[i][j+C]);
			g[i][j+C]=0;
		}
		for(int j=n;j>0;j--)
		{
			for(int k=2;j*k<=n;k++)
				Add(g[i][j*k+C],g[i][j+C]);
			g[i][j+C]=0;
		}
	}
//	printf("%lld\n",g[3][3+C]);
//	return 0;
	f[0][0+C]=1;
	for(int i=1;i<=n;i++)
		for(int j=-n+C;j<=n+C;j++)
		{
			Add(f[i][j],f[i-1][j-1]);
			Add(f[i][j],f[i-1][j+1]);
			for(int k=2;k<=i;k++) Add(f[i][j],f[i-k][j]*d[k]%mod);
			if(j==C)
			{
				for(int k=2;k<=i;k++)
					Add(f[i][j],f[i-k][j]*h[k-2]%mod);
			}
			else
			{
				for(int k=2;k<=i;k++)
					Add(f[i][j],f[i-k][C]*f[k-2][j]%mod),
					Add(f[i][j],f[i-k][C]*g[k-2][j]%mod);
			}
		}
//	printf("%lld\n",f[3][0+C]);
//	return 0;
	F[0][0+C]=1;
	for(int i=1;i<=n;i++)
		for(int j=-n+C;j<=n+C;j++)
		{
			Add(F[i][j],F[i-1][j-1]);
			Add(F[i][j],F[i-1][j+1]);
			for(int k=2;k<=i;k++) Add(F[i][j],F[i-k][j]*d[k]%mod);
			if(j==C)
			{
				for(int k=2;k<=i;k++)
				{
					Add(F[i][j],F[i-k][j]*h[k-2]%mod);
					for(int w=-n+C;w<=n+C;w++)
						if(w!=C)
							Add(F[i][j],F[i-k][w]*g[k-2][w]%mod),
							Add(F[i][j],F[i-k][w]*f[k-2][w]%mod);
				}
			}
		}
//	printf("%lld %lld %lld %lld\n",F[3][0+C],F[3][1+C],F[3][2+C],F[3][3+C]);
	ll ans=0;
	for(int i=-n+C;i<=n+C;i++) Add(ans,F[n][i]);
	printf("%lld\n",ans);
	return 0;
}

标签：10,ll,JSOI2017,int,代码,sum,rightarrow
From： https://www.cnblogs.com/the-blog-of-doctorZ/p/18282632