[Codefoces 401 D]Roman and Numbers数ビットdp
http://codeforces.com/problemset/problem/401/D
1つの数字nを与えて、nのすべての数字を再配列して、これらの配列数の中でnによって除去することができる方法の数を求めます.
問題解決の考え方:
暴力タイムアウト......
多くの人の書き方はビット圧縮ですが、そうすると2^18*100のスペースが必要で、効率が低く、繰り返し状態数が多く、処理も不便で、この問題は512 Mのスペースを与えています.しかし、空間がさらに2倍小さくなると、前者の方法はどうしようもありません.
デジタルxの出現回数に直接基づいて状態圧縮を行う,デジタルdpにとって比較的良好な状態圧縮方式があることが分かった.例えば333444は,前者の方法で圧縮すると2^6=64の空間が必要となり,出現回数に応じて圧縮すると(3+1)*(3+1)=16の空間しか必要とせず,限界データに対しては平均不等式を利用しても差は少なく(ceil(18/10+1)^10)=59049の空間が必要となり,空間の利用率(本来は2^18=262144)と判重の効率が向上する.
dp方程式はまた、iを符号化するすべてのnに対してjを余す数字に対して、その余剰数に10を加えて次の数字を加えて次の状態の一部を得ることも容易に確立する.結果として,すべての数字が使用される残りが0の場合である(dp[s][n]).
この圧縮の鍵はcodeitとdecode関数にある.
code
1つの数字nを与えて、nのすべての数字を再配列して、これらの配列数の中でnによって除去することができる方法の数を求めます.
問題解決の考え方:
暴力タイムアウト......
多くの人の書き方はビット圧縮ですが、そうすると2^18*100のスペースが必要で、効率が低く、繰り返し状態数が多く、処理も不便で、この問題は512 Mのスペースを与えています.しかし、空間がさらに2倍小さくなると、前者の方法はどうしようもありません.
デジタルxの出現回数に直接基づいて状態圧縮を行う,デジタルdpにとって比較的良好な状態圧縮方式があることが分かった.例えば333444は,前者の方法で圧縮すると2^6=64の空間が必要となり,出現回数に応じて圧縮すると(3+1)*(3+1)=16の空間しか必要とせず,限界データに対しては平均不等式を利用しても差は少なく(ceil(18/10+1)^10)=59049の空間が必要となり,空間の利用率(本来は2^18=262144)と判重の効率が向上する.
dp方程式はまた、iを符号化するすべてのnに対してjを余す数字に対して、その余剰数に10を加えて次の数字を加えて次の状態の一部を得ることも容易に確立する.結果として,すべての数字が使用される残りが0の場合である(dp[s][n]).
この圧縮の鍵はcodeitとdecode関数にある.
code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#define SIZES 40000
using namespace std;
char n[20];
int c[10],d[10],tim[10],m;
long long dp[60000][100];
int len;
int codeit(int *te)
{
int res=0;
for (int i=0;i<10;i++)
res=res*(tim[i]+1)+te[i];
return res;
}
long long decode(int l,int *t)
{
for (int i=9;i>=0;i--){
t[i]=(l%(tim[i]+1));
l/=(tim[i]+1);
}
}
int main()
{
int s;
while(~scanf("%s%I64d",n,&m)){
memset(dp,0,sizeof dp);
len=strlen(n);
memset(tim,0,sizeof(tim));
for (int i=0;i<len;i++)
++tim[n[i]-'0'];
int s=codeit(tim);
// printf("%d
",s);
dp[0][0]=1;
for (int i=0;i<s;i++){
int t[10];
decode(i,t);
for (int j=0;j<10;j++)
if (i+j)
if (tim[j]-t[j]){
t[j]++;
int pt=codeit(t);
for (int k=0;k<m;k++)
dp[pt][(k*10+j)%m]+=dp[i][k];
t[j]--;
}
}
printf("%I64d
",dp[s][0]);
}
}