[BZOJ4818] [Sdoi 2017] [용척 원리] [매트릭스 최적화 DP] 시퀀스 계수

용척 원리를 고려하면 Ans=f 만족과 p의 배수 - f 만족과 p의 배수는 질량을 포함하지 않는 것을 DP로 할 수 있다. f(i, j)는 i위로 옮기는 것을 의미하고 전 i위와 모드 P는 j의 방안수와 같다.
그러면 분명히 f(i,j)= ∑f(i-3-1,k)∗cnt(j-3-k+p)modp에서 cnti는 1~m 중 모드 P가 i의 개수(두 번째 개수를 계산할 때 질량수를 나가야 한다)를 나타낸다.직접 이동하면 당연히 안 된다. 더욱이 이 DP는 행렬 곱셈으로 최적화할 수 있고 일반적인 방법으로 하면 된다는 것을 발견할 수 있다.
#include 
#include 
#include 
#include 
#include 
#define N 110
#define P 20170408
#define M 20000010

using namespace std;

int n,m,p;
char vis[M];
int prime[1280000];
int cnt[N];

inline void Add(int &x,int y){
  if((x+=y)>=P) x-=P;
}

struct Mat{
  int a[N][N];
  Mat(){ for(int i=0;i

for(int j=0;j

0; } int *operator [](int x){ return a[x]; } friend Mat operator *(Mat A,Mat B){ Mat C; for(int i=0;i

for(int j=0;j

for(int k=0;k

1ll*A[i][k]*B[k][j]%P); return C; } }f1,f2,g; inline Mat Pow(Mat A,int c){ Mat ret; for(int i=0;i

1; for(;c;c>>=1,A=A*A) if(c&1) ret=ret*A; return ret; } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=m;i++) cnt[i%p]++; for(int i=0;i

for(int j=0;j

%p]; f1[0][0]=f2[0][0]=1; f1=f1*Pow(g,n); vis[1]=1; for(int i=2;i<=m;i++){ if(!vis[i]) prime[++*prime]=i; for(int j=1;j<=*prime&&1ll*prime[j]*i<=m;j++) if(vis[prime[j]*i]=1,i%prime[j]==0) break; } memset(cnt,0,sizeof(cnt)); for(int i=1;i<=m;i++) if(vis[i]) cnt[i%p]++; for(int i=0;i

for(int j=0;j

%p]; f2=f2*Pow(g,n); printf("%d
"
,(f1[0][0]-f2[0][0]+P)%P); //printf("%d
"
,clock()); return 0; }

좋은 웹페이지 즐겨찾기