SPOJ BALNUM
2024-09-17 06:08:03
一开始题看错了。。。dp[pos][sets][viss],其中sets表示出现次数,viss表示出现没有。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long t,l,r,dp[][][],bit[],ret=;
void get_bit(long long x)
{
ret=;
while (x) {bit[++ret]=x%;x/=;}
}
long long check(long long sets,long long viss)
{
for (long long i=;i<=;i++)
{
if (!(viss&(<<i))) continue;
if ((i&) && (sets&(<<i))) return ;
if ((!(i&)) && (!(sets&(<<i)))) return ;
}
return ;
}
long long dfs(long long pos,long long sets,long long viss,bool flag)
{
if (!pos) return check(sets,viss);
if ((!flag) && (~dp[pos][sets][viss])) return dp[pos][sets][viss];
long long ans=,up=flag?bit[pos]:;
for (long long i=;i<=up;i++)
ans+=dfs(pos-,sets^(<<i),viss|(<<i),flag&&(i==up));
if (!flag) dp[pos][sets][viss]=ans;
return ans;
}
long long work(long long x)
{
if (!x) return ;
get_bit(x);long long ans=;
for (long long i=;i<=ret-;i++)
for (long long j=;j<=;j++)
ans+=dfs(i-,<<j,<<j,);
for (long long j=;j<=bit[ret]-;j++)
ans+=dfs(ret-,<<j,<<j,);
ans+=dfs(ret-,<<bit[ret],<<bit[ret],);
return ans;
}
int main()
{
scanf("%lld",&t);memset(dp,-,sizeof(dp));
for (long long i=;i<=t;i++)
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",work(r)-work(l-));
}
return ;
}
最新文章
- 【清华集训】楼房重建 BZOJ 2957
- Spring3.0目录
- c++ 中static关键字
- Java 最简单的批处理
- 【转】火火火火火!看HomeKit如何改变物联网和智能家居?
- python运维开发(二十)----models操作、中间件、缓存、信号、分页
- 玩转Web之JavaScript(三)-----javaScript语法总结(三) 窗口/滚动条/文本的相关语法
- Java学习网站大全
- 【Docker笔记】-开启TCP管理端口
- leetcode — remove-duplicates-from-sorted-list-ii
- Django create和save方法
- [NOIP2014D2]
- Win32 SDK:ListBox 为什么不整个 LB_SETTEXT
- haploview画出所有SNP的LD关系图
- 现在越来越喜欢用ajax传值了,这样能让网站的体验性很好,今天就总结了一下常用的
- nfs 客户端挂住
- Python: TypeError: &#39;dict&#39; object is not callable
- loadrunner怎么解决录制完成后脚本为空
- def函数之另类用法
- Metal Programming Guide