【ARC 064-F】【XSY 2575】Rotated Palindromes(DP)(文字列)

Descriptionしかし、Cちゃんはゲーム作りに夢中になっていたため、国家合宿チームの一員として、156の宿題問題などを完全に忘れてしまった.あと1日で宿題が終わるが,彼はまだ1題もやっていない.そこで彼は急いで最も簡単に見える問題を選んだ.
「整数Nを指定すると、1からKの間の整数の文字列がどれだけあるかを求めてください.これにより、その文字列は長さNの文字列から循環シフトして得ることができます.循環シフトとは、文字列のある接頭辞(空でもよい)を文字列の末尾に移動することです.例えば、「1221」の循環シフトでは「1221」、「2211」、「2112」、「1122」が得られます4つの文字列.結果は109+7で型を取ります.」
Cさんの合宿チームの資格がCCFに取り消されないように、この問題を完成させてください.
Input
第1行は2つの整数N,Kを含む.
Output
条件を満たす文字列数対109+7の型取りの結果を出力します.
Sample Input
Sample Input 1
4 2
Sample Input 2
1 10
Sample Input 3
6 3
Sample Input 4
1000000000 1000000000
Sample Output
Sample Output 1
6
Sample Output 2
10
Sample Output 3
75
Sample Output 4
875699961
HINT
最初の例では、「1111」、「1122」、「1221」、「2211」、「2112」、「2222」の6文字列が条件を満たしている.
まず列挙回文列を考えると,回文列は回文であるため,列挙回文列の半分しか用いられず,回文列の個数は(m^{(n+1)/2})である.
各文字列には(n)種の循環シフト後の文字列があるはずですが、計算すると答えよりずっと大きいことがわかります.重複があるからです.
重複しない文字列の個数をどのように計算するかを考慮し,文列のループ節を列挙することができる.
二つの状況に分けて討論する.
1.循環節が奇数
1つのループ・セクションは必ずループ・セクションであるため、1つのループ・セクションをループ・シフトする長さが(len)であると重複するため、(len)個の新しい文字列が生成されます.
2.循環節が偶数
上記の理由で,ループ節は必ず返信し,我々は(len/2)の長ささえあれば繰り返す.
例えば、シリアル(1221111221)、私たちが2桁移動した後、シリアルは(21122212)となり、元のシリアルとは異なるように見えますが、私たちは回文シリアルを列挙する際にも(21122212)まで列挙するので、重複も計算されます.
続いてDP.
我々はまず(n)のすべての因数を前処理し,(a[])
最小ループ節が(a[i])の場合、条件に合致する文列がいくつあるかを(dp[i])とする.
私たちは(dp[i])から(dp[a[i]の因子])を減算し、(a[i])のときの最小のサイクルを保証するために.
ansは,回文列に寄与する文字列の個数を直接加算すればよい.

#include
#define mod 1000000007
#define int long long
using namespace std;
int dp[2010],cnt,n,k,a[2010],ans;
int fastpow(int x,int y)
{
    int sum=1;
    while(y)
    {
        if(y&1)
        {
            sum=(1ll*sum*x)%mod;
        }
        x=(1ll*x*x)%mod;
        y>>=1;
    }
    return sum;
}
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i*i<=n;i++)//    
    {
        if(n%i==0)
        {
            a[++cnt]=i;
            if(i*i!=n)
            {
                a[++cnt]=n/i;
            }
        }
    }
    sort(a+1,a+cnt+1);
    for(int i=1;i<=cnt;i++)
    {
        dp[i]=fastpow(k,(a[i]+1)/2);//       
        for(int j=1;j