关键词：
D. Roman and Numbers(状压dp)
把 n n n的每一位状压，问题等价于选择一个顺序走完这 c n t cnt cnt个位使得 ( m o d m ) = 0 \\pmodm=0 (modm)=0答案。
令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示状态 i i i 模 m m m余 j j j的答案。
转移时需要注意最高位对应的数不能为 0 0 0。
初始化： d p [ 0 ] [ 0 ] = 1 dp[0][0]=1 dp[0][0]=1。
而且同一个数字不能在一个状态转移多次，所以可以用一个标记数组，标记哪些数字已经转移过了。
时间复杂度： O ( 10 m × 2 18 ) O(10m\\times 2^18) O(10m×218)
// Problem: D. Roman and Numbers
// Contest: Codeforces - Codeforces Round #235 (Div. 2)
// URL: https://codeforces.ml/problemset/problem/401/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Date: 2021-08-11 19:32:34
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+5,M=(1<<18)+1,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n)
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\\n",a[n]);
ll dp[M][101];
int a[20],cnt,vis[20];
int main()
ll n;int m;scanf("%lld%d",&n,&m);
while(n) a[++cnt]=n%10,n/=10;
int st=1<<cnt;
dp[0][0]=1;
for(int i=0;i<st;i++)
mst(vis,0);
for(int j=0;j<cnt;j++)
if((1<<j)==i&&!a[j+1]) continue;
if(vis[a[j+1]]||!(i>>j&1)) continue;
vis[a[j+1]]=1;
for(int k=0;k<m;k++)
dp[i][(k*10+a[j+1])%m]+=dp[i^(1<<j)][k];
printf("%lld\\n",dp[st-1][0]);
return 0;
状压dp小结
1.要状压的那一维，所有有关的下标要从0开始，而不是从1开始2.预处理很重要，可以说基本所有的状压dp都要有预处理这玩意 查看详情
hoj2662经典状压dp//myfirst状压dp
题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言：用dp解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。但是有这样的一类题目，它们具有dp问题的特性，但状态中所包含的信息过多，... 查看详情
动态规划---状压dp2(代码片段)
今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情
状压dp(代码片段)
这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09 00001001&5 000001011 &nb 查看详情
foreignnumber[状压dp]
...leInput 123455SampleOutput 24HINT Solution 我们运用状压DP，令f[j][opt]表示当前余数为j，状态为opt的方案。 状态记录的是：各个数字被用了几次。 那么我们就可以状压了。先 查看详情
第一次接触状压dp(代码片段)
状压DP入门及理解*（另类的暴力）* 一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。 状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。 &... 查看详情
算法复习——状压dp
状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····... 查看详情
fzu2188状压dp
G-SimpleStringProblemTimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示： 转移方程：i是当前节点，j是下一步要走的节点 子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情
poj2411mondriaan'sdream（状压dp）
【POJ2411】Mondriaan‘sDream（状压dp）TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情
simplestringproblem（状压dp）(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情
状压dp初探·总结
...最优还是最优，无后还是无后，所以它比较好理解。 状压，顾名思义就是要将一些状压想办法压缩起来（可以压，也可以删）。其中这些状态都满足相似性和数量很多。这样才好压而且压得有意义。常见于一般的方格题，网 查看详情
各种dp分类整理
各种dp分类整理数位dp因为比较重要，单独写一篇见这篇状压dp某篇学术垃圾中指出，我们可以说，所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显，而使用二进制的状压dp压的比较复杂，才叫它“状压dp”所以这里... 查看详情
b.littleponyandharmonychest(状压dp)(代码片段)
B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi≥59时，bi=1b_i=1bi=1更优。所以只需考虑bi≤59b_i\\le59bi≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情
poj2441状压dp
ArrangetheBullsTimeLimit: 4000MS MemoryLimit: 65536KTotalSubmissions: 5289 Accepted: 2033DescriptionFarmerJohnson‘sBullsloveplayingbasketballverymuch.Butnoneofthemw 查看详情
poj2411状压dp经典
Mondriaan‘sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:16771 Accepted:9683DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthed 查看详情
zoj3471mostpowerful（状压dp）
Recently,researchersonMarshavediscoveredNpowerfulatoms.Allofthemaredifferent.Theseatomshavesomeproperties.Whentwooftheseatomscollide,oneofthemdisappearsandalotofpowerisproduced.Researchersknowthewayev 查看详情
jzoj3747(状压dp)
这题是一道状压DP,暂时还不是很懂.#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;constintLENM=1010,N=11,M=1e9+7;chars[N];intn,m,u,ind[200],f[LENM][1<<10],g[N],ans[N],gg[N 查看详情