codeforces 401D

어제는 못했는데 오늘은 선배에게 가르침을 청했다.나는 이런 dp의 사상이 매우 좋다고 생각한다. 이런 번거로운 문제에 직면하면 넉 냥 천 근의 기이한 효과가 있다는 것을 깨달았다.
먼저 dp[1<<18][100]의 수조를 구축하는데 이 수조는 의미가 있다.다음과 같이 설명합니다.
1차원: 하나의 숫자, 예를 들어 123123453에 대해 각각 0과 1로 사용했는지 여부를 표시할 수 있다. 그러면 2진법으로 표현할 수 있고 제목의 18자리 길이에 해당하는 크기의 수조를 구축할 수 있다.
2차원: 이 상태의 나머지를 나타낸다.
cnt[i]로 i의 출현 횟수를 기록합니다.
편리하고 같은 숫자가 중복되지 않도록 우리는 각 사람을 순서대로 배열한 상태로 생각한다. 예를 들어 1, 2, 3, 3, 3, 4, 5는 a[i]로 i의 시작 위치를 표시하기 때문에 a[i]개부터 a[i+1]까지 - 1개는 모두 i이다.
다음은 dp의 과정입니다. 첫 번째는 0이 될 수 없기 때문에 특수 처리:
for(int i=1;i<10;i++)     {         if(cnt[i])dp[1<1~9만 봐도 지금은 한 명의 상황.
다음은 2진법 구성에서 뒤로 미루겠습니다.
for(int i=1;i<(1<마지막 답은 dp[(1#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; long long dp[1<<18][111]; int cnt[11]; int a[11]; string s; int m; int main() { cin>>s>>m; int l=s.length(); memset(cnt,0,sizeof(cnt)); memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for(int i=0;i<l;i++) { cnt[s[i]-'0']++; } for(int i=1;i<11;i++)a[i]=a[i-1]+cnt[i-1]; for(int i=1;i<10;i++) { if(cnt[i])dp[1<<a[i]][i%m]=1; } for(int i=1;i<(1<<l);i++) { for(int j=0;j<m;j++) { if(dp[i][j]) { for(int k=0;k<=9;k++) { for(int p=a[k];p<a[k+1];p++) { if(i&(1<<p))continue; dp[i+(1<<p)][(j*10+k)%m]+=dp[i][j]; break; } } } } } cout<<dp[(1<<l)-1][0]<<endl; return 0; }