IncreasingNumber

一个数是Increasing当且仅当它的十进制表示是不降的，\(1123579\)。

求 \(n\) 位不降十进制数中被 \(d\) 整除的有多少个。

\(n\leq 10^{18},d \leq 500\)

题解

简单的想法：\(dp(i,j,k)\) 表示前 \(i\) 位已填好，第 \(i\) 位是 \(j\)，模 \(d=k\) 的数的个数。

但是即使加上矩阵优化，复杂度仍然达到了 \(O(10^3d^3 \log n)\)。不可过。

观察性质：一个数是Increasing的当且仅当它是至多 \(9\) 个全 \(1\) 的数的和。

由于最终产生的数必须严格 \(n\) 位，不能有前导 \(0\)，所以我们对位数 \(< n\) 的全 \(1\) 数和 \(=n\) 的全 \(1\) 数分开做。

我们可以用 \(dp(k,j,mod)\) 表示考虑了 \(\bmod d=0\sim k\) 的全 \(1\) 数，用了 \(j\) 个数，余数是 \(mod\) 的方案数。

转移系数是 \(\binom{j+cnt_k-1}{cnt_k-1}\)，其中 \(cnt_k\) 表示 \(1\sim n-1\) 位的全 \(1\) 数中，\(\bmod d=k\) 的数的个数。开始我想的是 \(cnt_k^j\)，后来发现这样就相当于有标号了。

考虑 \(n\) 位全 \(1\) 数模 \(d\) 的余数和 \(cnt\) 数组如何求。可以利用 \(d\) 比较小来找循环节。注意循环节和起始点可能类似符号 \(\rho\) ，要加上对 \(n\) 的特判。

AC程序：

#include<bits/stdc++.h>

using namespace std;

template<class T> T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T> T read(T&x){

	return x=read<T>();

}

#define CO const

#define IN inline

typedef long long LL;

CO int mod=1000000000+7;

IN int add(int a,int b){

	return (a+=b)>=mod?a-mod:a;

}

IN int mul(int a,int b){

	return (LL)a*b%mod;

}

IN int fpow(int a,int b){

	int ans=1;

	for(;b;b>>=1,a=mul(a,a))

		if(b&1) ans=mul(ans,a);

	return ans;

}

IN void upd(int&a,int b){

	a=add(a,b);

}

CO int N=500+10;

int pw[N],pst,pcir;

int bas[N],bst,bcir;

LL cnt[N];

int dp[N][10][N];

CO int inv[10]={1,1,500000004,333333336,250000002,400000003,166666668,142857144,125000001,111111112,};

IN int binom(LL n,int m){

	if(m==0) return 1;

	if(n<m) return 0;

	int ans=1;

	for(int i=1;i<=m;++i) ans=mul(ans,mul((n-i+1)%mod,inv[i]));

	return ans;

}

struct IncreasingNumber{

	static int countNumbers(LL n,int d){

		--n;

		pw[0]=1%d;

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

			pw[i]=pw[i-1]*10%d;

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

				if(pw[j]==pw[i]){

					pst=j,pcir=i-j;

					break;

				}

			if(pcir) break;

		}

		int rn=0;

		if(n<pst){

			for(int i=0;i<=n;++i) rn=(rn+pw[i])%d;

		}

		else{

			for(int i=0;i<pst;++i) rn=(rn+pw[i])%d;

			int sum=0;

			for(int i=1;i<=pcir;++i) sum=(sum+pw[pst-1+i])%d;

			rn=(rn+(n-pst+1)/pcir%d*sum)%d;

			for(int i=1;i<=(n-pst+1)%pcir;++i) rn=(rn+pw[pst-1+i])%d;

		}

//		cerr<<"rn="<<rn<<endl;

		bas[1]=1%d;

		for(int i=2;i<=d+1;++i){

			bas[i]=(10*bas[i-1]+1)%d;

			for(int j=1;j<i;++j)

				if(bas[j]==bas[i]){

					bst=j,bcir=i-j;

					break;

				}

			if(bcir) break;

		}

		if(n<bst){

			for(int i=1;i<=n;++i) ++cnt[bas[i]];

		}

		else{

			for(int i=1;i<bst;++i) ++cnt[bas[i]];

			for(int i=1;i<=bcir;++i) cnt[bas[bst-1+i]]+=(n-bst+1)/bcir;

			for(int i=1;i<=(n-bst+1)%bcir;++i) ++cnt[bas[bst-1+i]];

		}

//		cerr<<"cnt=";

//		for(int k=0;k<d;++k)if(cnt[k])

//			cerr<<" ("<<k<<","<<cnt[k]<<")";

//		cerr<<endl;

		for(int j=0;j<=9;++j)

			dp[0][j][0]=binom(j+cnt[0]-1,j);

		for(int k=0;k<d;++k)for(int j=0;j<=9;++j)

			for(int r=0;r<d;++r)if(dp[k][j][r])

				for(int j1=0;j1<=9-j;++j1)

					upd(dp[k+1][j+j1][(r+j1*(k+1))%d],mul(binom(j1+cnt[k+1]-1,j1),dp[k][j][r]));

		int ans=0;

		for(int j=0;j<=8;++j)

			for(int j1=1;j1<=9-j;++j1)

				upd(ans,dp[d-1][j][(d-j1*rn%d)%d]);

		return ans;

	}

};

//int main(){

//	LL n=read<LL>();

//	int d=read<int>();

//	int ans=IncreasingNumber::countNumbers(n,d);

//	printf("%d\n",ans);

//}

话说Topcoder让你实现一个类，我没看出这样做有什么好处。Z前辈告诉我这样大概不用消除了读入时间的影响？

开始我的程序漏洞百出，最后写了个对拍才调出来。

暴力DP程序：

CO int N=500+10;

int f[N][N][N];

int main(){

	int n=read<int>(),d=read<int>();

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

	for(int i=0;i<n;++i)for(int j=1;j<=9;++j)

		for(int k=0;k<d;++k)if(f[i][j][k])

			for(int j1=j;j1<=9;++j1) upd(f[i+1][j1][(10*k+j1)%d],f[i][j][k]);

	int ans=0;

	for(int j=1;j<=9;++j) upd(ans,f[n][j][0]);

	printf("%d\n",ans);

	return 0;

}

对拍程序：

int main(){

	for(int i=3;i<=18;++i)

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

			cerr<<"T "<<i<<" "<<j<<endl;

			FILE*f=fopen("std.in","w");

			fprintf(f,"%d %d\n",i,j);

			fflush(f);

			system("std.exe < std.in > std.out");

			system("test.exe < std.in > test.out");

			if(system("fc std.out test.out")) return 1;

		}

	return 0;

}

我发现如果直接freopen的话system的调用会失效。

注意那个fflush。我发现如果把造数据和对拍写在一起，就是又有输出又有调用其他程序的话，在输出和调用之间会卡住。这时候需要加个cerr或者fflush刷新一下。

巴特西

Topcoder10566 IncreasingNumber

IncreasingNumber

题解

最新文章

热门文章