PKU 3761 - Bubble Sort

問題概要

n, kが入力される。
n個の要素がある数列をバブルソートでソートされることを考える。
このとき、数列が並び終わるまでに、バブルソートの一重ループ目を実行した回数がkであるとする。
このようになる数列の初期配置は、何パターンあるか求めよ。

解法

ごめんなさい。
法則性ありそうだったけど、自力で導きだせなかったので、OEIS突っ込みました。
http://oeis.org/A056151

階上は、先に計算しておく。
累乗は、繰り返し二乗法で。
入力は、scanfで。

プログラム

/*
0回でソートできるのならば、各数字はソートされた状態でなければならない。
1 2 3 4

1回でソートできるのならば、各数字は「本来あるべき位置の1つ右」以下に位置すればおk。
さらに、最低でも1つの数字が本来あるべき位置でない位置になければならない。

2 1 3 4 <- 1は、本来あるべき位置より1つ右に位置するのでOK
4 1 2 3 <- 4は、本来あるべき位置より左側に位置するのでOK
2 3 1 4 <- 1は、本来あるべき位置より2つ右に位置しているのでNG
1 2 3 4 <- ソートされちゃってるのでNG

2回でソートできるのであれば、各数字は「本来あるべき位置の2つ右」以下に位置すればOK。
さらに、最低１つの要素は、本来あるべき位置より2つ右の位置になければならない。

2 3 1 <- 1は、本来あるべき位置より2つ右にあるからOK
3 2 1 <- 1は、本来あるべき位置より2つ右にあるからOK
1 2 3 <- sortされちゃってるからNG
3 1 2 <- 条件満たしてないのでNG
 */
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long ll;

#define MOD 20100713LL

ll fact[1000002];

ll modPow(ll x, ll n){
  if(n == 0) return 1LL;
  ll res = modPow(x * x % MOD, n / 2LL);
  if(n & 1LL) res = res * x % MOD;
  return res;
}

int main(){
  fact[0] = fact[1] = 1;
  for(ll i = 2; i <= 1000000; i++){
    fact[i] = fact[i - 1] * i;
    fact[i] %= MOD;
  }

  int T;
  ll n, k;

  scanf("%d", &T);

  while(T--){
    scanf("%lld%lld", &n, &k);

    ll cal = fact[k] * modPow(k + 1, n - k) % MOD;
    cal -= (fact[k - 1] * modPow(k, n - k + 1)) % MOD;
    cal = (cal + MOD) % MOD;

    printf("%lld\n", cal);
  }
}