C. Travelling Salesman and Special Numbers(数位)

首先因为二进制最多1000位,操作一次后数就变成了[1,1000]的数

所以要求数字x满足操作k次回到1

$其实就是枚举[1,1000]中操作次数是k-1次的数i$

$然后计算二进制有i个1且小于原数字的有多少个累加即可$

前面思维难度都不大,关键是如何找有i个1且小于原数字的数量?

$不妨我们把最长公共前缀记作j,原数字n长度记作len$

$j\in [1,len],那么前j位都相同,第j+1位是0且n的第j+1位是1$

$我们就这样去枚举它的公共前缀,计算前缀前1的数$

$然后第[j+2,len]的二进制就可以任意,组合数来计算$

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1009; const int mod=1e9+7; using namespace std; ll c[maxn][maxn],dp[maxn],k,pre[maxn]; char a[maxn]; int calucate(int x){ int cnt=0; while(x!=1){ int temp=0; while(x) { if(x&1) temp++; x>>=1; } x=temp,cnt++; } return cnt; } void init() { c[0][0]=1; for(int i=1;i<=1000;i++) { c[i][0]=1; for(int j=1;j<=1000;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } } int main() { cin >> (a+1) >> k; if(k==0) cout<<1; else if(k==1) cout<<strlen(a+1)-1; else { init();//求组合数 int len=strlen(a+1),num=0; for(int i=1;i<=len;i++) pre[i] = pre[i-1]+(a[i]=='1'); dp[ pre[len] ] = 1; for(int i=0;i<len;i++)//公共前缀长度 { if(a[i+1]=='0') continue; //让第i+1位变成0,那么现在已经更小了,[i+2,len]是任意的 int num=pre[i],tot=len-(i+2)+1; for(int bit=0;bit<=tot;bit++)//放bit个1 dp[bit+num]=(dp[bit+num]+c[tot][bit])%mod; } ll ans=0; for(int i=1;i<=len;i++) if(calucate(i)==k-1) ans=(ans+dp[i])%mod; cout<<ans; } }