Submission #857193

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string w;
    cin>>w;
    int n = (int)w.length();

    vector<vector<int>> P(n+1);
    for (int i=1; i<=n; i++)
        for (int j=1; j<i; j++)
            if (i%j==0)
                P[i].push_back(j);
    
    vector<vector<bool>> G(n, vector<bool>(n, true));

    for (int s=0; s<n; s++)
    for (int t=s; t<n; t++)
    {
        for (int p: P[t-s+1])
        {
            bool f = true;
            for (int i=s+p; i<=t && G[s][t]; i++)
                if (w[i] != w[i-p])
                    f = false;
            if (f)
                G[s][t] = false;
            if (!G[s][t])
                break;
        }
    }

    vector<long long> A(n);
    vector<long long> B(n, n);

    for (int i=0; i<n; i++)
    {
        if (G[0][i])
            B[i] = 1,
            A[i] = 1;
        for (int j=0; j<i; j++)
        if (G[j+1][i])
        {
            long long t = B[j]+1;
            if (t<B[i])
                B[i] = t,
                A[i] = 0;
            if (t==B[i])
                A[i] += A[j],
                A[i] %= 1000000007;
        }
    }

    cout<<B[n-1]<<endl;
    cout<<A[n-1]<<endl;
}

Submission Info

Judge Result