http://community.topcoder.com/stat?c=problem_statement&pm=14958
とても大きい数Xがある。
この数に対して、以下の操作を行う。
- a＜b＜cを用意し、a桁目をb桁目に、b桁目をc桁目に、c桁目をa桁目に数を移動させる
- このとき、leading-zeroとなるのは不正な操作である
異なるa,b,cについて以上の操作を行うとき、有効な操作によって得られる数の総和をmod 998244353で求めよ。
解法
｜X｜=nとする。
本当はO(n^3)で解けるのだが、以下はO(n^2)で解いてある。
a,cを固定して、bをまとめて計算することにする。
不正な操作はa=0であり、X[c]が'0'の場合はleading-zeroとなってしまうので、この場合はスキップしよう。
それ以外の場合を考える。
m=c-a-1としておく。これはbの組み合わせ数である。
sm[i] := i桁目の数そのもの
P[i] := i桁目の基数の累乗（最下位桁から1, 10, 100, ...）
A[i] := sm[i] * P[i]
これを全て累積和を取れるようにしておく。
getsm, getPP, getA(l, r) := [l,r]での累積和
各計算の簡単な説明を以下に残しておく。
ans += getA(0, a - 1) * m;
m通りの数に対して、[0,a)の部分は同じ数になる。
ans += mint(X[c] - '0') * P[a] * m;
操作によりc桁目の数がa桁目に移動する。
c桁目の数はa桁目にm回現れることになる。
ans += getsm(a + 1, c - 1) * P[c];
操作によりb桁目の数がc桁目に移動する。
b桁目の数としてありえるのが、[a+1,c)の数全てであるため、その総和を取ってc桁目として足しておく。
ans += mint(X[a] - '0') * getPP(a + 1, c - 1);
a桁目の数はb桁目に移動する。
b桁目はa+1桁目、a+2桁目、..., c-1桁目になりうるので、この全パターンを足す。
[a+1,c)桁目の基数の累乗の総和より、計算しておこう。
ans += getA(a + 1, c - 1) * (m - 1);
[a,c)の間のb桁目以外の数はそのまま残る。各桁m-1回同じ位置に現れることになる。
ans += getA(c + 1, n - 1) * m;
m通りの数に対して、[c+1,n)の部分は同じ数になる。
mint P[505], PP[505]; mint getPP(int l, int r) { if (l > r) return 0; mint res = PP[r]; if (l) res -= PP[l - 1]; return res; } mint sm[505]; mint getsm(int l, int r) { if (l > r) return 0; mint res = sm[r]; if (l) res -= sm[l - 1]; return res; } mint A[505]; mint getA(int l, int r) { if (l > r) return 0; mint res = A[r]; if (l) res -= A[l - 1]; return res; } struct DigitRotation { int sumRotations(string X) { int n = X.length(); P[0] = 1; rep(i, 1, n) P[i] = P[i - 1] * 10; reverse(P, P + n); PP[0] = P[0]; rep(i, 1, n) PP[i] = PP[i - 1] + P[i]; sm[0] = X[0] - '0'; rep(i, 1, n) sm[i] = sm[i - 1] + mint(X[i] - '0'); A[0] = mint(X[0] - '0') * P[0]; rep(i, 1, n) A[i] = A[i - 1] + mint(X[i] - '0') * P[i]; mint ans = 0; rep(a, 0, n) rep(c, a + 2, n) { if (a == 0 and X[c] == '0') continue; int m = c - a - 1; ans += getA(0, a - 1) * m; ans += mint(X[c] - '0') * P[a] * m; ans += getsm(a + 1, c - 1) * P[c]; ans += mint(X[a] - '0') * getPP(a + 1, c - 1); ans += getA(a + 1, c - 1) * (m - 1); ans += getA(c + 1, n - 1) * m; } return ans.get(); } };
