AtCoder ARC #096 : E - Everything on It

ここらへんからサボってますね。
https://beta.atcoder.jp/contests/arc096/tasks/arc096_c

問題

N種類のトッピングがあるラーメンを考えると、量を無視してトッピングの組み合わせは2^N通りある。
そのうちいくつかを選ぶとき、

• 同じ組み合わせの物は２つない
• 各トッピングは２回以上登場する

ような選び方は何通りか。

解法

way(i) := i個のトッピングが1回以下しか登場しないトッピングの組み合わせの組み合わせ
とすると、包除原理より解Aは１回以下しか登場しないトッピングの数に応じて正負を切り替えつつ組み合わせを足しこみである。
あとはこのway(i)を求めよう。

way2(i,j) := i個のトッピングについて、計j杯のラーメンで全トッピングが1回ずつ登場し、かつトッピングのないラーメンの存在しないトッピングの組み合わせ数
とすると、分割数と似た処理で要領でway2(i,j) = way2(i-1,j-1) + way2(i-1,j)*jで求まる。
あとは残りの(N-i)個のトッピングについて、最初のj杯への割り振り方と、最初のi個のトッピングとは関係ないラーメンへの割り振り方でway(i) += way2(i,j) * 2^*1のように足しこんでいけばよい。

ll N,mo;
ll ways2[3030][3030],ways[3030];
static const int N_=3020;
static ll C_[N_][N_];
ll p2[3030][3030];
ll p22[3030];

ll modpow(ll a, ll n = mo-2, ll m=mo) {
	ll r=1;a%=m;
	while(n) r=r*((n%2)?a:1)%m,a=a*a%m,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	
	FOR(i,N_) C_[i][0]=C_[i][i]=1;
	for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	
	FOR(x,3020) p2[0][x]=p2[x][0]=1;
	FOR(x,3020) {
		p2[x+1][1]=p2[x][1]*2%mo;
		for(y=2;y<=3020;y++) p2[x][y]=p2[x][y-1]*p2[x][1]%mo;
	}
	
	ways2[0][1]=1;
	
	ll ret=modpow(2,modpow(2,N,mo-1));
	for(i=1;i<=N;i++) {
		ll hoge=modpow(2,modpow(2,N-i,mo-1));
		for(j=1;j<=i+1;j++) {
			(ways2[i][j]=ways2[i-1][j-1]+ways2[i-1][j]*j)%=mo;
			(ways[i]+=ways2[i][j]*p2[N-i][j-1]%mo*hoge)%=mo;
		}
		if(i%2) ret-=C_[N][i]*ways[i]%mo;
		else ret+=C_[N][i]*ways[i]%mo;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

この回は配点の割に難しかったね。

*1:N-i)*j) * 2^(2^(N-i