Mediumに手間取ってレート減でした。
http://community.topcoder.com/stat?c=problem_statement&pm=14958
問題
N桁の整数が与えられる。
このうち3つの位置を選択し、その数字をローテートしたものを考える。
全選択のうち、ローテート後Leading zeroが含まれないものの総和を、mod 998244353で求めよ。
解法
3つの位置を総当たりしよう。
入力の整数から3つの桁の数字だけ入れ替えた数字におけるmod 998244353の値は、入力の整数値との差分を考えればO(1)で求められる。
よって位置を総当たりしてもO(N^3)で間に合う。
ll mo=998244353; ll p10[551]; class DigitRotation { public: int sumRotations(string X) { int N=X.size(); int i; p10[0]=1; FOR(i,501) p10[i+1]=p10[i]*10%mo; ll tot=0; FOR(i,N) { X[i]-='0'; tot=(tot*10+X[i])%mo; } int a,b,c; ll ret=0; FOR(c,N) FOR(b,c) { FOR(a,b) { if(a==0 && X[c]==0) continue; ret += tot; ret -= X[a]*p10[N-1-a]; ret -= X[b]*p10[N-1-b]; ret -= X[c]*p10[N-1-c]; ret += X[c]*p10[N-1-a]; ret += X[a]*p10[N-1-b]; ret += X[b]*p10[N-1-c]; } ret=(ret%mo+mo)%mo; } return ret; } }
まとめ
Easyとはいえ、何のひねりもないような問題に感じたが…。