SRM 509 DIV 1 250P
2011年6月8日晚7点，参加了【SRM 509 DIV 1】
250P：全场75分钟一直在做这题，一开始想位运算枚举肯定会超时，就想其他方案了，可样例总是不能全通过，本想放弃了，但还是坚持了下来，最后6分钟才提交，后又发现组合数组C[][]使用int会溢出应该用long，重新提交一次，最后几十秒发现大数应该先模9再乘积，否则两大数相乘又会溢出，又重新提交一次。
Challenge阶段，没人cha我的，自认为自己的代码肯定是对的，最后居然没有通过System Test，好奇怪，后来反应过来50位的数用long型也不行啊^_^
250P Problem
一个由'1'-'9'组成的字符串，最大长度为50。
For example, if X is 123, then super(X) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177.
求super(X)%9.
250P Solution
来自论坛解释
First notice that a number mod 9 is the sum of the digits in the number mod 9.
Next notice that every digit appears 2^(n-1) times in different subsets, like for 123: {1,2,3}, {1,2}, {1,3}, {2,3}, {1}, {2}, {3}.
The answer is therefore 2^(n-1)*digitSum (mod 9).
public class LuckyRemainder {public int getLuckyRemainder(String X) {int p2 = 1;for (int i = 1; i < X.length(); i++) {p2 = (p2 * 2) % 9;}int res = 0;for (char c : X.toCharArray()) {res += c - '0';}return (res * p2) % 9;}}public class LuckyRemainder {int[] A;int len;long res;long[][] C = new long[51][51];// resubmitpublic int getLuckyRemainder(String X) {len = X.length();A = new int[len];for(int i = 0; i < len; i++)A[i] = X.charAt(i) - '0';C[0][0] = C[1][0] = C[1][1] = 1;for(int i = 2; i < 51; i++) {for(int j = 0; j <= i; j++) {if(j == 0 || j == i)C[i][j] = 1;elseC[i][j] = C[i-1][j] + C[i-1][j-1];}}res = 0;for(int i = 0; i < len; i++) {solve(i);}return (int)res;}void solve(int i) {int k = len-1-i;// i位置右边最多有几位int kk = len-1-k;// i位置左边最多有几位for(int j = k; j >= 0; j--) {for(int jj = kk; jj >= 0; jj--) {long v = A[i];for(int m = 0; m < j; m++)v *= 10;// Failed Reason：if j=49...res = (res+(v%9)*(C[k][j]%9)*(C[kk][jj]%9))%9; // resubmit}}}}