bzoj 1072: [SCOI2007]排列perm【状压dp】
2024-09-08 13:53:46
先写了个next_permutation结果T了,于是开始写状压
设f[s][i]为选取状态为s,选的数模d为i的方案数,去重的话直接除以每个数字的出现次数的阶乘即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=20;
int T,d,n,a[N],fac[N],c[N],f[2005][2005];
char s[N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s%d",s+1,&d);
n=strlen(s+1);
for(int i=0;i<=9;i++)
fac[i]=1,c[i]=0;
for(int i=1;i<=n;i++)
{
a[i]=s[i]-'0';
c[a[i]]++;
fac[a[i]]*=c[a[i]];
}
for(int i=0;i<(1<<n);i++)
for(int k=0;k<d;k++)
f[i][k]=0;
f[0][0]=1;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<d;j++)
for(int k=1;k<=n;k++)
if(!((1<<(k-1))&i))
f[i|(1<<(k-1))][(a[k]+j*10)%d]+=f[i][j];
for(int i=0;i<=9;i++)
f[(1<<n)-1][0]/=fac[i];
printf("%d\n",f[(1<<n)-1][0]);
}
return 0;
}
最新文章
- 原创 C++作用域 (二)
- 盐水的故事[HDU1408]
- IE中无法执行JS脚本 解决WINDOWS SERVER 2008弹出INTERNET EXPLORER增强安全配置正在阻止来自下列网站的内容
- CSS实例
- HTML5 :b/strong加粗,i/em倾斜区别
- java 与 R 相互调用
- 隐藏index.php - ThinkPHP完全开发手册 - 3.1
- vbscript multiple line syntax
- Linux(Centos)之安装tomcat并且部署Java Web项目(转)
- C# json Helper
- 环境配置与JBoss安装-EJB3.0入门经典学习笔记(1)
- ORACLE uuid自己主动生成主键
- flannel 网络问题排查
- JS滚动显示
- ruby 对象转换哈希(Hash)
- Django 学习第十一天——中间键和上下文处理器
- js 创建标签执行
- BeautifulSoup下Unicode乱码解决
- 流媒体压力测试rtmp&;hls(含推流和拉流)
- [No0000184]JAVA语言学校的危险性
热门文章
- HDU 5573 Binary Tree【构造】
- delightful world--计蒜客(DFS)
- P1918 保龄球 洛谷
- 51nod 1499 (最小割)
- QT程序--CS1.6文件整理及安装器
- The sandbox is not sync with the Podfile.lock
- Android 性能优化探究
- ecshop广告宽度值必须在1到1024之间的解决方法
- 1.NetDh框架之数据库操作层--Dapper简单封装,可支持多库实例、多种数据库类型等(附源码和示例代码)
- Docker vs. Kubernetes vs. Apache Mesos: Why What You Think You Know is Probably Wrong