文档章节

CF401D Roman and Numbers 状压DP

o
 osc_z1hvg4cu
发布于 2018/04/24 21:24
字数 640
阅读 13
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

CF401D

题意翻译

将n(n<=10^18)的各位数字重新排列(不允许有前导零) 求 可以构造几个mod m等于0的数字

题目描述

Roman is a young mathematician, very famous in Uzhland. Unfortunately, Sereja doesn't think so. To make Sereja change his mind, Roman is ready to solve any mathematical problem. After some thought, Sereja asked Roma to find, how many numbers are close to number n n n , modulo m m m .

Number x x x is considered close to number n n n modulo m m m , if:

  • it can be obtained by rearranging the digits of number n n n ,
  • it doesn't have any leading zeroes,
  • the remainder after dividing number x x x by m m m equals 0.

Roman is a good mathematician, but the number of such numbers is too huge for him. So he asks you to help him.

输入输出格式

输入格式:

The first line contains two integers: n n n $ (1<=n&lt;10^{18}) $ and m m m (1<=m<=100) (1<=m<=100) (1<=m<=100) .

输出格式:

In a single line print a single integer — the number of numbers close to number n n n modulo m m m .

输入输出样例

输入样例#1: 
104 2
输出样例#1: 
3
输入样例#2: 
223 4
输出样例#2: 
1
输入样例#3: 
7067678 8
输出样例#3: 
47

说明

In the first sample the required numbers are: 104, 140, 410.

In the second sample the required number is 232.

 

分析:

题目描述确实比较吓人, n位数字重新排列最多可以创造出多少个%m == 0 的数;
其实就是状态压缩;
定义f [i] [j] , i表示一个二进制数, 1代表选这个数, j代表由n个数中选出x个组成的数%m==j;
 

转移方程 : f[i|(1 << k)][(j * 10 + x) % m] += f[i][j];

 

意义:对于第k位数x, 都可以由不选他转移到选他, 就是 i -> i |(1 << k);

然后第二维就由 j -> (j *10 + x) % m   (显然);

 

注意 : 因为状态压缩是暴力的把每一位数当成与前边的数都不一样, 比如 11 ,应该算一次, 但是我们却算了两次;

方案 : 1. 最后除以cnt!(cnt为一个数出现了多少次)。

    2. 直接去重。

代码奉上:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn (1 << 18) + 5
#define int long long

int n, m;

int s[21];

int f[maxn][105];

char ch[20];

bool vis[20];

signed main()
{
	scanf("%s%lld", &ch, &m);
	
	int n = strlen(ch);
	
	f[0][0] = 1;
	
	int e = (1 << n);
	for(register int i = 0 ; i < e ; i ++)
	{
		for(register int j = 0 ; j < m ; j ++)
		{
			memset(vis, 0, sizeof vis);
			for(register int k = 0 ; k < n ; k ++)
			{
				int x = ch[k] - '0';
				if(i & (1 << k)) continue;
				if(i == 0 && x == 0) continue;
				if(vis[x]) continue;
				vis[x] = 1;
				f[i|(1<<k)][(j*10+x)%m] += f[i][j];
			}
		}
	}
	
	cout << f[e-1][0];
	return 0;

	
}

 

 
上一篇: 关于求负数补码
下一篇: 进程Process
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
动态规划分类题目总结

动态规划分类有很多划分方法,网上有很多是按照状态来分,分为一维、二维、区间、树形等等。我觉得还是按功能即解决的问题的类型以及难易程度来分比较好,下面按照我自己的理解和归纳,把动态...

osc_k7wip3sn
2018/08/07
0
0
dp有哪些种类

dp有哪些种类 一、总结 一句话总结: 二、dp动态规划分类详解 动态规划一直是ACM竞赛中的重点,同时又是难点,因为该算法时间效率高,代码量少,多元性强,主要考察思维能力、建模抽象能力、...

osc_lpp1ias6
2018/07/09
2
0
[总结]2020年1月 OI学习/刷题记录

2020/1/1 UOJ #275. 【清华集训2016】组合数问题 Lucas+数位DP UOJ #276. 【清华集训2016】汽水 二分答案+点分治 Luogu P3690 【模板】Link Cut Tree (动态树) LCT UOJ #274. 【清华集训2...

osc_56wm84nt
01/01
1
0
状压DP初探·总结

2018过农历新年这几天,学了一下状态压缩动态规划,现在先总结一下。 状态压缩其实是一种并没有改变dp本质的优化方法,阶段还是要照分,状态还是老样子,决策依旧要做,转移方程还是得列,最...

osc_o18rkfva
2018/02/21
2
0
洛谷状压DP做题记录

P2915 [USACO08NOV]奶牛混合起来Mixed Up 题面 确实是状压的入门题 用dp[i][j] 表示以i结尾,状态为j时的方案数,代码如下: #include<bits/stdc++.h>using namespace std;const int maxn=1e...

osc_ugeljcjn
2019/07/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java架构师成长路线-高并发网络编程的分类

鲁班学院java架构师成长路线 随着互联网时代的到来,高并发网络编程这一新鲜名词早已跃然于纸上,为了满足大众眼光的需求,我为大家找了些关于高并发网络编程方面的资料,本文便来介绍高并发...

osc_o494ayqf
22分钟前
5
0
python dict乱码如何解决

定义字典并直接输出,结果输出结果中文是乱码展示 d={'name':'lily','age':18,'sex':'女','no':1121}print d 输出结果: {'age': 18, 'no': 1121, 'name': 'lily', 'sex': '\xe5\xa5\xb3'}...

osc_9mjo6c4e
22分钟前
14
0
硬肝50天,18w字的实战编程资料《重学Java设计模式》终于 出炉了

沉淀、分享、成长,让自己和他人都能有所收获! 一、前言 作者从5月20日那天投身实战型设计模式打磨,通过模拟互联网业务开发实际需求作为学习场景,讲解设计模式。 全书共计22个真实业务场景...

osc_zls6dx9i
24分钟前
20
0
怎么才能让Spring AOP有最大的作用--乐字节java

Spring AOP 日志处理带来的问题 我们有一个Pay(接口) 然后两个实现类DollarPay和RmbPay,都需要重写pay()方法, 这时我们需要对pay方法进行性能监控,日志的添加等等怎么做? 最容易想到的方法...

osc_sb30h1xb
26分钟前
14
0
Python 实现将numpy中的nan和inf,nan替换成对应的均值

nan:not a number inf:infinity;正无穷 numpy中的nan和inf都是float类型 t!=t 返回bool类型的数组(矩阵) np.count_nonzero() 返回的是数组中的非0元素个数;true的个数。 np.isnan() 返回b...

osc_sfl7wfr9
28分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部