赛场上竟然只有我写了数学做法，大家做法都是 $O(klgn)$ 极其更劣的，而且占用空间高，那么我们说一下 $O(k+lgn)$ 做法 my submission。

我们考虑枚举每一位，并且假设前面的位置已经保持原来大数不变，那么这里还需要放的数已经确定好了。

如果某一位原数不是 $0$ 那么放小于这个数的后面的数字就可以随便放 $(w_i-1)\times \binom{n-i}{k-cnt-1}\times 9^{k-cnt-1} + \binom{n-i}{k-cnt}\times 9^{k-cnt}$。

cnt表示前面非0数，i表示当前位置。

最后 $cnt=k$ 时 $++ans$，表示到目前为止后面都填 $0$ 就行并 $break$ 。

贴一下部分代码

if(x[i]!='0')ans+=(x[i]-'0'-1)*C(n-i-1,k-cnt-1)*pow(9,k-cnt-1);
	if(x[i]!='0')ans+=C(n-i-1,k-cnt)*pow(9,k-cnt);
	if(x[i]!='0')cnt++;
	if(cnt==k){
		ans++;
		break;
	}

于是我决定出一个加强版预计数据范围$n\le 10^{10^6},k\le 10^6,mod=10^9+7$。

加强版链接