…は何通りか。 解法 挿入DPで、レートの大きい順に並びを決めていく。 dp(n) := n要素目まで決めたとき、先頭要素が条件に違反しない並び方とすると、dp(n)に対し、(n+1)要素目を先頭か先頭以外に置くかで分岐する。 条件を満たす必要があるのは先頭に置くときだけなので、その際同時にn+1番以降で差がK以下の人の位置を同時に決めてしまうとよい。 int N,K; ll A[1010101]; const ll mo=998244353; ll dp[1010101]; …

…さい方から埋めて行く挿入DPを考える。 dp(i,j,k) := Bのうちi以下の要素だけを抜き出したとき、j個の連続部分列になる。その際、最初と末尾のうちi以下のものがk通り。それ以外の連続部分列の先頭・末尾はiであるような組み合わせの数ここにi+1を挿入する際、2つの連続部分列を連結するように入れる箇所とそうでない箇所があるが、その組み合わせは二項係数で計算できる。 int N; ll A; const ll mo=998244353; ll comb(ll N_, ll…

…は何通りか。 解法 挿入DPで解く。 Aのうち値の小さい順に、最終的な数列に挿入していくことを考える。 ただし、同じ値は同時に挿入する。f(n,k) := Aのうちnまでの値の並び順を決めたとき、A[i]＜A[i+1]となる箇所がk個であるような組み合わせとする。 今、A中にn以下の値がB個、n+1がC個あったとして、それらの挿入位置を考えよう。 f(n,k)の状態を考えると、Aは(B-k)個の単調増加列を連結したものであることがわかる。 ここにn+1をC個追加する場合、単調…

…要素がy個あるとき、挿入DPの要領で、この(x+y)個を並べ、転倒数ごとの組み合わせを数え上げて行こう。 int N,K; int A[101]; ll from[10101]; ll dp[5100][101][101]; const ll mo=998244353; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; map<int,int> M; FOR(i,N) { cin>>x; M[-x]++; } int…

…>1)][(j<<M)|(mask)]+=1; //take if(j<K) A.v[((j+1)<<M)|(1<<(M-1))|(mask>>1)][(j<<M)|(mask)]+=1+__builtin_popcount(mask); } } A=powmat(N,A,(K+1)<<M); ll ret=0; FOR(mask,1<<M) ret+=A.v[(K<<M)|mask][0]; cout<<ret%mo<<endl; } 解法 この挿入DPは思いつかないわ…。

…は何通りか。 解法 挿入DPで解く。 dp(n,a,b) := 1～nの並び順を決めたとき、P[i]＞iとなるiがa個、P[i]＜iとなるiがb個ある並び順 とし、状態遷移を考える。1～nのPermutationのどこかに(n+1)を加えることを考えよう。 末尾に加えると、a,bは変化しない dp(n+1,a,b) += dp(n,a,b) P[i]＞iである場所とswapすると、n+1＞iだがP[i]＜n+1なのでbが1個増える dp(n+1,a,b+1) += a*dp(…

…番の黒頂点… の順で挿入DPの要領で重さを確定させていくことを考えよう。状態を以下のtupleで表すとする。 (n,b,c,s) := n個目までの頂点の重さ順が確定したとき、黒頂点はb個含まれていて、その組み合わせはc通りであり、黒頂点の重みの総和はsである それぞれの頂点を追加するとき、状態は以下の通り遷移する。 白頂点を追加するとき、どこに追加してもよいのでその位置は(n+1)通り。よって(n.b.c.s)→(n+1,b,(n+1)c,(n+2)s)と状態遷移する。 s…

…を昇順にソートして、挿入DPすることを考える。 (0-originで)i番目のニワトリを輪に加えるとき、 既存の輪のどこかに加える場合、その組み合わせはi通り、よって美しさにはi倍寄与する 新規に輪を作る場合、和の美しさの定義より美しさにi倍寄与する こう考えると、多項式f(t) := (A[0]+0)*(A[1]+1)*...*(A[N-1]+N-1)を考えると、S(r)はf(t)のt^rの係数に相当することになる。 ここで、詳細はEditorialを参照して頂くとして、多…

…追加される確率を適宜挿入DPの要領で考えるとH(p)はO(Np)で求めることができる。 Rが10^18なので、pは60程度まで数えればよい。 ll N,L,R; ll mo=1000000007; ll fact[101010]; ll dp[70]; void solve() { int i,j,k,l,r,x,y; string s; fact[0]=1; for(i=1;i<=100100;i++) fact[i]=fact[i-1]*i%mo; cin>>N>>L>>…

…のを求めよ。 解法 挿入DPで解く。 大きい順に値をPに埋めていくことを考えよう。a個空きがある数列にaを埋める場合、左からb個目に数字を埋めると、その左には(b-1)個、右には(a-b)個aより小さい数字が入るので、あとの数字の埋め方はどうであってもP[i]＜P[a]＞P[j]となる(i,a,j)の組は(b-1)*(a-b)個増える。 あとは残り(a-1)個空きがある数列に(a-1)を埋めることを考えればよい。この考察から、以下の状態をDPで更新していけば良いことがわかる。…

…和を求めよ。 解法 挿入DPで解く。 まず長方形を高さで降順にソートする。(1-originで)高い順にx番の長方形に対し、その上にy番(y＜x)の高さまで水が注がれるケースの組み合わせ総数f(x,y)を考える。 そうすると解はである。 このf(x,y)がO(1)で求められれば、総和はO(N^2)で求められる。 O(N^2)では部分点にしかならないが、まずはf(x,y)を考えよう。x番の上にy番までの高さに水が注がれるには、y番未満の長方形は全部x番の左で、y番だけがx番の右…

…、X*Xの盤面を作る挿入DPで処理する。各列にはどこかの行に１個駒がある。 ここで、隣接する列において駒がある行の差が２の場合、不成立な隣接状態があると考える。 X行目まで処理した状態として、dp[X][不成立な列の対の数][(X-3,X-1)行目におかれた列は隣接しているか][(X-2,X)行目におかれた列は隣接しているか]を持ち、(X+1)行目の状態を更新する。X+1行目の置き方によって、以下のように状態が変化する。 (X-3,X-1)行目におかれた列が隣接している場合、…

…])%=mo; } ll ret=0; FOR(i,402) { ll pat=(dp[0][0][i][0]+dp[0][0][i][1])%mo; ll t=0; for(x=i;x<=401;x++) (t+=dp2[x]*combi(n[0]+n[1]+1-i , x-i))%=mo; ret=(ret+pat*t)%mo; } return (int)ret; } } まとめ 挿入DPとか、基本的なアイデアは本番にも思いつけたものの本番中に最後まで到達できなかった。