【HDOJ】4351 Digital root

digital root = n==0 ? 0 : n%9==0 ? 9:n%9;
可以简单证明一下
n = a0*n^0 + a1*n^1 + ... + ak * n^k
n%9 = a0+a1+..+ak
然后，数学归纳易知结论是正确的。
因此9个状态就够了，表示%9的结果。
这里需要特殊处理0， 表示状态为0。

 /* 4351 */
 #include <iostream>
 #include <sstream>
 #include <string>
 #include <map>
 #include <queue>
 #include <set>
 #include <stack>
 #include <vector>
 #include <deque>
 #include <algorithm>
 #include <cstdio>
 #include <cmath>
 #include <ctime>
 #include <cstring>
 #include <climits>
 #include <cctype>
 #include <cassert>
 #include <functional>
 #include <iterator>
 #include <iomanip>
 using namespace std;
 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>
 #define stpii            set<pair<int, int> >
 #define mpii            map<int,int>
 #define vi                vector<int>
 #define pii                pair<int,int>
 #define vpii            vector<pair<int,int> >
 #define rep(i, a, n)     for (int i=a;i<n;++i)
 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 #define clr                clear
 #define pb                 push_back
 #define mp                 make_pair
 #define fir                first
 #define sec                second
 #define all(x)             (x).begin(),(x).end()
 #define SZ(x)             ((int)(x).size())
 #define lson            l, mid, rt<<1
 #define rson            mid+1, r, rt<<1|1

 typedef struct {
     short sum;
     short lst, rst, st;
 } node_t;

 const int maxn = 1e5+;
 int zn[maxn];
 bool visit[];
 int a[maxn];
 node_t nd[maxn<<];
 int Mod9[];
 short sum_st[][];
 short st_st[][];
 int n;

 void init() {
     rep(i, , )
         Mod9[i] = i % ;

     rep(st, , ) {
         rep(i, , ) {
             int nst = ;

             rep(j, , ) {
                 if (st & (<<j)) {
                     int k = Mod9[i + j];
                     nst |= (<<k);
                 }
             }
             sum_st[i][st] = nst;
         }
     }

     rep(lst, , ) {
         rep(rst, lst, ) {
             int nst = ;
             rep(i, , ) {
                 if ((lst & (<<i)) == )
                     continue;
                 rep(j, , ) {
                     if (rst & (<<j)) {
                         int k = Mod9[i+j];
                         nst |= (<<k);
                     }
                 }
             }
             st_st[lst][rst] = st_st[rst][lst] = nst;
         }
     }
 }

 void PushUp(int rt) {
     int lb = rt << ;
     int rb = lb | ;

     nd[rt].sum = Mod9[nd[lb].sum + nd[rb].sum];
     nd[rt].lst = nd[lb].lst | sum_st[nd[lb].sum][nd[rb].lst];
     nd[rt].rst = nd[rb].rst | sum_st[nd[rb].sum][nd[lb].rst];
     nd[rt].st = nd[lb].st | nd[rb].st | st_st[nd[lb].rst][nd[rb].lst];
 }

 void Build(int l, int r, int rt) {
     if (l == r) {
         if (zn[l] == zn[l-]) {
             nd[rt].sum = a[l];
             nd[rt].lst = nd[rt].rst = nd[rt].st = ( << a[l]);
         } else {
             nd[rt].sum = a[l];
             nd[rt].lst = nd[rt].rst = nd[rt].st = ;
         }
         return ;
     }

     int mid = (l + r) >> ;

     Build(lson);
     Build(rson);

     PushUp(rt);
 }

 node_t Query(int L, int R, int l, int r, int rt) {
     if (L==l && R==r) {
         return nd[rt];
     }

     int mid = (l + r) >> ;

     if (R <= mid) {
         return Query(L, R, lson);
     } else if (L > mid) {
         return Query(L, R, rson);
     } else {
         node_t lnd = Query(L, mid, lson);
         node_t rnd = Query(mid+, R, rson);
         node_t ret;

         ret.sum = Mod9[lnd.sum + rnd.sum];
         ret.lst = lnd.lst | sum_st[lnd.sum][rnd.lst];
         ret.rst = rnd.rst | sum_st[rnd.sum][lnd.rst];
         ret.st = lnd.st | rnd.st | st_st[lnd.rst][rnd.lst];

         return ret;
     }
 }

 void solve() {
     Build(, n, );

     int q;
     node_t d;
     int l, r;

     scanf("%d", &q);
     while (q--) {
         scanf("%d %d", &l, &r);
         memset(visit, false, sizeof(visit));
         d = Query(l, r, , n, );
         rep(i, , ) {
             if (d.st & (<<i))
                 visit[i] = true;
         }
         visit[] = visit[];
         visit[] = (zn[r] - zn[l-]) > ;
         int cnt = ;
         per(i, , ) {
             if (visit[i]) {
                 if (cnt == )
                     printf("%d", i);
                 else
                     printf(" %d", i);
                 if (--cnt == )
                     break;
             }
         }

         while (cnt) {
             printf(" -1");
             --cnt;
         }
         putchar('\n');
     }
 }

 int main() {
     ios::sync_with_stdio(false);
     #ifndef ONLINE_JUDGE
         freopen("data.in", "r", stdin);
         freopen("data.out", "w", stdout);
     #endif

     int t;

     init();
     scanf("%d", &t);
     rep(tt, , t+) {
         scanf("%d", &n);
         rep(i, , n+) {
             scanf("%d", &a[i]);
             zn[i] = zn[i-] + (a[i] == );
             a[i] %= ;
         }
         printf("Case #%d:\n", tt);
         solve();
         if (tt != t)
             putchar('\n');
     }

     #ifndef ONLINE_JUDGE
         printf("time = %d.\n", (int)clock());
     #endif

     return ;
 }

数据发生器。

 from copy import deepcopy
 from random import randint, shuffle
 import shutil
 import string

 def GenDataIn():
     with open("data.in", "w") as fout:
         t = 10
         bound = 10**9
         fout.write("%d\n" % (t))
         for tt in xrange(t):
             n = randint(10, 20)
             fout.write("%d\n" % (n))
             L = []
             for i in xrange(1, n):
                 x = randint(0, bound)
                 L.append(x)
             L.append(0)
             shuffle(L)
             fout.write(" ".join(map(str, L)) + "\n")
             q = (n+1)*n/2
             fout.write("%d\n" % (q))
             for l in xrange(1, n+1):
                 for r in xrange(l, n+1):
                     fout.write("%d %d\n" % (l, r))

 def MovDataIn():
     desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
     shutil.copyfile("data.in", desFileName)

 if __name__ == "__main__":
     GenDataIn()
     MovDataIn()