C++ 解法, 执行用时: 49ms, 内存消耗: 15872K, 提交时间: 2021-10-07 20:33:20

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N=10005;
const int mod=1e9+7;
#define ll long long 
vector<int>dp[366][366][2];
ll b[366];
ll a[366];
vector<int>add(vector<int>&A,vector<int>&B){
	if(A.size()<B.size())return add(B,A);
	vector<int>C;
	int t=0;
	for(int i=0;i<A.size();i++){
		t+=A[i];
		if(i<B.size())t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t)C.push_back(t);
	return C;
}
vector<int>sub(vector<int>& A,vector<int>&B){
	vector<int>C;
	for(int i=0,t=0;i<A.size();i++){
		t=A[i]-t;
		if(i<B.size())t-=B[i];
		C.push_back((t+10)%10);
		if(t<0)t=1;
		else t=0;
	}
	while(C.size()>1&&C.back()==0)C.pop_back();
	return C;
}
vector<int>dfs(ll pos,ll limit,ll lead,ll flag,ll len){
	vector<int>ans;
	ans.push_back(0);
	vector<int>B;
	if(pos==-1&&flag==0)B.push_back(1);
	if(pos==-1)return (flag==0)?add(ans,B):ans;
	if(!limit&&!lead&&dp[pos][len][flag][0]!=-1)return dp[pos][len][flag];
	int up=limit?a[pos]:1;
	for(int i=0;i<=up;i++){
		b[pos]=i;
		vector<int>x=dfs(pos-1,limit&&i==up,lead&&i==0,(pos<=(len-1)/2)?(flag|(b[len-pos]!=i)):flag,(lead&&i==0)?len-1:len);
		ans=add(ans,x);
	}
	if(!limit&&!lead)dp[pos][len][flag]=ans;
	return ans;
}

char s[366];
vector<int>div(vector<int>&A,int b,int &r){
	vector<int>C;
	r=0;
	for(int i=A.size()-1;i>=0;i--){
		r=r*10+A[i];
		C.push_back(r/b);
		r%=b;
	}
	reverse(C.begin(),C.end());
	while(C.size()>1&&C.back()==0)C.pop_back();
	return C;
}
signed main(){
	for(int i=0;i<334;i++){
		for(int j=0;j<334;j++){
			for(int k=0;k<2;k++)
			{
				dp[i][j][k].push_back(-1);
			}
		}
	}
	scanf("%s",s);
	int n=strlen(s);
	vector<int>A,B;
	for(int i=n-1;i>=0;i--)A.push_back(s[i]-'0');
	int r;
	int cnt=0;
	while(!(A.size()==1&&A[0]==0)){
		A=div(A,2,r);
		a[cnt++]=r;
	}
	B.push_back(1);
	A=dfs(cnt-1,1,1,0,cnt-1);
	A=sub(A,B);
	for(int i=A.size()-1;i>=0;i--){
		printf("%d",A[i]);
	}
	scanf(" ");

}