题目描述
在又一次消灭林登·万的战斗中，指挥官moreD缴获了一个神奇的盒子。盒子异常的坚固，以至于完全无法摧毁，唯一打开的方式是通过盒上的密码锁。
经过仔细的调查，研究人员一致认为这个盒子中隐藏了林登·万和他的弟弟林登·图的秘密。然而moreD使用了许多办法，都没能打开这个盒子。最后只好将这个盒子封存在了仓库的底层。
事情并没有结束。moreD之所以没能打开这个盒子，是因为老牌的调查员/邪教徒LCJ隐瞒了它的调查结果。LCJ经过不懈的努力，得出了结论。即：给你一个长度不超过17的由0~9组成的无前导0的字符串S，S中的数字排列组成的无前导零的能被17整除的整数中字典序第K小的那个数就是密码。
尽管解开了密码，然而处于对未知的恐惧，LCJ最终并没有打开盒子。然而另一个资历较浅的调查员/邪教徒，你，YDMan不知通过什么办法得知了上述信息，并得到了S和K。现在你决定要解开这个密码，来取得“终极的智慧”。 输入
一行，一个由0~9组成的字符串S和一个不超过17！的正整数K。 输出
一行，即密码。 如果第K个不存在，输出“-1” 样例输入
2242223 2
样例输出
2242232
提示
【数据规模】 对于40%的数据，字符串S长度<=12,K<=2*10^6。 对于100%的数据，字符串S长度<=17,K<=17!。 来源
数位_状压DP 题解
f[i][k]表示选用i状态的数字，后续数字组合能mod 17为k的方案数，转移见代码，计算答案时判断是否有足够多的解即可。 代码 #include #include #include #include #include long long f[1<<17][17],a[18],fac[18],J[18],c[18]; long long K; using namespace std; int main() { char ch[20]; scanf("%s",ch); scanf("%lld",&K); int n=strlen(ch); for (int i=1;i<=n;i++) a[i]=ch[i-1]-'0'; sort(a+1,a+n+1); int N=(1<1; f[N][0]=1; for (int i=N;i>0;i--) { int p=1; for (int j=1;j<=n;j++) if ((i&(1<<(j-1)))==0) p*=10,p%=17; for (int j=1;j<=n;j++) if (i&(1<<(j-1))) { for (int k=0;k<=16;k++) { f[i^(1<<(j-1))][(k+a[j]*p)%17]+=f[i][k]; } } } J[0]=1; for (int i=1;i<=17;i++) J[i]=J[i-1]*i; for (int i=N;i>0;i--) { for (int j=0;j<=9;j++) c[j]=0; for (int j=1;j<=n;j++) if ((i&1<<(j-1))==0) c[a[j]]++; for (int j=0;j<=9;j++) for (int k=0;k<=16;k++) f[i][k]/=J[c[j]]; } int s=0,p=0; bool flag=0; fac[0]=1; for (int i=1;i<=n;i++) fac[i]=(fac[i-1]*10)%17; for (int i=1;i<=n;i++) { int pre=-1; for (int j=1;j<=n;j++) if ((s&(1<<(j-1)))==0) { if (a[j]==pre) continue; pre=a[j]; int k=(17-(p+a[j]*fac[n-i])%17)%17; if (i==1&&a[j]==0) continue; if (f[s|1<<(j-1)][k]>=K) { s|=1<<(j-1); p+=a[j]*fac[n-i]; p%=17; cout<1; break; } else K-=f[s|1<<(j-1)][k]; } if (!flag){puts("-1");return 0;} } for (int i=1;i<=n;i++) if ((s&1<<(i-1))==0) cout<return 0; }