C. Travelling Salesman and Special Numbers (binary + combination number)

C. Travelling Salesman and Special Numbers

题意
给定一个数 n,问 1 - n A total of more than a few can pass m The following conversion into 1？

• 对于一个数 x,If the corresponding binary altogether k 位为 1,那么 x 变为 k.

$(1\le n<2^{1000},0\le m\le 1000)$
$nGive\; without\; leading\; zeros\; binary.$

思路
虽然 n 很大,But the large number of execution again after conversion are less than 1000 了.
Assume that perform once operations into x,x 经过 k Operations into1,那么 n 就要执行 k+1 次操作变为1.
So to violence and the 1-1000 How many times all number respectively in the need to convert into1,假设一个数 x 经过 k 次操作变为1,So if a number k+1 次操作变为1,其二进制中1的个数就为 x.
For each operating frequency k,Stored in advance of its corresponding to the original number of binary expression 1 的个数.
例如：If the operation frequency as 2,Then the original binary should have 2 或 4 或 8 或 16 … 个 1.

现在给定了 操作次数为 m,We need according to the given n The binary expression to find 1-n A total of more than a few meet its binary have v[0], v[1], v[2]… 个 1.

对于 n 的二进制每一位 1 来说,如果这一位 1 变为 0 了,Then the modified whatever was behind all three 0 是 1,都比原来的 n 小.Assume that the front position of cnt 个1,后面还有 left 个位置,You can from the back of the all in the position to select v[i] - cnt 个 和 cnt Of a total v[i] 个1.

遍历所有 1 的位置,For every position traverse need 1 的个数,O combinations of accumulation.

int cnt = 0;
for(int i=1;i<=n;i++)
{
    
	if(a[i] != '1') continue;
	
	for(int x : vv)
	{
    
		int left = n - i;
		if(cnt > x) continue;
		if(left < x-cnt) continue;
		ans = (ans + C[left][x-cnt]) % mod;
	}
	cnt ++;
}

需要注意的细节：

• The above is determine 1~n-1 的数,n 本身的 1 The number of to judge whether it is need to meet 1 的个数,如果是,ans ++;
• 当操作数为 1 时,Need to meet in the binary 1 个 1,But if the number is 1 的话,Its operands should be 0,Need to delete the original number is 1 的情况;
• 当操作数为 0 时,原数为 1,n ≥1 一定满足,答案一定为 1.

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
char a[N];
vector<int> v[20];
int C[1010][1010];

void init()
{
    
	for(int i=1;i<1000;i++)
	{
    
		int x = i;
		int cnt = 0;
		while(x != 1)
		{
    
			cnt ++;
			bitset<12> f(x);
			x = f.count();
		}
		v[cnt+1].push_back(i);
	}
	
	C[0][0] = 1;
	for(int i=1;i<=1000;i++)
	{
    
		C[i][0] = 1;
		for(int j=1;j<=i;j++)
		{
    
			C[i][j] = C[i-1][j-1] + C[i-1][j];
			C[i][j] %= mod;
		}
	}
}

signed main(){
    
	Ios;
	init();
	
	cin >> a+1;
	n = strlen(a+1);
	
	cin >> m;
	
	if(m > 5){
    
		cout << 0; return 0;
	}
	if(m == 1 && n == 1){
    
		cout << 0; return 0;
	}
	if(m == 0){
    
		cout << 1; return 0;
	}
	
	vector<int> vv = v[m];
	
	int ans = 0;
	if(m == 1) ans --;
	
	int t = 0;
	for(int i=1;i<=n;i++) if(a[i] == '1') t++;
	for(int x : vv) if(x == t) ans ++;
	
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
    
		if(a[i] != '1') continue;
		
		for(int x : vv)
		{
    
			int left = n - i;
			if(cnt > x) continue;
			if(left < x-cnt) continue;
			ans = (ans + C[left][x-cnt]) % mod;
		}
		cnt ++;
	}
	cout << ans;
	
	return 0;
}