CF582D Number of Binominal Coefficients 库默尔定理数位dp

LINK：Number of Binominal Coefficients

原来难题都长这样。。

水平有限只能推到一半。

设\(f(x)\)表示x中所含p的最大次数。即x质因数分解之后 p的指标。

容易想到 \(f(n!)=\sum_{i=1}^{n}\frac{n}{p^i}\)

也同时题目其实是想让我们求出 \(f(n!)-f(k!)-f((n-k)!)>=a\)的数对(n,k)的个数。

需要再转换一下可以得到\(f(x)\)x质因数分解之后扔掉第一位的数字大小。

\(f(n!)\)其实是不断扔掉一位数字大小的累加。

但是我们需要求出\(f(C(n,k))\) 这里可以自己硬猜不过存在一个库默尔定理。

\(f(C(n,k))\)其实是 \(f(n!)-f(k!)-(n-k)!\)也即 k和n-k在p进制下进位的次数。

这里给出简单证明：如果不存在进位那么显然这个东西就是为0.

如果某一位存在进位那么在统计当前位的时候没有影响统计下一位的贡献时 \(f(n!)\)会多1.

显然当前的进位只会对下一位有贡献1。

也就是每次进位都是n!比k!+(n-k)!多1的时候所以\(f(C(n,k))\)即 k和n-k在p进制下进位的次数。

至此可以发现需要解决的问题变成了有多少个数对(n,k) 在p进制下进位次数>=a 当然\(n+k\leq lim\)

剩下的就是一个数位dp的模型了不过有点难写。

大体上设状态 f[i][j][0/1][0/1]表示最高位~当前位有j次进位且是否存在最高位限制且是否有下一位的进位。

值得一提的是需要保留下一位是否进位而并非当前位因为下一位对当前有影响且一下位也同时影响着当前位是否满足限制。

记忆化搜索就不大行了常数大了这个状态被定义出来就是接近1e7的。

显然递推需要从左到右推转移比较难写注意要认真。

这可真是从头到尾都是一道难题该有的样子。

const int MAXN=3510;

int n,m,p,a;

int f[MAXN][MAXN][2][2];//f[i][j][k][l]表示n~i+1位进了j次位了有没有最高位的限制是否存对上一次的进位.

char c[MAXN];

int cc[MAXN],b[MAXN];

int main()

{

	freopen("1.in","r",stdin);

	gt(p);gt(a);gc(c);

	m=strlen(c+1);

	reverse(c+1,c+1+m);

	rep(1,m,i)cc[i]=c[i]-'0';

	while(m)

	{

		ll cnt=0;

		fep(m,1,i)

		{

			cnt=cnt*10+cc[i];

			cc[i]=cnt/p;cnt%=p;

		}

		if(!cc[m]&&m>=1)--m;

		b[++n]=cnt;

	}

	if(a>n-1){puts("0");return 0;}

	f[n+1][0][1][0]=1;

	fep(n,1,i)

	{

		int c0=(ll)(1+p)*p/2%mod;//定义域为[0,p-1]值域为[0,p-1].

		int c1=(ll)(b[i]+1)*b[i]/2%mod;//定义域为[a+b<=bi-1] 值域为[0,bi-1].

		int c2=(ll)(p-1)*p/2%mod;//定义域为[0,p-1] 值域为[p,2p-2]

		int c3=(ll)b[i]*(2*p-b[i]-1)/2%mod;//定义域为[a+b<=p+bi-1] 值域[p,p+bi-1]

		int c4=(ll)(b[i]-1)*b[i]/2%mod;

		int c5=(ll)(2*p-b[i]+1)*b[i]/2%mod;

		rep(0,n-i,j)

		{

			int f0=f[i+1][j][0][0],f1=f[i+1][j][1][0];

			int f2=f[i+1][j][0][1],f3=f[i+1][j][1][1];

			f[i][j][0][0]=((ll)f0*c0%mod+(ll)c1*f1+(ll)f2*c2%mod+(ll)f3*c3%mod)%mod;

			f[i][j][1][0]=((ll)(b[i]+1)*f1%mod+(ll)(p-1-b[i])*f3%mod)%mod;

			f[i][j+1][0][1]=((ll)c2*f0%mod+(ll)c4*f1%mod+(ll)c0*f2%mod+(ll)c5*f3%mod)%mod;

			f[i][j+1][1][1]=((ll)b[i]*f1%mod+(ll)(p-b[i])*f3%mod)%mod;

		}

	}

	ll ans=0;

	rep(a,n,i)

	{

		ans=(ans+f[1][i][0][0]+f[1][i][1][0])%mod;

		//cout<<f[1][i][0][0]<<endl;

	}

	putl(ans);return 0;

}

巴特西

CF582D Number of Binominal Coefficients 库默尔定理数位dp

最新文章

热门文章

巴特西

CF582D Number of Binominal Coefficients 库默尔定理 数位dp

最新文章

热门文章

CF582D Number of Binominal Coefficients 库默尔定理数位dp