SDOI 2017 나무 자르기 게임
참고: 이 기사의 약정:\(s u\)는 노드\(u\)의 하위 노드 집합을 나타냅니다.\(ls u\)는 노드\(u\)의 경아들 집합을 나타낸다.이 가벼운 아들은 나무를 쪼개서 만든 것을 가리킨다.
간단\(dp\) 방정식을 먼저 나열합니다.\(f[u][i]\)는\(u\)를 최고점으로 하는 연결 블록 중 이/가\(i\)인 방안의 수를 나타낸다.그럼\(f[u][i]=\sum {j\oplusk=i}f[v][j]*f[u][k]\)는 분명히\(FWT\)의 형식이다.그러면 우리는 먼저 모든 생성 함수를\(FWT\) (FWT\) 한 다음에 곱하기를 더하면 바로 할 수 있고, 마지막에\(IFWT\) 하면 된다.우리는\(g[u]\) 를\(u\) 를 뿌리로 하는 하위 트리에서 이차 또는 화의 생성 함수를 표시하도록 명령합니다.비교적 명백한 것은\(g[u]=f[u]+\sum {v\ins u}g[v]\)
지금 어떻게 수리해야 할지 고려 중입니다.먼저 트리 체인을 분할한 다음\(f, g\)와 위에서 설명한\(lf[u]=\prod {v\in ls u}(f[v]+1)\),\(lg[u]=\sum {v\in ls u} g[v]\)
명령\(t\)는\(u\)의 중아들을 표시하면 전이 방정식이 있다.\[f[u]=(f[t]+1)*lf[u]*w[u]=f[t]*lf[u]*w[u]+lf[u]*w[u]\g[u]=f[u]+g[t]+lg[u]\]
그렇다면 매트릭스 곱셈\[\left[\begin {matrix} lf[u]*w[u] & 0 &lf[u] & 0 &lf[u]\lf[\lf[u] & lf [u] + lg [u]\0 &1\0 &\\\{{{matrix}\right[u] * *\0 &1\0 &1\0 &1\0 &1\\\\\{{{{{{0&lf[u} lf[u} lf[u] 행렬 곱셈 [u]\[\[\[\[\[\[\[\left]\1\\\end {matrix}\right]\]는 이것이 맞는지 쓰기 시작해서 확인할 수 있습니다.
그리고 라인 트리에 행렬 연승적을 유지합니다.\(lf\) 를 유지할 때 나누어야 하지만\(10007\) 의 배수가 나오면 매우 번거롭습니다.\(0\) 로 나누어야 합니다.따라서 우리는 각 노드에 대해 한 그루의 선을 긋고 가벼운 아들의 승적을 유지해야 한다.
또 하나의 최적화가 있다.\[\left[\begin{matrix} a1&0&b1\c1&1&1&&&\0&\\\\{begin{matrix} a1 & 0 &b1\c1&1&1&1&\0&1&\0&\\\\\\{{matrix}\right*\left[\begin {matrix} a 1&0&0&0&b1&b1\c1&\c1&\[\[\[\[\[\[\\[\\[\[\\\[\\\\\\\\\\end{matrix}\right]\] 따라서 우리는 네 개의 점만 저장하면 된다.상수가 크게 줄어들다.
코드는 아래와 같다(매우 못생겼다)
#include
#include
#include
#include
#include
#include
#define N (30010)
#define P (10007)
#define M (128)
#define inf (0x7f7f7f7f)
#define rg register int
#define Label puts("NAIVE")
#define spa print(' ')
#define ent print('
')
#define rand() (((rand())<
inline void read(T &x){
static bool iosig;
static char c;
for(iosig=false,c=read();!isdigit(c);c=read()){
if(c=='-')iosig=true;
if(c==-1)return;
}
for(x=0;isdigit(c);c=read())x=((x+(x<<2))<<1)+(c^'0');
if(iosig)x=-x;
}
inline char readchar(){
static char c;
for(c=read();!isalpha(c)&&!isdigit(c);c=read())
if(c==-1)return 0;
return c;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN],*ooh=obuf;
inline void print(char c) {
if(ooh==obuf+OUT_LEN)fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf;
*ooh++=c;
}
template
inline void print(T x){
static int buf[30],cnt;
if(x==0)print('0');
else{
if(x<0)print('-'),x=-x;
for(cnt=0;x;x/=10)buf[++cnt]=x%10+48;
while(cnt)print((char)buf[cnt--]);
}
}
inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}
}
using namespace fastIO1;
int n,m,Q;
int w[N],ind,E,fi[N],ne[N<<1],b[N<<1],invm;
int fa[N],son[N],siz[N],top[N],dfn[N],rdfn[N],tmp[N],en[N],pos[N];
int ksm(int a,int p){
int res=1;
while(p){
if(p&1)res=1ll*res*a%P;
a=1ll*a*a%P,p>>=1;
}
return res;
}
struct poly{
int a[M];
void FWT(int *a,int tp){
for(int i=1;i s;
void build(int l,int r,int x){
if(l==r){s[x]=f[tmp[l]]+zt[0];return;}
int mid=(l+r)>>1;
build(l,mid,x*2),build(mid+1,r,x*2+1);
s[x]=s[x*2]*s[x*2+1];
}
void init(int L){
s.resize((L+1)<<2),len=L;
if(!L)s[1]=zt[0];else build(1,len,1);
}
void modify(int L,int R,int k,poly t,int x){
if(L==R){s[x]=t;return;}
int mid=(L+R)>>1;
if(k<=mid)modify(L,mid,k,t,x*2);
else modify(mid+1,R,k,t,x*2+1);
s[x]=s[x*2]*s[x*2+1];
}
void modify(int k,poly t){modify(1,len,k,t,1);}
}lf[N];
struct Matrix{
poly a,b,c,d;
Matrix(){}
Matrix (poly x,poly y){a=b=c=x,d=x+y;}
Matrix operator *(Matrix x){
Matrix ans;
ans.a=a*x.a,ans.b=a*x.b+b,ans.c=c*x.a+x.c,ans.d=c*x.b+x.d+d;
return ans;
}
}t[N<<2];
void add(int x,int y){
ne[++E]=fi[x],fi[x]=E,b[E]=y;
}
void dfs1(int u,int pre){
siz[u]=1,f[u]=zt[w[u]];
for(int i=fi[u];i;i=ne[i]){
int v=b[i];
if(v==pre)continue;
fa[v]=u,dfs1(v,u),siz[u]+=siz[v];
f[u]=f[u]*(f[v]+zt[0]),g[u]=g[u]+g[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
g[u]=g[u]+f[u];
}
void dfs2(int u){
rdfn[dfn[u]=++ind]=u;
if(son[u])top[son[u]]=top[u],dfs2(son[u]),en[u]=en[son[u]];
else en[u]=u;
for(int i=fi[u];i;i=ne[i]){
int v=b[i];
if(v==fa[u]||v==son[u])continue;
top[v]=v,dfs2(v),lg[u]=lg[u]+g[v];
}
int ls=0;
for(int i=fi[u];i;i=ne[i])
if(b[i]!=fa[u]&&b[i]!=son[u])tmp[pos[b[i]]=++ls]=b[i];
lf[u].init(ls);
}
void build(int l,int r,int x){
if(l==r){
int u=rdfn[l];
t[x]=Matrix(lf[u].s[1]*zt[w[u]],lg[u]);
return;
}
int mid=(l+r)>>1;
build(l,mid,x*2),build(mid+1,r,x*2+1);
t[x]=t[x*2]*t[x*2+1];
}
void modify(int L,int R,int k,Matrix mat,int x){
if(L==R){t[x]=mat;return;}
int mid=(L+R)>>1;
if(k<=mid)modify(L,mid,k,mat,x*2);
else modify(mid+1,R,k,mat,x*2+1);
t[x]=t[x*2]*t[x*2+1];
}
Matrix query(int L,int R,int l,int r,int x){
if(L==l&&R==r)return t[x];
int mid=(L+R)>>1;
if(r<=mid)return query(L,mid,l,r,x*2);
else if(l>mid)return query(mid+1,R,l,r,x*2+1);
else return query(L,mid,l,mid,x*2)*query(mid+1,R,mid+1,r,x*2+1);
}
int main(){
read(n),read(m),invm=ksm(m,P-2);
for(int i=1;i<=n;i++)read(w[i]);
for(int i=0;i
전재 대상:https://www.cnblogs.com/Romeolong/p/10221312.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.