TopCoder SRM 597 Div2 Hard LittleElephantAndSubset

これも発想を変えると一気に簡単になる。
http://community.topcoder.com/stat?c=problem_statement&pm=12761

問題

自然数Nが与えられる。
1～Nの数値からなるN要素の集合があったとき、そこから空でない部分集合を選んで、その部分集合に含まれる数値の各桁において、0～9の数が高々1回しか使われないようにしたい。
そのような部分集合の選び方の数を答えよ。

解法

最初「N以下で同じ数字を２回使わないようなものを選んで…」といったDPを考えていたがややこしくなってしまった。

部分集合に使われる数字は、各桁で同じ数字を２回以上使わないので、高々10!個程度しか無いことに気づく。(実際は0で始まる数は除外したりするのでもう少し異なる)

よって、先にN以下で同じ数字を２回以上使わないものをDFSで列挙しておく。
また、列挙した数はいちいち覚えておく必要はなく、0-9の各数字を使ったか使ってないかをbitmapで表現し、各bitmapに対応するN以下の数値の数を数えておけばよい。
(最初列挙してsetに入れたらメモリからあふれた)

ここまでくれば後は簡単。
残り利用できる数字をbitmap表記したものに対し、そのbitmapに対応する数値の数がわかっている。
あとは0～1023の各bitmaskを複数のbitmaskのorであらわす方法を列挙し、各bitmaskに対応した数値の数を掛け合わせていけばよい。

空集合は不可なので1を引くのを忘れずに。

ll mo=1000000007;
int mask[100000];
int SZ[1030];
ll dp[1030];

class LittleElephantAndSubset {
	public:
	int N;
	
	ll dpdp(int mask) {
		int i,m;
		if(mask==0) return 1;
		if(dp[mask]>=0) return dp[mask];
		dp[mask]=0;
		m=1;
		while(m*2<=mask) m*=2;
		FOR(i,m) {
			if((mask & (m+i)) !=(m+i)) continue;
			if(SZ[m+i]==0) continue;
			dp[mask]+=SZ[m+i]*dpdp(mask ^ (m+i));
			dp[mask]%=mo;
		}
		return dp[mask];
	}
	
	void dfs(ll val,int mask) {
		int i;
		if(val>N) return;
		SZ[mask]++;
		FOR(i,10) if((mask & (1<<i))==0) dfs(val*10+i,mask | (1<<i));
	}
	
	int getNumber(int N) {
		int i,r=0;
		this->N=N;
		ZERO(SZ);
		
		for(i=1;i<=9;i++) dfs(i,1<<i);
		MINUS(dp);
		ll ret=mo-1;
		FOR(i,1024) ret+=dpdp(i);
		return (int)(ret%mo);
	}
};

まとめ

先にN以下の数値を列挙してしまえばよい、ということに気づけて良かった。
でも１発目はsetに数値を全部格納していたので、本番参加していたら落としてたな…。