kmjp's blog

競技プログラミング参加記です

TopCoder SRM 736 Div1 Easy DigitRotation

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とはいえ、何のひねりもないような問題に感じたが…。