F - Balanced Number
2024-08-27 15:48:23
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
#include <cmath>
#include <vector> #define Faster ios::sync_with_stdio(false),cin.tie(0)
#define Read freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
#define Close fclose(stdin),fclose(stdout)
const int maxn = 1e4 + ;
using namespace std;
const int MOD = 1e9+;
typedef long long ll; ll dp[][][];
int a[]; ll dfs(int pos, int cut, int sum, bool limit){
if (pos == -) return sum?:; //sum为0的时候说明是平衡的
if (sum < ) return ; //sum < 0 就肯定不平衡了返回0
if(!limit && dp[pos][cut][sum] != -)
return dp[pos][cut][sum];
int up = limit?a[pos]:;
ll ans = ;
for(int i = ; i <= up;i++){
ans += dfs(pos-, cut, sum + (pos-cut)*i, limit && a[pos] == i);
}
if(!limit)
dp[pos][cut][sum] = ans;
return ans;
} ll solve(ll x){
int pos = ;
while(x){
a[pos++] = x%;
x /= ;
}
ll ans = ;
for(int i = ;i < pos;i++){
ans += dfs(pos-, i, , true);
}
return ans - pos + ;
//因为0多加了(pos - 1)次
} int main(){
Faster;
int t;
cin >> t;
memset(dp, -, sizeof(dp));
while(t--){
ll l, r;
cin >> l >> r;
ll ans = solve(r) - solve(l-);
cout << ans << endl;
}
return ;
}
最新文章
- [HAOI2009]求回文串
- EBS中OPM成本更新处理流程及对应的表结构、SLA表
- FTP文件管理
- mapreduce流程中的几个关键点
- Java使用for循环打印乘法口诀(正倒左右三角形)
- JQuery Mobile 页面参数传递(转)
- smarty基本语法
- bnu A Matrix 北京邀请赛A题
- Js_字符串操作
- Codeforces Round #339 Div.2 C - Peter and Snow Blower
- 生成Excel直接以流或字节形式发给客户端,无需在服务生成一个实体文件。
- 解决版本冲突-使用SVN主干与分支功能
- Java 8 VM GC Tuning Guide Charter3-4
- How to Cope with Deadlocks
- [原创.数据可视化系列之十二]使用 nodejs通过async await建立同步数据抓取
- spring源码 — 五、事务
- svn 服务器部署
- 013_RomanToInteger
- SQL Server数据库开发的二十一条军规
- nfs 提高传输速度