Travelling Salesman and Special Numbers CodeForces

大意: 对于一个数$x$, 每次操作可将$x$变为$x$二进制中1的个数

定义经过k次操作变为1的数为好数, 求$[1,n]$中有多少个好数

注意到n二进制位最大1000位, 经过一次操作后一定变为1000以内的数, 所以可以暴力求出1000以内的数变为1的操作次数,

记$G_i$为$[1,n]$中二进制中1的个数为i的个数, 数位dp求出$G_i$后, 再用乘法原理就可以得出结果

要特判k为0和1的情况, k=1时会将1多算一次最后减去1

#include <iostream>

#include <bitset>

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

typedef long long ll;

const int P = 1e9+7, N = 1e3+10;

bitset<N> bit;

ll G[N], cnt[N], C, k;

int main() {

	cin>>bit>>k;

	if (!k) return cout<<1<<endl,0;

	PER(j,0,N-1) {

		PER(i,1,N-1) (G[i]+=G[i-1])%=P;

		if (bit[j]) ++G[C++];

	}

	++G[C];

	REP(i,2,N-1) cnt[i]=cnt[__builtin_popcount(i)]+1;

	ll ans = 0;

	REP(i,1,N-1) if (cnt[i]==k-1) (ans+=G[i])%=P;

	if (k==1) --ans;

	cout<<ans<<endl;

}

巴特西

Travelling Salesman and Special Numbers CodeForces - 914C (数位dp)

最新文章

热门文章