题目
思路：由于数位最大为10，所以我们可以分出所有3出现位置和个数的所有情况，最多也就 210种情况，然后对每种可行情况进行 dfs.
dfs进行的每一层说明，前面 0−now都是跟给定的数字相同的，那么当前这一位就有两种取法，一个是小于给定的数字，一个是等于给定的数字。
1.小于给定的数字我们好解决，后面的位置没有被3放的位置我们可以放任意的数字，但是最后一位不能放偶数。
2.直接递归下一位即可。
3.若当前已经递归完成，若最后没有放三且是偶数则贡献为0，否则为1.
详细细节见代码
#include<iostream>
#include <cstring>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){if(b<=0)return 1;LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
char a[33];
int res[333],cnt,n,q[11];
LL ans;
LL f(int x,int now){
int mid=0;
if(now==n)return ((res[n-1]==0&&(a[n-1]-'0')%2==0)?0:1);
for(int i=now+1;i<n;i++)mid+=res[i];
if(res[now]){
if(a[now]-'0'<3)return 0;
if(a[now]-'0'==3)return f(x,now+1);
if(now==n-1)return 1;
return (res[n-1]?powmod(9,n-now-mid-1,1e18):(powmod(9,n-now-mid-1,1e18)/9*4));
}
if(a[now]=='0')return f(x,now+1);
if(now==n-1){
return a[n-1]-'0'+1-q[a[n-1]-'0']-(a[n-1]-'0'>=3);
}
return max(0,a[now]-'0'-(a[now]-'0'>3))*(res[n-1]?powmod(9,n-now-mid-1,1e18):(powmod(9,n-now-mid-1,1e18)/9*4))+(a[now]!='3'?f(x,now+1):0);
}
int main(){
ios::sync_with_stdio(false);
cin>>a;
n=strlen(a);
q[0]=1;q[1]=1;q[2]=2;q[3]=2;q[4]=3;q[5]=3;
q[6]=4;q[7]=4;q[8]=5;q[9]=5;
for(int i=0;i<(1<<n);i++){
memset(res,0,sizeof res);
cnt=0;
for(int j=0;j<n;j++){
if((1<<j)&i)res[j]=1,cnt++;
}
if(res[0]&&a[0]-'0'<3)continue;
if(cnt>n)continue;
ans+=1ll*cnt*f(i,0);
}
cout<<ans<<endl;
return 0;
}
看了大佬们的另一种写法，感觉智商压制了。。。。。。。。
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
ll n;
while(~scanf("%lld",&n)){
ll ans=0,t1=1,k=0,no;
while(n){
ll t=t1;
if(t1==1)t*=2;
ans+=n/10*t/2;//这一位是3，前不为0
cout<<n/10*t/2<<endl;
no=n%10;
if(no>3)ans+=t/2;//前面都是0
else if(no==3)ans+=(t1==1?1:(k+1)/2);
k+=no*t1;
t1*=10;
n/=10;
}
printf("%lld\n",ans);
}
return 0;
}
这种做法直接考虑每一位，两种情况，这一位是3前面不是0，这一位是3前面是0，然后对3出现的次数直接累加即可。。，复杂度
O(数位)…
京公网安备 11010502036488号