JZOJ 4374. [GDOI 2016 시 뮬 레이 션 3.9] 폭주 의 묘기
10703 단어 행렬 곱셈
처음에 두 문자열 '0', '1' 을 정 했 습 니 다. 매번 작업 할 때마다 두 문자열 을 새 문자열 로 연결 합 니 다.N 번 동작 한 문자열 에 주어진 문자열 T 의 개 수 를 포함 하고 P 모드 에 대한 답 을 구하 십시오.M 은 문자열 T 의 길이 입 니 다.
Data Constraint 30% 의 데이터 에 대해 N ≤ 20 대 100% 의 데이터, N ≤ 109, M ≤ 104, P ≤ 109
해제
상위 30% 는 직접 폭력 처리 가 가능 한 것 으로 나 타 났 다.n 번 째 문자열 의 T 개 수 를 f [n] 로 표시 합 니 다.이 득, f [n] = f [n - 1] + f [n - 2] + C 는 직렬 S [n - 2] 와 직렬 S [n - 1] 를 합병 한 후 중간 부분의 공헌 을 나타 내 고 전, 후 m - 1 을 직접 기록한다.KMP 나 Hash 로 계산 할 수 있 습 니 다.그 다음 에 중간 에 순환 이 있 는 것 을 발견 할 수 있 기 때문에 행렬 을 구성 하여 이동 할 수 있다.
SRC
#include
#include
#include
#include
#include
using namespace std ;
#define N 100000 + 10
#define M 50000 + 10
typedef long long ll ;
const int MO1 = 10007 ;
const int MO2 = 32767 ;
struct Matrix {
int mat[5][5] ;
void set() {
mat[1][1] = mat[2][2] = mat[3][3] = mat[4][4] = 1 ;
}
} S , B , C ;
char s[30][M] , T[N] ;
int f[30] , val1[M] , val2[M] , s1[M] , s2[M] ;
int st1 , st2 , A1 , A2 , ans ;
int n , m , P ;
Matrix operator * ( Matrix A , Matrix B ) {
memset( C.mat , 0 , sizeof( C.mat ) ) ;
for (int i = 1 ; i <= 4 ; i ++ ) {
for (int j = 1 ; j <= 4 ; j ++ ) {
for (int k = 1 ; k <= 4 ; k ++ ) {
C.mat[i][j] = (C.mat[i][j] + (ll) A.mat[i][k] * B.mat[k][j] % P) % P ;
}
}
}
return C ;
}
void PreMat() {
B.mat[1][2] = B.mat[2][1] = B.mat[2][2] = B.mat[3][4] = B.mat[4][3] = 1 ;
B.mat[3][2] = A1 ;
B.mat[4][2] = A2 ;
}
void Power( int k ) {
S.set() ;
while ( k ) {
if ( k & 1 ) S = S * B ;
B = B * B ;
k /= 2 ;
}
}
int Calc( char *ch ) {
int len = strlen( ch ) , ret = 0 ;
val1[0] = val2[0] = 0 ;
s1[0] = s2[0] = 1 ;
for (int i = 1 ; i <= len ; i ++ ) {
s1[i] = s1[i-1] * 2 % MO1 ;
s2[i] = s2[i-1] * 2 % MO2 ;
val1[i] = (val1[i-1] * 2 + ch[i-1] - '0') % MO1 ;
val2[i] = (val2[i-1] * 2 + ch[i-1] - '0') % MO2 ;
}
for (int l = 1 ; l <= len - m + 1 ; l ++ ) {
int r = l + m - 1 ;
int v1 = (val1[r] - val1[l-1] * s1[r-l+1] % MO1 + MO1) % MO1 ;
int v2 = (val2[r] - val2[l-1] * s2[r-l+1] % MO2 + MO2) % MO2 ;
if ( v1 == st1 && v2 == st2 ) ret = (ret + 1) % P ;
}
return ret ;
}
void Merge( int k , int l , int r ) {
strcpy( s[k] , s[l] + strlen(s[l]) - m + 1 ) ;
strncat( s[k] , s[r] , m - 1 ) ;
}
int main() {
freopen( "machine.in" , "r" , stdin ) ;
freopen( "machine.out" , "w" , stdout ) ;
scanf( "%d%d%d" , &n , &m , &P ) ;
scanf( "%s" , T + 1 ) ;
for (int i = 1 ; i <= m ; i ++ ) {
st1 = (st1 * 2 + T[i] - '0') % MO1 ;
st2 = (st2 * 2 + T[i] - '0') % MO2 ;
}
s[0][0] = '0' , s[1][0] = '1' ;
f[0] = Calc( s[0] ) ;
f[1] = Calc( s[1] ) ;
for (int i = 2 ; i <= 23 ; i ++ ) {
strcpy( s[i] , s[i-2] ) ;
strcat( s[i] , s[i-1] ) ;
f[i] = Calc( s[i] ) ;
}
if ( n <= 23 ) { printf( "%d
" , f[n] ) ; return 0 ; }
Merge( 24 , 22 , 23 ) ;
Merge( 25 , 23 , 22 ) ;
Merge( 26 , 23 , 23 ) ;
f[24] = f[23] + f[22] + Calc( s[24] ) ; // 2 3
A1 = Calc( s[25] ) ; // 4 1
A2 = Calc( s[26] ) ; // 4 3
PreMat() ;
Power( n - 24 ) ;
f[1] = f[23] ;
f[2] = f[24] ;
f[3] = 1 ;
f[4] = 0 ;
for (int i = 1 ; i <= 4 ; i ++ ) ans = (ans + (ll) f[i] * S.mat[i][2] % P) % P ;
printf( "%d
" , ans ) ;
return 0 ;
}
이상
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CF1117D Magic Gems dp 매트릭스 곱셈[ d p [ n − m − 1 ] d p [ n − m ] . d p [ n − 1 ] ] ∗\begin{bmatrix} dp[n-m-1] & dp[n-m] & ... & dp[n-1]\end{bmatrix}* [...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.