B - Kleene Inversion
300点にしては難しくないですか(令和ABCだと400っぽい…?)
整数列Aが与えられるので、AをK回繰り返した整数列の転倒数を求めて下さい。
考察
整数列Aの長さはたかだか2000なので、Aについては$ O(N^2)を書いても通りそう…
{5,2,4,1}が4つ横につながった例を考えてみます。
https://gyazo.com/698013e984c335059137465d231996e3
ここで、転倒は「俺より右にあるのに俺よりも小さいやん!!」のこと、と言いかえることができます。
たとえば左から3番目の4からみた転倒の個数を考えてみると、
https://gyazo.com/d0664c0268f19b5b28d03ffc866f2e93
右側に自分よりも小さい数が7個あることが分かります。
ここでよ〜く考えてみると、整数列Bは整数列Aを繰り返したものなので、右に同じようなパターン{2,1}が3回連続で来ることが分かります。
https://gyazo.com/d61f53204f5aa2ab63e49f68628dfafc
例えば先程の4を基準に考えた時、右側にある自分よりも小さい物の個数は1+(2*3)=7と求めることができます。
その他の4でも同じことをしてみます。
https://gyazo.com/7c349677596fe08a5e1e04f01b7fa269
https://gyazo.com/3accf26337dc0fb26fb9987253e2f852
https://gyazo.com/b8f394b497b681b1d79c26e450fcb18b
4だけで転倒の総和を考える時、
1+2+2+2
1+2+2
1+2
1
の4つを足したら良いことが分かります。上の4つを言い換えると
1+6
1+4
1+2
1+0
という風になります。
左側の縦は1*4=4で、右側の縦は等差数列の和の公式$ \frac{(初項+最後の項) * 項数}{2}から$ \frac{(0+6)*4}{2} = 12なので、
合わせると4+12で16だ!ということになります。
このアイデアを使えば、一番左側の整数列Aについて考えるだけで、その他の部分も含めた全体の転倒数を計算することができます。
実装
整数列Aにおいて、自分よりも右にあるが自分よりも小さい数の個数…migi
整数列A全体で、自分よりも小さい数の個数…zentai
の2つの個数をa[i]について計算して、
ans += migi * k
ans += zentai * (k-1) * k / 2
※kは「何回列が連続するか」の回数
※「最後の項」はcount * (k-1) で求められます、初項は0です
のようにすればいいです。基本的にMODうんぬんが絡むとき/2をするのは危険(確か逆元を求めたほうが良い)なんですが、
今回は(k-1)*(k)が偶数になる(必ずどちらかが偶数になるので)ので、2で割っています。
今回はMODをとる系問題なので、
ans += migi * k % MOD;
ans %= MOD;
ans += (k - 1) * k / 2 % MOD * zentai % MOD;
ans %= MOD;
このようにどんどんMODをとりましょう。そうしないとWAを連発してレートが落ちる原因になります(僕は落ちました)。
自分の提出
code:mysubmit.cpp
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
// ====================================================================
int main() {
ll n, k;
cin >> n >> k;
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> vi; ll ans = 0;
for (int i = 0; i < n; i++) {
ll migi = 0, zentai = 0;
for (int j = i; j < n; j++)
for (int j = 0; j < n; j++)
ans += migi * k % MOD;
ans %= MOD;
ans += (k - 1) * k / 2 % MOD * zentai % MOD;
ans %= MOD;
}
cout << ans << endl;
}