HDU 4669 Mutiples on a circle 不知道该归为哪一类。

题意：给你N个珠宝和一个K，每个珠宝上面都有数字，这个珠宝做成项链，把珠宝上的数字拼起来如果可以整除掉K，那么久说这个数字为wonderful value,问你有多少种方案可以组成WONDERFUL VALUE。

对每个数取余并记录多少位，这样的话拼数的时候好操作。详细解法贴个结题报告吧。

代码：

 #include <iostream>

 #include <stdio.h>

 using namespace std;

 int dp[][];

 int a[];

 int len[];

 int decmod[<<];

 int digit(int a)

 {

     int len = ;

     while(a)

     {

         a /=  ;

         len++;

     }

     return len;

 }

 void getdecmod(int k,int n)

 {

     decmod[] = ;

     int i;

     for(i = ;i <= n<<;i++)

     {

         decmod[i] = (decmod[i-]*)%k;

     }

 }

 int main()

 {

     int n,k;

     while(~scanf("%d %d",&n,&k))

     {

         int j,i;

         for(i = ;i <= n;i++)

         scanf("%d",&a[i]),a[i+n] = a[i];

         getdecmod(k,n);

         for(i = ;i <= n;i++)

         {

             for(j = ;j < k;j++)

             dp[i][j] = ;

         }

         int r ;

         for(i = ;i <= n;i++)

         {

             len[i+n] = len[i] = digit(a[i]);

             r = a[i] = a[i+n] = a[i]%k;

             dp[i][r]++;

         }

         r = a[];

         int sublen = ;

         for(i = n;i > ;i--)

         {

             sublen += len[i+];

             r = (a[i]*decmod[sublen]+r)%k;

             dp[][r]++;

         }

         sublen = ;

         for(i = ;i<= n;i++)

         sublen += len[i];

         int last;

         last = r;

        // printf("%d--------------\n",last);

         __int64 ans = dp[][];

         for(i = ;i <= n;i++)

         {

             for(j =;j < k;j++)

             {

                 r = (j*decmod[len[i]]+a[i])%k;

                 dp[i][r] += dp[i-][j];

             }

             last = (last*decmod[len[i]]+a[i])%k;

             dp[i][last]--;

             last = (last-(a[i]*decmod[sublen])%k+k)%k;

             ans += dp[i][];

         }

         printf("%I64d\n",ans);

     }

 }

巴特西

HDU 4669 Mutiples on a circle 不知道该归为哪一类。

最新文章

热门文章