SRM509 Div1 Easy - LuckyRemainder

問題

数字aを文字とみなしたときの全ての(連続とは限らない)subsetの和を9で割った余りを求める

解法

10^k %9 = 1より各桁を独立に考えることができる
全ての桁についてその数(と10^kの積)を含む部分列は2^(n-1)個あるからこれの総和%9を求めればいい

ex) 123なら
1桁目を含むsubset = 1, 12(10+2), 13(10+3), 123(100+23)
2桁目 = 2, 12(2+10), 23(20+3), 123(20+103)
3桁目 = 3, 13(3+10), 23(3+20), 123(3+120)
こんな感じ？

class LuckyRemainder {
	public:
	int getLuckyRemainder(string a) {
		int n = a.size(), res = 0;
		rep(i,n) (res += (ll)(a[i]-'0') * (1ll<<(n-1)) %9) %= 9;
		return res;
	}
};