HDU 4669 Muttiples on a circule（2013多校連合7 1004）

http://acm.hdu.edu.cn/showproblem.php?pid=4669
Muttiples on a circule
Time Limit：3000/1000 MS（Java/Others）    メモリLimit：65535/65535 K（Java/Others）Total Submission（s）：767    Acceepted Submission(s)：209
Problem Description
Tom has a necklace with n jewels.The e e isa number on each jwel.Now Tom wants to selecta wonderful chain ffrom thenecklace.A chain will regardwonderful the wonderful valul value of the the chainininininininininininininininmmmmmmmmmtttttttttttttfffffffrerererererererefefefefefefefefefefefefefefefefefefefeaaaaaaaammmmmmmmmmmmmmmmmmmmmmmmmockwise order and concateates them together.In this way，he gets a decimal number which is defined as the wonderful value.
For example、consider a necklace with 5 jewels and corese ponding numbers on the jewels are 9 6 4 2 8（9 and 8 are neighborhond）.Asume we take K=7，then wen find that only five five five five caltres
Now Tom wants to know that how many ways he can follow to select a wonderful chain from his necklace.
 
Input
The input contains several test cases、terminated by EOF.
Each case begins with two integers n（1≦n≦50000）、K（1≦K≦200）、the length of the necklace and the key number.
The second line consists of n integer numbers，the i-th number a
i(1≦a
i ≦1000）indicating the number on the ith jwel.It’s given in clockwise order.
 
Output
For each test case、print a number indicating how many ways Tom can follow to select a wonderful chain.
考え方：まず、リングをチェーンに変えてもいいです。例えば、もともとは9 6、4、8、8、2のチェーンにして、9、4、8、4のチェーンにして、それから元のリングをn個のビーズにして、dp[i]、[j]を設定して、i番目のビーズで終わり、前に最大n個のビーズを含みます。（ここでi番目はチェーンのi番目を指します。私たちはn番目から始めます。）例に対して、8番目で終わるのは5つのケース8、28、428、6428、96428、5つのケースです。9番目で終わるのは9、89、289、4289、64289、5つの場合があります。他のプッシュしやすいです。まず暴力は8で終わります。その後、どのようにして9で終わる方案に素早く移行するかを考えて、8で終わるすべての状態を分かりました。簡単に述べるために、8で終わる方案をV 8で代用して、V 9は9で終わる方案に取って代わっています。
ご存知のように、V 8については、96428を除いて、他の（n−1）の状況は直接にV 9に移行することができ、すなわち8->89,28->289->>4289,6428->>289に移行することができます。このn−1の場合、私たちはモードkによってkに分割され、O（k）の複雑度で移動することができます。すなわち、dp[i-1]、[j]私たちは転送を完了し、最後にV 9を取得します。
前の例を理解したら、この問題はもう90%できました。10%は何ですか？
ここで注意するのはビーズの権利値の範囲は1から1000までです。したがって、私たちはこのステップを移行する時（dp[i-1]、[j]->dp[i]“（（*10＋9）%k”）は10に乗るのではなく、10^lenを掛けます。ここでlenはi番目の数の十進数を指します。これは処理によって得られます。
また、私達が移動する時に必要な情報は前の方の情報だけですので、dp[50000][200]のような大きな空間を設けずに、スクロール配列の思想を取り入れて、使用空間を交換することができます。
以上は全体の考えで、コードの実現にはまだいくつかの細かいところがあります。具体的には下記のコードを参考にして実現します。

#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 50010
#define ll long long
using namespace std;
int getlen(int x)
{
    int sum=1;
    while(x/10)
    {
        sum++;
        x/=10;
    }
    return sum;
}
int pow[200010];
int a[maxn],len[maxn];
int cout[2][210];
void init(int n,int mod)
{
    int i;pow[0]=1;
    for(i=1;i<=n;i++)
    pow[i]=(pow[i-1]*10)%mod;
}
int main()
{
  //  freopen("dd.txt","r",stdin);
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        int i;
        memset(cout,0,sizeof(cout));
        init(n*4,k);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            len[i]=getlen(a[i]);
        }
        a[n]=a[0];
        len[n]=len[0];
        ll ans=0;
        int le=0,sum=0;
        for(i=n;i>0;i--)
        {
            sum=(a[i]*pow[le]+sum)%k;
            cout[0][sum]++;
            le+=len[i];
        }
        ans+=cout[0][0];
        int t=1;
        for(i=1;i<n;i++)
        {
            memset(cout[t],0,sizeof(cout[t]));
            for(int j=0;j<k;j++)
            {
                cout[t][(j*pow[len[i]]+a[i])%k]+=cout[1-t][j];
            }
            sum=(sum*pow[len[i]]+a[i])%k;
            cout[t][sum]--;
            cout[t][a[i]%k]++;
            ans+=cout[t][0];
            t=1-t;
            sum=((sum-a[i]*pow[le])%k+k)%k;
        }
        printf("%I64d
",ans);

    }
    return 0;
}