题意

$1 \leq n \leq 10^{18}$

$2 \leq m \leq 10^{18}$

$1 \leq k \leq 20$

思路

n,m较小

首先考虑朴素的$k=1$问题：

$f[i]$表示分解$i$的方案数

那么转移方程如下

$f[i]=f[i-1]$，这里$i$不是$m$的倍数

$f[i]=f[i-1]+f[i/n]$，这里$i$是$m$的倍数

然后对于$k \neq 1$的情况就写个$ntt$就好了

但是这个只能解决$n,m \leq 1000$

另外一种dp

考虑另外一个和值域有关的方程：

一共有$1,m,m^2,m3....$这些数

$f[i][j]$表示用了前$i$个数，得到和为$j$的方案数

注意这个状态表示是可以优化的

可以看到，如果已经用了前$i$个数，那么后面不管怎么用，从这种方案继续拓展可以得到的新的和与$j$在模$m^{i+1}$的意义下是同余的

也就是说，设$j=p \ast m^{i+1} + q$，那么从$f[i][j]$出去的状态的新的$j$写成这种方式，最后面的$q$都是相等的

因为我们最后要得到的是$n$，所以我们可以钦定这个$q = n % m^{i+1}$

这样，我们就可以换一个方式写方程：

$f[i][j]$表示用了前$i$个数，得到$j \ast m^{i+1} + n % m^{i+1}$的方案数

状态数还是太大，怎么办？

别急

我们打个表观察一下这个方程，其实可以发现一点：$f[i]j$是一批点值，它们在同一个$i$次多项式的图像上

别问我是怎么观察出来的，我也不知道

其实意会一下，就是你后面这个东西是呈$i+1$次增长的，所以每连续的$i$个就可以确定它的递推方式（其实这也是我瞎说的，我也不知道怎么证啊啊啊）

然后就很快乐了

我们每次只保存最前面的几个，然后往下一层推的时候，用插值把这一层的多项式插出来，然后定位到你推导下一层的前几个需要的那几个位置，再推导出下一层的前面几个

这样总效率是$\log^3n$的

那k呢？

我们这里可以利用一个类似多重背包的思想

显然，你把两个$k=1$的卷积起来，等价于你每一种数可以选两个了

所以$k$就代表每一种数可以选$k$个

于是就和上面的没啥差别了

总效率$O((k\log n)^3)$

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#define MOD 1000000007

#define ll long long

using namespace std;

inline ll read(){

	ll re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

ll qpow(ll a,ll b){

	ll re=1;

	while(b){

		if(b&1) re=re*a%MOD;

		a=a*a%MOD;b>>=1;

	}

	return re;

}

ll n,m,o;ll fac[2010],finv[2010];

void init(){

	ll i,len=2000;

	fac[0]=fac[1]=finv[0]=finv[1]=1;

	for(i=2;i<=len;i++) fac[i]=fac[i-1]*i%MOD;

	finv[len]=qpow(fac[len],MOD-2);

	for(i=len;i>2;i--) finv[i-1]=finv[i]*i%MOD;

}

ll t1[2010],t2[2010],g[2010],f[2010],num[2010],cnt;

inline void add(ll &a,ll b){

	a+=b;

	if(a>=MOD) a-=MOD;

}

inline ll calc(ll k,ll lim){//这里我用了线性插出一个位置的方法

	if(lim<=k) return g[lim];

	ll i,tcnt;ll ans=0;

	tcnt=0;

	for(i=lim;i>=lim-k;i--){

		if(tcnt==0) t1[tcnt]=1;

		else t1[tcnt]=t1[tcnt-1]*((i+1)%MOD)%MOD;

		tcnt++;

	}

	tcnt=k;

	for(i=lim-k;i<=lim;i++){

		if(tcnt==k) t2[tcnt]=1;

		else t2[tcnt]=t2[tcnt+1]*((i-1)%MOD)%MOD;

		tcnt--;

	}

	for(i=0;i<=k;i++){

		tcnt=(((k-i)&1)?MOD-finv[k-i]:finv[k-i]);

		add(ans,g[i]*t1[i]%MOD*t2[i]%MOD*finv[i]%MOD*tcnt%MOD);

	}

	assert(ans>=0&&ans<=MOD);

	return ans;

}

int main(){

	n=read();m=read();o=read();

	ll i,j;

	init();

	num[++cnt]=1;

	for(i=1;i<=n;i=i*m){

		for(j=1;j<=o;j++)

			num[++cnt]=i;

	}

	f[0]=1;f[1]=1;

	for(i=2;i<=cnt;i++){

		swap(f,g);

		memset(f,0,sizeof(f));

		if(num[i]==num[i-1]){//同一个数递推

			for(j=0;j<=i;j++){

				if(j) f[j]=f[j-1];

				add(f[j],calc(i-1,j));

			}

		}

		else{//不同的数递推

			for(j=0;j<=i;j++){

				if(j) f[j]=f[j-1];

				add(f[j],calc(i-1,j*m+(n%num[i])/num[i-1]));

			}

		}

	}

	swap(f,g);

	cout<<calc(cnt,n/num[cnt])<<'\n';

}

巴特西

整数拆分 [dp+多项式插值]

题意

思路

n,m较小

另外一种dp

状态数还是太大，怎么办？

那k呢？

Code

最新文章

热门文章