这玩意好像甚至有递推式……不太懂
（为什么是图片？cnblogs 第一个公式没渲染成功）
时间复杂度是 \(O(4^{\deg F}\log K)\) 的。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100;
int f[17][maxn],cur[10],al[4];
int calc(int K){// cerr<<"___________________________________"<<endl;// cerr<<"solve "<<K<<endl;memset(f,0,sizeof(f));f[1][1]=1;for(int R=2;R<=62;R++){if(K&(1ll<<R-2)){for(int j=0;j<4;j++)al[j]=0;for(int j=0;j<16;j++)al[0]+=(j&1)*(1<<j);for(int j=0;j<16;j++)al[1]+=(__builtin_popcount(j)&1)*(1<<j);for(int j=0;j<16;j++)al[2]+=(((j&1)+((j>>1)&1)+((j>>2)&1))&1)*(1<<j);for(int j=0;j<16;j++)al[3]+=((((j>>1)&1)+((j>>3)&1))&1)*(1<<j);for(int j=1;j<16;j++){int c1=(1<<16)-1,c2=0;for(int k=0;k<4;k++){if(j&(1<<k))c1=c1&al[k];else c2=c2|al[k];}int x=c1-(c1&c2);for(int l=0;l<16;l++)if((1<<l)&x)f[j][R]+=f[l][R-1];}for(int j=0;j<4;j++)al[j]=0;for(int j=0;j<16;j++)al[0]+=(((j&1)+((j>>2)&1))&1)*(1<<j);for(int j=0;j<16;j++)al[1]+=((((j>>1)&1)+((j>>2)&1)+((j>>3)&1))&1)*(1<<j);for(int j=0;j<16;j++)al[2]+=(__builtin_popcount(j)&1)*(1<<j);for(int j=0;j<16;j++)al[3]+=((j>>3)&1)*(1<<j);for(int j=1;j<16;j++){int c1=(1<<16)-1,c2=0;for(int k=0;k<4;k++){if(j&(1<<k))c1=c1&al[k];else c2=c2|al[k];}int x=c1-(c1&c2);for(int l=0;l<16;l++)if((1<<l)&x)f[j][R]+=f[l][R-1];}}else{for(int j=0;j<4;j++)al[j]=0;for(int j=0;j<16;j++)al[0]+=(j&1)*(1<<j);for(int j=0;j<16;j++)al[2]+=((j>>1)&1)*(1<<j);for(int j=1;j<16;j++){int c1=(1<<16)-1,c2=0;for(int k=0;k<4;k++){if(j&(1<<k))c1=c1&al[k];else c2=c2|al[k];}int x=c1-(c1&c2);for(int l=0;l<16;l++)if((1<<l)&x)f[j][R]+=f[l][R-1];}for(int j=0;j<4;j++)al[j]=0;for(int j=0;j<16;j++)al[0]+=((j>>2)&1)*(1<<j);for(int j=0;j<16;j++)al[2]+=((j>>3)&1)*(1<<j);for(int j=1;j<16;j++){int c1=(1<<16)-1,c2=0;for(int k=0;k<4;k++){if(j&(1<<k))c1=c1&al[k];else c2=c2|al[k];}int x=c1-(c1&c2);for(int l=0;l<16;l++)if((1<<l)&x)f[j][R]+=f[l][R-1];}}// for(int j=0;j<16;j++)cerr<<f[j][R]<<" ";cerr<<endl;}int ans=0;for(int i=0;i<16;i++)ans+=f[i][62]*__builtin_popcount(i);// cerr<<K<<" ans = "<<ans<<endl;return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// cout<<calc(100)<<endl;int K,res=0;cin>>K;for(int i=1,z=1;i<=K;i++)z=z*10,res+=calc(z);cout<<res<<endl;return 0;
}
