こういう言い換え系さっと思いつかないな。
https://community.topcoder.com/stat?c=problem_statement&pm=14813
https://community.topcoder.com/stat?c=problem_statement&pm=14795
問題
整数N,Xが与えられる。
1~Nの整数のうち、X個を当確率で選ぶ場合を考える。
選んだX個のうち最小値がSとすると、選んだX個の値のスコアは2^Sとなる。
Div2ではスコアの期待値、Div1では全組み合わせのスコアの総和を求めよ。
解法
Div2はN,Xが小さいので、Sを総当たりし、S以外の要素は[S+1,N]から(X-1)個選ぶ点に着目して2^Sの平均値を求めればよい。
問題はDiv1である。
Xは大きくないがNがとても大きく、総当たりはできない。
真面目に数式変形をすると大変だが、問題文を言い換えると簡単になる。
元ツイートが削除済みなので出所の言及は避けるが、以下のように考えるとよい。
X個の最小値がSのときスコアが2^Sになるという。
これはSより手前の要素について、さらに選ぶ・選ばないを2^(S-1)通り考えると、個々の組み合わせについてスコアが2ずつ得られることになる。
さらに言い換えると、NからX個以上の値を選ぶと、それは選んだうち上からX個目の要素Sにおける手前の選びかた2^(S-1)通りのうちの1個を選んだことと同じである。
よって、求めるのはN個から任意の個数を選ぶ組み合わせ2^Nから、(X個未満を選ぶ組み合わせ*2)を引くことである。
あとはCombinationを求めながら2^Nから値を引いていくだけ。
ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } class ExpectedMinimumPower { public: int findExp(int n, int x) { ll ret=modpow(2,n); ll c=1; for(int i=0;i<x;i++) { ret=(ret+mo-c)%mo; c=c*n--%mo*modpow(i+1)%mo; } return ret*2%mo; } }