[HNOI 2011] 수학 숙제 (BZOJ 2326)

2682 단어 ZOJ
제목 링크:
http://www.lydsy.com/JudgeOnline/problem.php?id=2326   f [i] 는 i 의 답 을 나타 낸다. 그러면 f [i] = f [i - 1] * 10 + i     (i < 10) f[i] = f[i - 1] * 100 + i    (  100<=i<=999) ……   우 리 는 N 의 범위 가 매우 크다 는 것 을 발 견 했 기 때문에 행렬 로 가속 전달 을 해 야 한다. 그리고 세그먼트 로 전달 행렬 의 계 수 를 바 꿔 야 한다.  

#include 
 
   
    
  
#include 
  
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              #include 
             
               #include 
              
                #define MID(x,y) ((x+y)>>1) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long LL; LL n, m; const int MAX = 5; struct Mat{ int row, col; LL mat[MAX][MAX]; }; //initialize square matrix to unit matrix Mat unit(int n){ Mat A; A.row = A.col = n; memset(A.mat, 0, sizeof(A.mat)); for (int i = 0; i < n; i ++) A.mat[i][i] = 1; return A; } //return A*B%mod Mat mul(Mat A, Mat B, int mod){ Mat C; C.row = A.row; C.col = B.col; for (int i = 0; i < A.row; i ++){ for (int j = 0; j < B.col; j ++){ C.mat[i][j] = 0; for (int k = 0; k < A.col; k ++) //            ，              C.mat[i][j] += A.mat[i][k] * B.mat[k][j]; C.mat[i][j] %= mod; } } return C; }; //return A^n%mod Mat exp_mod(Mat A, LL n, int mod){ Mat res = unit(A.row); while(n){ if (n & 1LL){ res = mul(res, A, mod); } A = mul(A, A, mod); n >>= 1; } return res; } Mat A, res; void changeA(LL p){ A.col = A.row = 3; A.mat[0][0] = p % m; A.mat[0][1] = 1; A.mat[0][2] = 0; A.mat[1][0] = 0; A.mat[1][1] = 1; A.mat[1][2] = 1; A.mat[2][0] = 0; A.mat[2][1] = 0; A.mat[2][2] = 1; } void init(){ res.col = 1; res.row = 3; res.mat[0][0] = 0; res.mat[1][0] = 1; res.mat[2][0] = 1; changeA(10); } int main(){ cin >> n >> m; init(); LL k1 = 0; LL k2 = 9; LL ct = 10; while(n >= k2){ res = mul(exp_mod(A, k2-k1, m), res, m); k1 = k2; if (k2 == 99999999999999999) k2 = 100000000000000001; k2 = k2 * 10 + 9; changeA(10*ct); ct *= 10; } if (n > k1) res = mul(exp_mod(A, n-k1, m), res, m); cout << res.mat[0][0] << endl; return 0; }
permission 과 uses - permission 의 차이
node 닫기modules 페이지 매핑 시 끊임없이 보내는 요청

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage