Posts Tagged 二分

HDOJ 2429 Word Game

Posted by twcai in ACM/ICPC on November 5, 2008

成都网络赛的题目，这题可以用矩阵乘法求解。以单词为点，能前后相连的单词之间连边，得到一个有向图，求长度为奇数且小于等于N的不同的S->T的路径数。设该有向图的邻接矩阵为A，则可通过求A + A ^ 3 + … + A ^ N求解。
因为 N 比较大所以要通过二分来求矩阵和，即 A + A ^ 3 + A ^ 5 + A ^ 7 = (A + A ^ 3) + A^4 * (A + A ^ 3)。贴下代码：

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. char tem[33][12];
  6. int l[33], t, m, n;
  7.  
  8. class matrix{
  9. public :
  10.     int rw;
  11.     int cn;
  12.     int ma[33][33];
  13.  
  14.     matrix()
  15.     {
  16.         rw = 0;
  17.         cn = 0;
  18.     }
  19.  
  20.     matrix(int &x, int &y)
  21.     {
  22.         int i, j;
  23.         rw = x;
  24.         cn = y;
  25.  
  26.         for(i = 0; i < rw; i++)
  27.             for(j = 0; j < cn; j++)
  28.                 ma[i][j] = 0;
  29.     }
  30.  
  31.     matrix(const matrix &x)
  32.     {
  33.         int i, j;
  34.         rw = x.rw;
  35.         cn = x.cn;
  36.         for(i = 0; i < rw; i++)
  37.             for(j = 0; j < cn; j++)
  38.                 ma[i][j] = x.ma[i][j];
  39.     }
  40.  
  41.     matrix operator*(matrix &x)
  42.     {
  43.         int i, j, k;
  44.         matrix ret(cn, x.rw);
  45.         for(i = 0; i < rw ; i++)
  46.             for(j = 0; j < x.cn ; j++)
  47.             {
  48.                 for(k = 0; k < cn; k++)
  49.                     ret.ma[i][j] += ma[i][k] * x.ma[k][j];
  50.                 if(ret.ma[i][j] > 10001)
  51.                     ret.ma[i][j] %= 10001;
  52.             }
  53.             return ret;
  54.     }
  55.  
  56.     matrix power(int x)
  57.     {
  58.         matrix ret(rw, cn);
  59.  
  60.         if(x == 1)
  61.             return *this;
  62.         if(x == 2)
  63.         {
  64.             int i, j ,k;
  65.             for(i = 0; i < rw; i++)
  66.                 for(j = 0; j < cn; j++)
  67.                 {
  68.                     for(k = 0; k < cn; k++)
  69.                         ret.ma[i][j] += ma[i][k] * ma[k][j];
  70.                     if(ret.ma[i][j] >= 10001)
  71.                         ret.ma[i][j] %= 10001;
  72.                 }
  73.         }
  74.         else if((x & 1) == 0)
  75.         {
  76.             ret = this->power(x >> 1);
  77.             ret = ret.power(2);
  78.         }
  79.         else
  80.         {
  81.             ret = this->power(x >> 1);
  82.             ret = ret.power(2);
  83.             ret = ret * (*this);
  84.         }
  85.  
  86.         return ret;
  87.     }
  88.  
  89.     inline matrix operator+= (const matrix &x)
  90.     {
  91.         int i, j;
  92.         for(i = 0; i < rw; i++)
  93.             for(j = 0; j < cn; j++)
  94.             {
  95.                 ma[i][j] += x.ma[i][j];
  96.                 if(ma[i][j] > 10001)
  97.                     ma[i][j] %= 10001;
  98.             }
  99.             return *this;
  100.     }
  101.  
  102.     inline matrix operator = (const matrix &x)
  103.     {
  104.         int i, j;
  105.         rw = x.rw;
  106.         cn = x.cn;
  107.  
  108.         for(i = 0; i < rw; i++)
  109.             for(j = 0; j < cn; j++)
  110.                 ma[i][j] = x.ma[i][j];
  111.         return *this;
  112.     }
  113.  
  114. };
  115.  
  116. inline matrix mtx(matrix &ltr, int n)
  117. {
  118.     if((n & 1) == 0) n--;
  119.     if(n == 1) return ltr;
  120.  
  121.     int tmp = (n + 1) >> 1;
  122.     matrix ret, t1, t2;
  123.     t1 = mtx(ltr, tmp - 1);
  124.     t2 = ltr.power(tmp);
  125.     if((tmp & 1) == 0)
  126.     {
  127.         ret = t2;
  128.         ret = ret * t1;
  129.         ret += t1;
  130.     }
  131.     else
  132.     {
  133.         ret = t2 * ltr;
  134.         ret = ret * t1;
  135.         ret += t1;
  136.         ret += t2;
  137.     }
  138.     return ret;
  139. }
  140.  
  141. int main()
  142. {
  143.     int i, j;
  144.     int st, ed;
  145.     matrix ret;
  146.  
  147.     scanf("%d", &t);
  148.     while(t--)
  149.     {
  150.         scanf("%d", &m);
  151.         for(i = 0; i < m + 2; i++)
  152.         {
  153.             scanf("%s", tem[i]);
  154.             l[i] = strlen(tem[i]);
  155.         }
  156.         scanf("%d", &n);
  157.  
  158.         matrix ltr(m, m);
  159.         st = -1; ed = -1;
  160.         for(i = 0; i < m; i++)
  161.         {
  162.             if(st == -1 && strcmp(tem[i], tem[m]) ==0)
  163.                 st = i;
  164.             if(ed == -1 && strcmp(tem[i],tem[m+1])==0)
  165.                 ed = i;
  166.  
  167.             for(j= 0; j < m; j++)
  168.             {
  169.                 if(tem[i][l[i]-1] == tem[j][0])
  170.                     ltr.ma[i][j] = 1;
  171.             }
  172.         }
  173.         ret = mtx(ltr, n);
  174.         printf("%dn", ret.ma[st][ed]);
  175.     }
  176.     return 0;
  177. }

, , ,

No Comments