# CFR 71 C. Round Table Knights ( Cycle DP )

Problem - C - Codeforces

dp[ i ] : i 號武士 ( 若 i >= N, 則是 i - N 號 ) 逆時針最多可以和幾個心情好的武士，連續且相鄰兩兩間隔距離 x 進行連線。
dp[ i ] = ( i 好武士心情好 ) ? max{ 1, dp[ i - x ] } : 0

O( N ^ 1.5 ) / O( N )

```int N;
vi A; // good mood;

void init(){
cin >> N;
A = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ];
}

vi gm2; // good mood table * 2

void preprocess(){
gm2 = vi( N << 1 );
for( int i = 0; i < 2 * N; ++i )
gm2[ i ] = i < N ? A[ i ] : A[ i - N ];
}

void solve(){
for( int i = 1; i * i <= N; ++i ){
if( not ( N % i == 0 ) )
continue;
if( not ( N / i > 2 ) )
continue;

vi dp( N << 1 );
for( int j = 0; j < N; ++j )
dp[ j ] = gm2[ j ];
for( int j = 0; j < N << 1; ++j )
if( gm2[ j ] and j + i < N << 1 and gm2[ j + i ] )
upmax( dp[ j + i ], dp[ j ] + 1 );

if( *max_element( dp.begin(), dp.end() ) >= N / i )
cout << "YES" << endl,
exit( 0 );

if( not ( i > 2 ) ) // otherwise not polygon
continue;

dp = vi( N << 1 );
for( int j = 0; j < N; ++j )
dp[ j ] = gm2[ j ];
for( int j = 0; j < N << 1; ++j )
if( gm2[ j ] and j + N / i < N << 1 and gm2[ j + N / i ] )
upmax( dp[ j + N / i ], dp[ j ] + 1 );

if( *max_element( dp.begin(), dp.end() ) >= i )
cout << "YES" << endl,
exit( 0 );
}
cout << "NO" << endl;
}
```