手順3の「できた数が2桁なら十の位と一の位を足す」という操作は9での剰余を求めることとほぼ等しいことに注意すれば、途中で行われる操作が加算のみであることから、これは最後にまとめてすれば良い。
よって(Σs[i]*(寄与度))%9を求めることになる。
操作手順をぐっと睨めばこれはパスカルの三角形の逆の操作をしていることが分かるので、寄与度はC(strlen(s)-1,i)と分かる（C(n,r)は二項係数）
（操作によってできる列を下から上に積み上げていけば、ある数を作るためにはその左下と右下の数が寄与していることが分かる）
ということでC(n,r)%9を求める問題に帰着された。
二項係数の計算は漸化式でする。
modが素数でないので除算が簡単にはできないが、次のように考える。
・すべての整数aは、3と互いに素な整数xと非負整数nによりa=x*3^nの形で表す事ができる
・b=y*3^mがa=x*3^nを整除する時、当然x/yもまた整数となり、ここでyは3と互いに素なのでy'*y≡1 mod9 となるようなy'が存在し、a/b≡x/y*3^(n-m)≡xy'*3^(n-m) mod 9
要するに3の因数の分だけよければ他はいつもどおり計算できますよ、ということ。
また、答えが0になるのは、元の数列に登場する全ての数が0のときに限る事に注意する
char s[100010]; n,i,t,ans,c,c3; //n*inv9[n]≡1 mod 9 inv9[]={0,1,5,0,7,2,0,4,8}; //n=g3(n)*3^f3(n) f3(n){int i=0;for(;n&&n%3==0;n/=3)i++;return i;} g3(n){for(;n&&n%3==0;n/=3);return n;} main(){ for(gets(s);gets(s);){ n=strlen(s)-1; t=ans=c3=0,c=1; //tは元の数列に登場した数の合計。これが0か否かで答えが0か9か判別する //C(n,i)≡c*3^c3 mod 9 for(i=0;i<=n;i++){ t+=s[i]-48; ans+=c*(c3?c3==1?3:0:1)*(s[i]-48)%9; c3+=f3(n-i)-f3(i+1); c=c*g3(n-i)*inv9[g3(i+1)%9]%9; } printf("%d\n",ans%9?:t?9:0); } return 0; }
これを縮める
fとgの計算は次のようにまとめることができる
//fとgの計算 f3(n){int i=0;for(;n&&n%3==0;n/=3)i++;return i;} g3(n){for(;n&&n%3==0;n/=3);return n;} ↓ f3(n){return!n|n%3?x=n,0:f3(n/3)+1;} //新たにグローバル変数xを用意し、x=g3(n)となるようにした
その他、細かい点をいろいろ工夫して
char s[1<<17]; i,t,a,c,p,x; v[]={0,1,5,0,7,2,0,4,8}; f(n){return!n|n%3?x=n,0:f(n/3)+1;} main(n){ for(gets(s);gets(s);t=a=p=i=!printf("%d\n",a%9?:t?9:0)){ for(n=strlen(s)-1,c=1;s[i];p-=f(++i),c=c*v[x%9]%9){ t+=s[i]-=48; a+=c*(p-1?!p:3)*s[i]%9; p+=f(n--);c*=x; } } }
252B
2016/10/23追記
オイラーの定理から逆元はx^(φ(n)-1)で計算できた…
char s[1<<17]; i,t,a,c,p,x; f(n){return!n|n%3?x=n%9,0:f(n/3)+1;} main(n){ for(gets(s);gets(s);t=a=p=i=!printf("%d\n",a%9?:t?9:0)){ for(n=strlen(s)-1,c=1;s[i];p-=f(++i),c=c*x*x*x*x*x%9){ t+=s[i]-=48; a+=c*(p-1?!p:3)*s[i]%9; p+=f(n--);c*=x; } } }
233B
2016/11/03追記
for文に{}を使ってるとか馬鹿なの？死ぬの？
char s[1<<17]; i,t,a,c,p,x; f(n){return!n|n%3?x=n%9,0:f(n/3)+1;} main(n){ for(gets(s);gets(s);t=a=p=i=!printf("%d\n",a%9?:t?9:0)) for(n=strlen(s)-1,c=1;s[i];p-=f(++i),c=c*x*x*x*x*x%9) t+=s[i]-=48, a+=c*(p-1?!p:3)*s[i]%9, p+=f(n--),c*=x; }
229B
2016/12/19追記
aに加算する値は1回につき高々8*3*9=216、ループは|S|≦10^5なので、毎回剰余を取らなくてもオーバーフローしない
またぐっと睨むとnがいらないことに気付く
char s[1<<17]; i,t,a,p,x; f(n){return!n|n%3?x=n%9,0:f(n/3)+1;} main(c){ for(gets(s);gets(s);t=a=p=i=!printf("%d\n",a%9?:t?9:0)) for(c=1;s[i];p-=f(i),c=c*x*x*x*x*x%9) t+=s[i]-=48, a+=c*(p-1?!p:3)*s[i], p+=f(strlen(++i+s)),c*=x; }
219B
2017/06/19追記
fのreturn文省略で2B、pの正負反転で1Bの計3B短縮
char s[1<<17]; i,t,a,p,x,g; f(n){g=!n|n%3?x=n%9,0:f(n/3)+1;} main(c){ for(gets(s);gets(s);t=a=p=i=!printf("%d\n",a%9?:t?9:0)) for(c=1;s[i];p+=f(i),c=c*x*x*x*x*x%9) t+=s[i]-=48, a+=c*(~p?!p:3)*s[i], p-=f(strlen(++i+s)),c*=x; }
216B
