Codeforces 551 Div2 F. Serval and Bonus Problem
http://codeforces.com/contest/1153/problem/F
問題
解法
区間のうち、左端の点をl,右端の点をrと呼ぶ
ここでl,rをN個ずつ決めた時、どのl,rを結んでも、領域の重なり方は同じになる。
よって、具体的な区間は考えず、LRとして使う頂点だけ考えればいい。
また、N個ずつLとRを置いた時、全体は2*N+1個に分割されますが、期待値の計算であるためそれらは等分されてると考えて良いです。
よって全てのL,Rの取り方について、2 * N+1個の区間のうち、 K個以上の区間に被覆されてるものの数を数え上げればよさそうです
res := [i,i+1]のうちK個以上の区間に被覆されるものの場合の数
dp[i][j] := 前からi個を、対応の無いLがj個あるように埋める場合の数 とします
iにLを置く場合 dp[i+1][j+1] += dp[i][j] ;
iにRを置く場合 dp[i+1][j-1] +=dp[i][j] * j; (jはLとして選べる相手の数)
とすればいいです。
j >=K の時 [i,i+1]はk個以上の区間に被覆されるので
res += dp[i][j] * rdp[i][j] (rdpはdp[i][j]以降で、対応がつくようなi以降のLRの決め方(rdpを掛けないとゴールしない))
大体終わりです
一つ当たりの区間の長さは1/(2*N+1)なので res /= 2*N+1;
N個の区間が現れる順番を入れ替えられるので res *= N!
上で考えやすさのため区間の左右a,bをL,Rと置きましたが実際はa,bを入れ替えることが出来るためres *= 2^N
全事象で割る res /= (2*N)!
長さがL倍 res *= L;
#include <bits/stdc++.h>
#define int long long
using ll=long long;
using namespace std;
//マクロ 繰り返し
#define _overloadrep(_1, _2, _3, _4, name, ...) name
# define _rep(i, n) for(int i = 0,_lim=n; i < _lim ; i++)
#define repi(i, m, n) for(int i = m,_lim=n; i < _lim ; i++)
#define repadd(i, m, n, ad) for(int i = m,_lim=n; i < _lim ; i+= ad)
#define rep(...) _overloadrep(__VA_ARGS__,repadd,repi,_rep,)(__VA_ARGS__)
#define _rer(i, n) for(int i = n; i >= 0 ; i--)
#define reri(i, m, n) for(int i = m,_lim=n; i >= _lim ; i--)
#define rerdec(i, m, n, dec) for(int i = m,_lim=n; i >= _lim ; i-=dec)
#define rer(...) _overloadrep(__VA_ARGS__,rerdec,reri,_rer,)(__VA_ARGS__)
#define fora(a, b) for(auto&& a : b)
//マクロ省略系 コンテナ
using vi = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vc = vector<char>;
#define vec vector
#define o_vvt(o1, o2, o3, o4, name, ...) name
#define vvt0(t) vec<vec<t>>
#define vvt1(t, a) vec<vec<t>>a
#define vvt2(t, a, b) vec<vec<t>>a(b)
#define vvt3(t, a, b, c) vec<vec<t>> a(b,vec<t>(c))
#define vvt4(t, a, b, c, d) vec<vec<t>> a(b,vec<t>(c,d))
#define vvi(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(ll,__VA_ARGS__)
#define vvb(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(bool,__VA_ARGS__)
#define vvs(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(string,__VA_ARGS__)
#define vvd(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(double,__VA_ARGS__)
#define vvc(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(char,__VA_ARGS__)
#define vvp(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(P,__VA_ARGS__)
#define vvt(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(T,__VA_ARGS__)
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }
#define vni(name, ...) auto name = make_v<ll>(__VA_ARGS__)
#define vnb(name, ...) auto name = make_v<bool>(__VA_ARGS__)
#define vns(name, ...) auto name = make_v<string>(__VA_ARGS__)
#define vnd(name, ...) auto name = make_v<double>(__VA_ARGS__)
#define vnc(name, ...) auto name = make_v<char>(__VA_ARGS__)
//@formatter:off
//constexpr
int MOD = 1000000007;
/*@formatter:on*/
struct mint {
int x;
mint() : x(0) {}
mint(int a) {
x = a % MOD;
if (x < 0) x += MOD;
}
mint &operator+=(mint that) {
x = (x + that.x) % MOD;
return *this;
}
mint &operator-=(mint that) {
x = (x + MOD - that.x) % MOD;
return *this;
}
mint &operator*=(mint that) {
x = (int) x * that.x % MOD;
return *this;
}
mint &operator/=(mint that) { return *this *= that.inverse(); }
mint operator-() { return mint(-this->x); }
friend ostream &operator<<(ostream &out, mint m) { return out << m.x; }
mint inverse() {
int a = x, b = MOD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
u -= t * v;
swap(a, b);
swap(u, v);
}
return mint(u);
}
operator int() const { return x; }
template<class T> mint &operator+=(T that) { return operator+=((mint) that); }
template<class T> mint &operator-=(T that) { return operator-=((mint) that); }
template<class T> mint &operator*=(T that) { return operator*=((mint) that); }
template<class T> mint &operator/=(T that) { return operator/=((mint) that); }
mint operator+(mint that) { return mint(*this) += that; }
mint operator-(mint that) { return mint(*this) -= that; }
mint operator*(mint that) { return mint(*this) *= that; }
mint operator/(mint that) { return mint(*this) /= that; }
template<class T> mint operator+(T that) { return mint(*this) += (mint) that; }
template<class T> mint operator-(T that) { return mint(*this) -= (mint) that; }
template<class T> mint operator*(T that) { return mint(*this) *= (mint) that; }
template<class T> mint operator/(T that) { return mint(*this) /= (mint) that; }
bool operator==(mint that) const { return x == that.x; }
bool operator==(signed that) const { return x == that; }
bool operator!=(mint that) const { return x != that.x; }
bool operator<(mint that) const { return x < that.x; }
bool operator<=(mint that) const { return x <= that.x; }
bool operator>(mint that) const { return x > that.x; }
bool operator>=(mint that) const { return x >= that.x; }
};
/*@formatter:off*/
istream &operator>>(istream &i, mint &a) { i >> a.x; return i;}
typedef vector<mint> vm;
vector<mint> fac, finv;
int mint_len = 1400000; //既に変更されていたら変えない
void setmod(int mod = 1e9 + 7) { /*mint_len>=modの時fac[mint_len]が0になり、下の1/fac[mint_len]で0徐算になってしまう*/ if (mint_len >= mod - 1)mint_len = mod - 1; MOD = mod; fac = vector<mint>(mint_len + 1); finv = vector<mint>(mint_len + 1); fac[0] = 1; rep(i, 1, mint_len + 1) { fac[i] = fac[i - 1] * i; } finv[mint_len] = (mint) 1 / fac[mint_len]; rer(i, mint_len, 1) { finv[i - 1] = finv[i] * i; }}
mint com(int a, int b) { if (a < 0) return 0; if (b < 0 || b > a) return 0; return fac[a] * finv[a - b] * finv[b];}
mint hom(int a, int b) { return com(a + b - 1, b);}
template<typename T, typename U> mint mpow(const T a, const U b) { assert(b >= 0); int x = a, res = 1; U p = b; while (p > 0) { if (p & 1) (res *= x) %= MOD; (x *= x) %= MOD; p >>= 1; } return res;}template<typename T> inline mint mpow(const T a, const mint b) { int x = a, res = 1; int p = b.x; while (p > 0) { if (p & 1) (res *= x) %= MOD; (x *= x) %= MOD; p >>= 1; } return res;}
using PM = pair<mint, mint>;
using vm = vector<mint>;
#define vvm(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(mint,__VA_ARGS__)
#define vnm(name, ...) auto name = make_v<mint>(__VA_ARGS__)
string yuri(const mint &a) { stringstream st; rep(i, 300) {rep(j, 300) {if ((mint) i / j == a) {st << i << " / " << j;return st.str();}}} rep(i, 1000) {rep(j, 1000) {if ((mint) i / j == a) {st << i << " / " << j;return st.str();}}} return st.str();}
#define smod setmod
//setmodを呼ぶ @formatter:on
int N, K, H, W;
vi A, B, C;
signed main() {
int N,K,L;
cin>>N>>K>>L;
vnm(dp, 2 * N + 1, N + 1);
dp[0][0] = 1;
setmod(998244353);
mint res = 0;
//no toki usirono umecata
vvm (rdp, 2 * N + 1, N + 1);
rdp[2 * N][0] = 1;
//rer(i,s,t) := iをsからtまで
rer(i, 2 * N - 1, 1) {
//rer(i,s) := iをsから0まで
rer(r, N) {
//(
if (r < N)rdp[i][r] += rdp[i + 1][r + 1];
//)
if (r)rdp[i][r] += rdp[i + 1][r - 1] * r;// * r is number of aite
}
}
rep(i, N * 2) {
rep(r, N + 1) {
if (dp[i][r] == 0)continue;
//[i,i+1] is dup k
if (r >= K) {
res += dp[i][r] * rdp[i][r];//* i ikou no okicata
}
//)
if (r) {
dp[i + 1][r - 1] += dp[i][r] * r;//erabu
}
if (r < N)dp[i + 1][r + 1] += dp[i][r];
}
}
res /= 2 * N + 1; // 1kukan is 1/(2*N+1) len
res *= fac[N]; // junjo
res *= mpow(2, N); // sayuu narabicae
// res /= (2*N)!
res *= finv[2 * N]; // zenzishou
res *= L;
cout << res << endl;
return 0;
}
