HDU-5332(접두어 및 최적화 dp/CDQ+NTT)
HDU-5332(CDQ+NTT/ 접두어 및 최적화 dp)
점\(i\) 의 답을 차례로 구하는 것을 고려하다
가령 현재\(i-1\)개의 점이 있고 제\(i\)개의 점 앞에 있는 점수\(j\)를 열거하고 있다면\(dp i=dp {i-j-1}\cdot(j+1)^2\cdotC(i-1,i-j-1)\cdotj!\)
직접 이전은\(O(n^2)\)이며,\(dp\) 이전이 차치와 관련이 있음을 볼 수 있으므로\(CDQ\)분할+\(NTT\)로 해결할 수 있습니다.
이런 간단하고 거친 방법에 관하여 템플릿 문제 HDU-5730 문제 풀이
다음은 폭력 코드입니다.
#include
using namespace std;
#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
template inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template inline void cmax(T &a,T b){ ((a>=1,x=x*x%P) if(k&1) res=res*x%P;
return res;
}
void NTT(int n,ll *a,int f){
rep(i,1,n-1) if(rev[i]>i) swap(a[i],a[rev[i]]);
for(reg int i=1;i>1;
Solve(l,mid);
int R=1,c=-1;
while(R<=r-l+1) R<<=1,c++;
rep(i,1,R) rev[i]=(rev[i>>1]>>1)|((i&1)< \[\\]
다음은 \ (O (n) \) 방법입니다.
전이 관찰\(dp i=dp {i-j-1}\cdot(j+1)^2\cdotC(i-1,i-j-1)\cdotj!\)
변형\(dp i=dp j\cdot(i-j)^2\cdot\rac{(i-1)!}{j!}\)
접두사 및 전환 고려
곱하기 문제는 매개 변수 분리를 통해 잘 해결될 수 있습니다.\(i-j)^2\) 문제입니다
\(i\rightarrow i+1\)일 때\((i-j)^2\rightarrow(i+1-j)^2\)
꺼내 보시면\(x^2\rightarrow(x+1)^2=x^2+2x+1\)
따라서\(a=\sum x^2dp j, b=\sum xdp j, c=\sum dp j\) 를 기록할 수 있습니다
그래서 매번\(i\) 증가하고\(a=a+2b+c,b=b+c\)
#include
using namespace std;
#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
template inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template inline void cmax(T &a,T b){ ((a 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
