zoj3416 Balanced Number

时间:2022-10-13 18:45:15

链接

这题纠结了好久,刚开始想到的是正解,不过想到可能会出现一个数支点不唯一的情况,这样就多算了,其实是我想多了,一个数只有一个支点。

这样就好像想到了,枚举支点的位置,保存力矩的状态。

dp[i][k][s] i为当前处理位 k为支点 s为到目前为止根据支点算出来的部分力矩。

有一点需要注意算0的时候 会有len个支点 所以要减掉重算的len-1个

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 2550
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
LL dp[][][N];
int d[],g;
LL dfs(int i,bool e,int k,int s)
{
if(s<) return ;
if(i==-)
return s==;
if(!e&&~dp[i][k][s])
return dp[i][k][s];
int mk = e?d[i]:;
LL ans = ;
for(int j = ;j <= mk ;j++)
{
//ans+=dfs(i-1,e&&j==mk,s+=j*i,sum+=j);
ans+=dfs(i-,e&&j==mk,k,s+(i-k)*j);
}
// cout<<ans<<" "<<i<<endl;
return e?ans:dp[i][k][s] = ans;
}
LL cal(LL x)
{
if(x<) return ;
if(x==) return ;
g = ;
while(x)
{
d[g++] = x%;
x/=;
}
LL ans = ;
for(int i = ;i < g ; i++)
{
ans+=dfs(g-,,i,);
}
//return dfs(g-1,1,N,0);
return ans-g+;
}
int main()
{
int t;
LL l,r;
cin>>t;
memset(dp,-,sizeof(dp));
while(t--)
{
cin>>l>>r;
cout<<cal(r)-cal(l-)<<endl;
}
return ;
}