就是个需要实现的比较精细的数位DP 枚举长度 如果长度是奇数 那么需要的是奇数交替和的和 与 偶数交替和的和 的 差 如果长度是偶数 那么需要的是奇数交替和的和 与 偶数交替和的和 的 和 我一开始以为奇数偶数只要看最后一位就可以了 实际上在奇数进制下并不是这样
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define cl(x) memset(x,0,sizeof(x)) using namespace std; typedef long long ll; const int N=55; ll n; int b; ll pw[N]; int w[N],m; ll f[N][2],tot[N][2]; inline ll calc(int len){ cl(f),cl(tot); ll t=pw[len-1]; tot[len+1][0]=1; for (int j=1;j<b;j++) for (int k=0;k<2;k++) f[len][k^((t*j)&1)]+=f[len+1][k]+j*tot[len+1][k],tot[len][k^((t*j)&1)]+=tot[len+1][k]; t/=b; for (int i=len-1;i;i--,t/=b){ for (int j=0;j<b;j++) for (int k=0;k<2;k++) f[i][k^((t*j)&1)]+=f[i+1][k]+((len-i)&1?-j:j)*tot[i+1][k],tot[i][k^((t*j)&1)]+=tot[i+1][k]; } if (len&1) return pw[len-1]&1?f[1][1]-f[1][0]:f[1][0]-f[1][1]; else return f[1][0]+f[1][1]; } inline ll Solve(){ cl(f),cl(tot); ll t=pw[m-1]; tot[m+1][0]=1; for (int j=1;j<w[m];j++) for (int k=0;k<2;k++) f[m][k^((t*j)&1)]+=f[m+1][k]+j*tot[m+1][k],tot[m][k^((t*j)&1)]+=tot[m+1][k]; int cur=w[m],g=(t*w[m])&1; t/=b; for (int i=m-1;i;i--,t/=b){ for (int j=0;j<b;j++) for (int k=0;k<2;k++) f[i][k^((t*j)&1)]+=f[i+1][k]+((m-i)&1?-j:j)*tot[i+1][k],tot[i][k^((t*j)&1)]+=tot[i+1][k]; for (int j=0;j<w[i];j++) f[i][g^((t*j)&1)]+=cur+((m-i)&1?-j:j),tot[i][g^((t*j)&1)]++; cur+=(m-i)&1?-w[i]:w[i],g^=(t*w[i])&1; } if (m&1) return pw[m-1]&1?f[1][1]-f[1][0]:f[1][0]-f[1][1]; else return f[1][0]+f[1][1]; } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d%lld",&b,&n); n++; for (ll t=n;t;w[++m]=t%b,t/=b); pw[0]=1; for (int i=1;i<=m;i++) pw[i]=pw[i-1]*b; int pot=0; ll Ans=0; for (int len=1;len<m;len++){ if (~pot&1) Ans+=calc(len); else Ans-=calc(len); pot+=(pw[len]-pw[len-1])*len; } if (~pot&1) Ans+=Solve(); else Ans-=Solve(); printf("%lld\n",Ans); return 0; }