ARC096 E : Everything on It(900)
作成日：2018.09.16
最終更新日：2018.09.16
問題概要
$N$種類のトッピングからいくつか選んで乗せられるラーメンをいくつか注文する。
トッピングの組み合わせが全く同じラーメンがなく、すべてのトッピングが$2$杯以上のラーメンに乗っているような注文の仕方の数を$M$で割った余りを求めよ。
制約
$2 \leq N \leq 3000$
$10^8 \leq M \leq 10^9 + 9$ , $M$は素数
考え方
すべてのトッピングが$2$杯以上のラーメンに乗っているかを考えるのは難しいので、$1$杯以下のラーメンにのみ乗っているトッピングがないと考えることにする。
これは$1$杯以下のラーメンに乗っているトッピングの数$x$に注目して包除原理を用いれば数え上げられそうである。
$N$個のトッピングから$x$個選ぶのは$_NC_x$通りあるから、答えは$\sum_{0 \leq x \leq N} [(-1)^x \: _NC_x f_x]$の形で表せる。
ここで$f_x$は、ある$x$個のトッピングが$1$杯以下のラーメンに乗っているような注文の仕方の数であり、後はこれを求められれば良い。
選ばれた$x$個のトッピングとそれ以外の$(N-x)$個のトッピングでわけて考える。
後者には制約がないので、ラーメン$1$杯あたり$2^{N-x}$通りの可能性がある。
特に前者を含まないラーメンは自由に選べるから、選び方は$2^{2^{N-x}}$通り存在する。
後は、選ばれたトッピングが乗っているラーメンの選び方が何通りあるかが分かれば良い。
先の考察から、選ばれたトッピングを何杯のラーメンに振り分けるかは気にする必要があることが分かる。
つまり、$y$杯のラーメンのうちのいずれかに乗せるものとトッピングせずに残すものとに$x$個のトッピングを振り分ける方法$g_{x,y}$を求める必要がある。
またそうすれば$f_x = \sum_{0 \leq y \leq x} [2^{(N-x)y}g_{x,y}]$となるので、答えを求められる。
$g_{x,y}$の求め方としては$x$を昇順に見ていくか$y$を昇順に見ていくかの2つが考えられるので、以下ではこれらを検討する。
$x$を昇順に見ていくことを考える。
$x$が$1$増えるのは、選ばれたトッピングが$1$つ増えることに対応する。
増えたトッピングについては、今あるラーメンに乗せるか、新たな別のラーメンに乗せるか、どのラーメンにも乗せないかのいずれかである。
よって$g_{x+1,y} = yg_{x,y} + g_{x,y-1} + g_{x,y}$$= (y+1)g_{x,y} + g_{x,y-1}$となる。
これはDPにより$O(N^2)$で求められる。
$g_{x,y}$を用いれば$f_x$も$O(N^2)$で求められるから、この方針で解くことができる。
ちなみに$y$を昇順に見ていくとすると、ラーメンにいくつのトッピングを乗せるかが遷移となるDPを行うことになる。
しかしこれは状態$O(N^2)$,遷移$O(N)$のDPになってしまうので間に合わない。
ソースコード
マクロ等はこちら
const int MC = 3003;
LL fct[MC+1]; //fct[i] = i!
LL invfct[MC+1]; //invfct[i] = 1/i!
int N;
LL M;
LL dp[MC][MC];
void build(){
fct[0] = fct[1] = 1;
repp(i,2,MC+1){
fct[i] = fct[i-1] * i % M;
}
LL x = fct[MC];
invfct[MC] = 1;
for(int i = M - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (invfct[MC] *= x) %= M;
(x *= x) %= M;
}
repm(i,MC,0){
invfct[i-1] = invfct[i] * i % M;
}
}
int main(){
cin >> N >> M;
build();
dp[0][0] = 1;
repp(i,1,N+1){
dp[i][0] = 1;
repp(j,1,N+1) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (j+1)) % M;
}
LL ans = 0;
LL p = 2 , q = 1;
repm(i,N,-1){
LL c = (i&1?M-1:1) * p % M * fct[N] % M * invfct[i] % M * invfct[N-i] % M;
repp(j,0,N+1){
(ans += dp[i][j] * c) %= M;
c = c * q % M;
}
p = p * p % M;
q = q * 2 % M;
}
cout << ans << endl;
return 0;
}解法まとめ
$dp_{0,0} = 1$,$dp_{i,j} = (j+1)dp_{i-1,j} + dp_{i-1,j-1}$($i \geq 1$,$0 \leq j \leq i$,$dp_{i,-1}$は$0$とする)の漸化式を元にしたDPを行う。(27-31行)
答えは$\sum_{0 \leq i \leq N} [(-1)^i \: _NC_i \sum_{0 \leq j \leq i} [2^{(N-i)j} dp_{i,j}]]$である。(32-43行)