转载请注明原文地址http://www.cnblogs.com/LadyLex/p/8536399.html
听说今年省选很可怕？刷题刷题刷题
省选已经结束了但是我们要继续刷题刷题刷题
目标是“有思维难度的DP题”！
一，uoj316
这个不用多说……NOI2017的D1T3，难度肯定是有的
个人觉得那个dp方程难想……
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define mod 998244353
#define K 1010
#define L 2048
#define RG register
#define LL long long
inline int quick_mod(int di,int mi)
{
int ret=;
for(;mi;mi>>=,di=(LL)di*di%mod)
if(mi&)ret=(LL)ret*di%mod;
return ret;
}
int poww[L],logi[L],rev[L],len=;
inline void dft(int *a,int ra,int opt)
{
register int i,j,l,d=logi[len]-logi[ra],wn,tmp,*w,*x,*y;
for(i=;i<ra;++i)if(i<(rev[i]>>d))swap(a[i],a[rev[i]>>d]);
for(d=;d<=ra;d<<=)
for(wn=((opt==)?(len/d):(-len/d)),i=,l=(d>>);i<ra;i+=d)
for(w=poww+(opt==?:len),j=,x=a+i,y=x+l;j<l;++j,++x,++y,w+=wn)
tmp=(LL)(*w)*(*y)%mod,*y=(*x-tmp+mod)%mod,*x=(*x+tmp)%mod;
if(opt==-)
for(tmp=quick_mod(ra,mod-),i=;i<ra;++i)a[i]=(LL)a[i]*tmp%mod;
}
int n,k,p,q,pp[K];
int g[K][K],h[K][K],f[K<<];
inline int min(int a,int b){return a<b?a:b;}
int tmp1[L];
inline int get_inv(int *a,int *ret,int ra)
{
if(ra==){ret[]=quick_mod(a[],mod-);return ;}
RG int i,la=,r1=get_inv(a,ret,ra+>>);
while(la<(ra<<))la<<=;
memcpy(tmp1,a,ra<<),memset(tmp1,,(la-ra)<<);
memset(ret,,(la-r1)<<);
dft(tmp1,la,),dft(ret,la,);
for(i=;i<la;++i)ret[i]=(LL)ret[i]*(+mod-(LL)tmp1[i]*ret[i]%mod)%mod;
dft(ret,la,-);return ra;
}
inline void rev_copy(int *to,int *st,int ra)
{for(RG int i=;i<ra;++i,++to)*to=st[ra-i-];}
inline void reverse(int *st,int ra)
{for(RG int t,i=,j=ra-;i<j;++i,--j)t=st[i],st[i]=st[j],st[j]=t;}
int tmp2[L],tmp3[L];
inline int get_mod(int *a,int ra,int *p,int rp,int *ret)
{
while(ra&&!a[ra-])--ra;
while(rp&&!p[rp-])--rp;
if(ra<rp){memcpy(ret,a,ra<<),memset(ret+ra,,(rp-ra)<<);return rp;}
RG int i,j,re=ra-rp+,la=;
while(la<(re<<))la<<=;
rev_copy(tmp2,p,rp);memset(tmp2+re,,(la-re)<<);
get_inv(tmp2,tmp3,re),memset(tmp3+re,,(la-re)<<);
rev_copy(tmp2,a,ra),memset(tmp2+re,,(la-re)<<);
dft(tmp3,la,);dft(tmp2,la,);
for(i=;i<la;++i)tmp2[i]=(LL)tmp2[i]*tmp3[i]%mod;
dft(tmp2,la,-);
la=;while(la<ra)la<<=;
reverse(tmp2,re),
memset(tmp2+re,,(la-re)<<);
memcpy(tmp3,p,rp<<),memset(tmp3+rp,,(la-rp)<<);
dft(tmp2,la,),dft(tmp3,la,);
for(i=;i<la;++i)tmp2[i]=(LL)tmp2[i]*tmp3[i]%mod;
dft(tmp2,la,-);
for(i=;i<rp;++i)ret[i]=(a[i]-tmp2[i]+mod)%mod;
memset(ret+rp,,(la-rp)<<);
while(rp&&!ret[rp-])--rp;
return rp;
}
int c[L],d[L],e[L],tmp[L];
inline int calc(int k)
{
RG int i,j,u,ra=k+,r1=k+,lim,la=;
memset(g,,sizeof(g));
memset(h,,sizeof(h));
g[k][]=(LL)pp[k]*q%mod;
g[k][]=h[k][]=;
for(i=k-;i>;--i)
{
ra=k/i,g[i][]=h[i][]=;
for(j=;j<=ra;++j)
for(u=;u<j;++u)
h[i][j]=(h[i][j]+(LL)h[i][u]*g[i+][j-u-]%mod*pp[i]%mod*q)%mod;
for(j=;j<=ra;++j)
for(u=;u<=j;++u)
g[i][j]=(g[i][j]+(LL)h[i][u]*g[i+][j-u])%mod;
}
memset(f,,sizeof(f)),f[]=;
for(i=;i<=(ra<<);++i)
for(j=,lim=min(k+,i);j<=lim;++j)
f[i]=(f[i]+(LL)f[i-j]*g[][j-]%mod*q)%mod;
int ret=;
if(n<=(ra<<))
{
for(i=max(,n-k);i<=n;++i)
ret=(ret+(LL)f[i]*g[][n-i])%mod;
return ret;
}
memset(c,,sizeof(c)),c[]=;
memset(d,,sizeof(d));d[ra]=;
for(i=;i<=ra;++i)d[ra-i]=(LL)q*g[][i-]%mod;
memset(e,,sizeof(e)),e[]=;
while(la<(ra<<))la<<=;
for(lim=n-k-;lim;lim>>=)
{
if(lim&)
{
memcpy(tmp,c,k<<);memset(tmp+k,,(la-k)<<);
dft(e,la,),dft(tmp,la,);
for(i=;i<la;++i)e[i]=(LL)e[i]*tmp[i]%mod;
dft(e,la,-);
get_mod(e,k<<,d,ra,e);
}
dft(c,la,);
for(i=;i<la;++i)c[i]=(LL)c[i]*c[i]%mod;
dft(c,la,-);
get_mod(c,k<<,d,ra,c);
} }
int main()
{
RG int i,x,y;
scanf("%d%d%d%d",&n,&k,&x,&y);logi[]=;
while(len<=(k+<<))len<<=,logi[len]=logi[len>>]+;
poww[]=poww[len]=,poww[]=quick_mod(,(mod-)/len);
for(i=;i<len;++i)poww[i]=(LL)poww[i-]*poww[]%mod;
for(i=;i<len;++i)
if(i&)rev[i]=(rev[i>>]>>)|(len>>);
else rev[i]=(rev[i>>]>>);
p=(LL)x*quick_mod(y,mod-)%mod,q=(LL)(y-x)*quick_mod(y,mod-)%mod;
for(pp[]=,pp[]=p,i=;i<=k;++i)pp[i]=(LL)pp[i-]*p%mod;
printf("%d\n",(calc(k)-calc(k-)+mod)%mod);
}
uoj316
二，bzoj3326
题目模型不算特别新的数位DP，能想到它在干什么，但是……
那个式子，想推对必须非常严谨才行……
#include <cstdio>
#include <cstring>
using namespace std;
#define RG register
#define mod 20130427
#define N 100010
#define LL long long
char cB[<<],*S=cB,*T=cB;
#define getc (S==T&&(T=(S=cB)+fread(cB,1,1<<15,stdin),S==T)?0:*S++)
inline int read()
{
RG int x=;RG char c=getc;
while(c<''|c>'')c=getc;
while(c>=''&c<='')x=*x+(c^),c=getc;
return x;
}
inline int Sum(int a){return ((LL)a*(a+1ll)/)%mod;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int ge2[N],sum2[N],ge3[N],sum3[N],no_zero_sum3[N],B,lena,bit[N],lenb,bin[N];
inline int calc(bool start,int left,int lim,int cnt,int sum,int sum_of_substring )
{
if(lim==)return ;
if(start)
return
(
(LL) Sum(lim-) * ge2[left] %mod * bin[left] %mod + //前与后连接之后前面的贡献
(LL) ( lim - ) %mod * sum3[left] %mod + no_zero_sum3[left] %mod +//后面的子串
(LL) ( lim - ) %mod * sum2[left] %mod//前与后连接之后后面的贡献
)%mod;
int new_sum=( (LL) sum * B %mod * lim %mod + (LL) Sum(lim-) * cnt %mod ) %mod;
return
(
(LL) sum_of_substring * lim %mod * bin[left] %mod + //之前的子串
(LL) new_sum * ge2[left] %mod * bin[left] %mod + //前与后连接之后前面的贡献
(LL) lim %mod * sum3[left] %mod +//后面的子串 不乘cnt
(LL) cnt * lim %mod * sum2[left] %mod//前与后连接之后后面的贡献 ,要乘cnt 因为再前面不同
)%mod;
}
inline int dfs(bool start,int st,int cnt,int sum,int sum_of_substring)
{
if(st==)return ;
int new_sum=( (LL) sum * B %mod + (LL) ( cnt + ) * bit[st] %mod )%mod;
return
( new_sum + calc(start, st- , bit[st] , cnt + , sum , sum_of_substring ) +
dfs(, st - , cnt + , new_sum , (sum_of_substring + new_sum)%mod ) )%mod;
}
signed main()
{
RG int i,j,len,ans;
B=read(),lena=read();
for(i=lena;i;--i)bit[i]=read();
lenb=read();len=max(lena,lenb);
if(lena>||bit[]>)
{
--bit[],j=;
while(bit[j]<)bit[j]+=B,--bit[j+],++j;
while(lena>&&!bit[lena])--lena;
}
for(bin[]=ge2[]=i=;i<=len;++i)
{
bin[i]=(LL)bin[i-]*B%mod;
ge2[i]=( ge2[i-] + bin[i] )%mod;
ge3[i]=(LL) Sum(i) * bin[i] %mod;
sum2[i]=( (LL) sum2[i-] * B %mod + Sum ( bin[i] - ) )%mod;
sum3[i]=( (LL) Sum(B-) * bin[i-] %mod * ge2[i-] %mod + (LL)B * sum2[i-] %mod + (LL) B * sum3[i-] %mod )%mod;
no_zero_sum3[i]=( (LL) Sum(B-) * bin[i-] %mod * ge2[i-] %mod +
(LL) (B - ) * sum2[i-] %mod + (LL) (B - ) * sum3[i-] %mod + no_zero_sum3[i-] )%mod;
}
ans=mod-dfs(,lena,,,);
for(i=lenb;i;--i)bit[i]=read();
printf("%d\n",(ans+dfs(,lenb,,,))%mod);
}
bzoj3326
三，bzoj4513
二进制的数位DP
听dalao们说挺简单……但是我觉得是比较好的一道数位dp
wq的做法又简洁又快，但是我太弱了不会……
只好打一个稍微麻烦的dp了
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define RG register
#define LL long long
LL n,m,k,bin[],f_ge[][][][],f_sum[][][][];
int main()
{
RG int mod,i,j,ta,tb,tc,a,b,c,x,y,z,t,len,lena,lenb,lenc,bita,bitb,bitc;LL ans,tmp;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld%d",&n,&m,&k,&mod),--n,--m;
lena=lenb=lenc=;
tmp=n;while(tmp)++lena,tmp>>=;
tmp=m;while(tmp)++lenb,tmp>>=;
tmp=k;while(tmp)++lenc,tmp>>=;
len=max(lena,max(lenb,lenc));
for(bin[]=i=;i<=len;++i)bin[i]=(bin[i-]<<)%mod;
memset(f_ge,,sizeof(f_ge)),memset(f_sum,,sizeof(f_sum));
f_ge[len+][][][]=;ans=;
for(i=len;~i;--i)
{
bita=(n>>i)&,bitb=(m>>i)&,bitc=(k>>i)&;
for(a=;a<;++a)for(b=;b<;++b)for(c=;c<;++c)
if(f_ge[i+][a][b][c])
for(x=;x<;++x)
{
if(a && x>bita)break;
for(y=;y<;++y)
{
if(b && y>bitb)break;
z=x^y;
if(c && z<bitc)continue;
ta=(a && bita==x)?:,tb=(b && bitb==y)?:,tc=(c && bitc==z)?:;
f_ge[i][ta][tb][tc]=(f_ge[i][ta][tb][tc]+f_ge[i+][a][b][c])%mod;
f_sum[i][ta][tb][tc]=( f_sum[i][ta][tb][tc]+f_sum[i+][a][b][c])%mod;
if(z)f_sum[i][ta][tb][tc]=( f_sum[i][ta][tb][tc]+ bin[i]*f_ge[i+][a][b][c]%mod )%mod;
}
}
}
k%=mod;
for(a=;a<;++a)for(b=;b<;++b)for(c=;c<;++c)
ans=(ans+f_sum[][a][b][c]-k*f_ge[][a][b][c]%mod+mod)%mod;
printf("%lld\n",ans);
}
}
bzoj4513
四，uoj141
很棒的插头(轮廓线)dp题目……我从一开始就没有想出来……
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
#define RG register
#define N 15
#define mod 998244353
#define D 51
#define SZ 612497
int n,m,ans[];
LL K,B[N][N],lower,bin[];
char row[N],line[N];
struct node{LL state;int next,cnt,val;};
struct hash_map
{
node s[SZ+];int e,adj[SZ+];
inline void init(){e=;memset(adj,,sizeof(adj));}
inline void update(LL state,int val,int cnt)
{
RG int i,pos=(state%SZ+(LL)val*SZ)%SZ;
for(i=adj[pos];i&&(s[i].state!=state||s[i].val!=val);i=s[i].next);
if(!i)s[++e].state=state,s[e].val=val,s[e].cnt=cnt,s[e].next=adj[pos],adj[pos]=e;
else s[i].cnt=(s[i].cnt+cnt)%mod;
}
}f[];
inline void execute(int x,int y,int cur)
{
RG int i,j,last=cur^,tot=f[last].e,val,val1,val2,cnt,sum,half;
LL state,nstate;
f[cur].init();
for(i=;i<=tot;++i)
{
state=f[last].s[i].state,val=f[last].s[i].val,cnt=f[last].s[i].cnt;
nstate=state%bin[y-],state/=bin[y-];
val1=state%D,state/=D;
val2=state%D,state/=D;
sum=val1+val2+B[x][y],half=sum>>;
f[cur].update(nstate+state*bin[y+]+(sum-half)*bin[y]+half*bin[y-],val,cnt);
f[cur].update(nstate+state*bin[y+]+half*bin[y]+(sum-half)*bin[y-],val,cnt);
}
}
int main()
{
RG int i,j,cur=;
for(bin[]=i=;i<=;++i)bin[i]=bin[i-]*D;
scanf("%d%d%lld",&n,&m,&K);
scanf("%s",row+),scanf("%s",line+);
B[][]=K;
for(i=;i<=n;++i)
for(j=;j<=m;++j)
B[i+][j]+=B[i][j]>>,B[i][j+]+=B[i][j]>>,B[i][j]&=;
for(i=;i<=n;++i)if(row[i]=='')lower+=B[i][m+];
for(j=;j<=m;++j)if(line[j]=='')lower+=B[n+][j];
f[].update(,,);
RG int tot,last,val,cnt;LL state;
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)cur^=,execute(i,j,cur);
cur^=,last=cur^;tot=f[last].e;
f[cur].init();
for(j=;j<=tot;++j)
{
state=f[last].s[j].state,val=f[last].s[j].val;
if(row[i]=='')val+=state/bin[m];
state=(state%bin[m])*D;
f[cur].update(state,val,f[last].s[j].cnt);
}
}
for(i=;i<=f[cur].e;++i)
{
state=f[cur].s[i].state/D;
val=f[cur].s[i].val;
for(j=;j<=m;++j,state/=D)if(line[j]=='')val+=state%D;
ans[val]=(ans[val]+f[cur].s[i].cnt)%mod;
}
for(i=;i<=n*m;++i)ans[i]=(ans[i]+ans[i-])%mod;
RG int q;LL l,r;
scanf("%d",&q);
while(q--)
{
scanf("%lld%lld",&l,&r);
if(r<lower||l>lower+n*m){puts("");continue;}
l=max(0ll,l-lower),r=min((LL)n*m,r-lower);
printf("%d\n",l?(ans[r]-ans[l-]+mod)%mod:ans[r]);
}
}
uoj141
五，uoj129
NOI2015D1T3，难度还是稍微有的
我自己只想出了50pts做法，其实只差一点，把n/2改成$\sqrt(n)$的复杂度就行了
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
inline int min(int a,int b){return a<b?a:b;}
#define RG register
#define LL long long
#define N 510
#define L 266
int f[L][L],g[][L][L];
vector<int>cont[N];
int n,mod,ans,lim,full,prime[N],id[N],tot;bool vis[N];
int bin[];
inline void print(int s)
{
for(RG int i=;i<lim;++i)printf("%d",(s>>i)& );
printf("\n");
}
signed main()
{
scanf("%d%d",&n,&mod);
RG int x,y,z,tmp,i,j,k;
for(i=;i<=n;++i)
{
if(!vis[i])prime[++tot]=i,id[i]=tot;
for(j=;(x=i*prime[j])<=n;++j)
{vis[x]=;if(i%prime[j]==)break;}
}
lim=min(,tot),full=(<<lim)-;
for(bin[]=i=;i<=lim;++i)bin[i]=bin[i-]<<;
for(i=;i<=n;++i)
{
for(x=i,y=,j=;j<=lim;++j)
if(x%prime[j]==)
{
y|=bin[j-];
while(x%prime[j]==)x/=prime[j];
}
cont[id[x]].push_back(y);
}
f[][]=;
for(x=,y=cont[].size();x<y;++x)
{
memcpy(g[],f,sizeof(f));
memcpy(g[],f,sizeof(f));
for(i=full;~i;--i)
for(j=full;~j;--j)
if((i&j)==)
{
if((cont[][x]&j)==)g[][i|cont[][x]][j]=(g[][i|cont[][x]][j]+g[][i][j])%mod;
if((cont[][x]&i)==)g[][i][j|cont[][x]]=(g[][i][j|cont[][x]]+g[][i][j])%mod;
}
for(i=full;~i;--i)
for(j=full;~j;--j)
if((i&j)==)f[i][j]=(g[][i][j]+g[][i][j]-f[i][j])%mod;
}
for(k=;k<=tot;++k)
{
memcpy(g[],f,sizeof(f));
memcpy(g[],f,sizeof(f));
for(x=,y=cont[k].size();x<y;++x)
{
for(i=full;~i;--i)
for(j=full;~j;--j)
if((i&j)==)
{
if((cont[k][x]&j)==)g[][i|cont[k][x]][j]=(g[][i|cont[k][x]][j]+g[][i][j])%mod;
if((cont[k][x]&i)==)g[][i][j|cont[k][x]]=(g[][i][j|cont[k][x]]+g[][i][j])%mod;
}
}
for(i=full;~i;--i)
for(j=full;~j;--j)
if((i&j)==)f[i][j]=((LL)g[][i][j]+g[][i][j]-f[i][j])%mod;
}
for(i=full;~i;--i)
for(j=full;~j;--j)
if((i&j)==)ans=(ans+f[i][j])%mod;
printf("%d\n",(ans+mod)%mod);
}
uoj129
六，uoj372
刷新期望概率观的题目
思维难度不错，而且之前我是没见过期望概率用积分的……
虽然出题人说这很套路
#include <cstdio>
#include <cstring>
#define N 35
#define mod 998244353
#define N2 5000010
#define LL long long
#define RG register
#define MD 2332333
struct hash_map
{
struct node{int state,next,id;}s[N2];
int e,adj[MD];
inline void ins(int state,int id)
{
RG int pos=state%MD;
s[++e].state=state,s[e].next=adj[pos];adj[pos]=e;s[e].id=id;
}
inline int find(int state)
{
RG int i,pos=state%MD;
for(i=adj[pos];i;i=s[i].next)
if(s[i].state==state)return s[i].id;
return -;
}
}H;
struct node
{
int A[N],n;
inline node operator * (const node &a)const
{
RG int i,j;
node c;memset(c.A,,sizeof(c.A));
c.n=n+a.n;
for(i=;i<=n;++i)
for(j=;j<=a.n;++j)
c.A[i+j]=(c.A[i+j]+(LL)A[i]*a.A[j])%mod;
return c;
}
}X[N2];
int tot,T,vis[N],d[N][N],adj[N],C[N][N];
int inv[N],inv2[N],bin[N],cnt1[],n,m,A[N],B[N];
inline int count(int s){return cnt1[s&]+cnt1[s>>];}
inline int dfs(RG int rt,int G)
{
RG int ret=bin[rt-];vis[rt]=T;
for(RG int i=;i<=n;++i)
if(vis[i]!=T&&d[rt][i]&&(G&bin[i-]))ret|=dfs(i,G);
return ret;
}
inline void update(node &a,const node &b,int d)
{
RG int i,j,nn=b.n+d;
memset(A,,sizeof(A)),memset(B,,sizeof(B));
for(i=;i<=d;++i)
if(i&)A[i]=mod-C[d][i];else A[i]=C[d][i];
for(i=;i<=b.n;++i)for(j=;j<=d;++j)
B[i+j]=(B[i+j]+(LL)b.A[i]*A[j])%mod;
for(i=;i<=nn;++i)a.A[i]=(a.A[i]+B[i])%mod;
}
inline int getans(RG int G)
{
int pre=H.find(G);
if(pre!=-)return pre;
if(!G)
{
++tot,X[tot].n=,X[tot].A[]=;H.ins(G,tot);
return tot;
}
++T,++tot,H.ins(G,tot);
RG int i,u,j,un=,cid=tot;
int block[N];
for(i=;i<=n;++i)
if((G&bin[i-])&&vis[i]!=T)
{u=dfs(i,G);if(u!=G)block[++un]=u;}
if(un)
{
for(X[cid]=X[getans(block[])],i=;i<=un;++i)
X[cid]=X[cid]*X[getans(block[i])];
return cid;
}
X[cid].n=count(G);
for(i=;i<=n;++i)
if(G&bin[i-])
update(X[cid],X[getans(G&(~adj[i]))],count(G&adj[i])-);//考虑每个点作为最大值 for(i=X[cid].n;i;--i)X[cid].A[i]=(LL)inv[i]*X[cid].A[i-]%mod;//求导
RG int sum=;
for(i=X[cid].n;i;--i)sum=(sum+(LL)X[cid].A[i]*inv2[i])%mod;//求导第二部分
X[cid].A[]=(mod+inv2[X[cid].n]-sum)%mod;//考虑最大值<=t/2
return cid;
}
int main()
{
RG int i,j,a,b;
scanf("%d%d",&n,&m);
for(bin[]=i=;i<=;++i)bin[i]=bin[i-]<<;
for(inv[]=inv[]=,i=;i<=n+;++i)inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;
for(inv2[]=,i=;i<=n+;++i)inv2[i]=(LL)inv2[i-]*inv[]%mod;
for(i=;i<=n;++i)adj[i]=bin[i-];
for(i=;i<bin[];++i)cnt1[i]=cnt1[i^(i&-i)]+;
for(i=;i<=m;++i)
scanf("%d%d",&a,&b),d[a][b]=d[b][a]=,adj[a]|=bin[b-],adj[b]|=bin[a-];
for(C[][]=,i=;i<=n+;++i)
for(C[i][]=,j=;j<=i;++j)
C[i][j]=(C[i-][j-]+C[i-][j])%mod;
RG int fin=getans(bin[n]-),ans=;
for(i=;i<=n;++i)
ans=(ans+(LL)inv[n+]*X[fin].A[i])%mod;
for(i=;i<=n;++i)
ans=(ans+(LL)inv[n-i+]*X[fin].A[i]%mod*(bin[n-i+]-))%mod;
printf("%d\n",-ans+mod);
}
uoj372
七，codeforces848E
一开始想了个暴力dp，结果发现自己也漏了不少状态，也重了不少……
然后就很完蛋啊……发现没法打
最后怂了题解，然后题解和我一样先考虑一条弧的状态
但是又不太一样……他考虑的是“弧两端由对称的花分开”，然后枚举第一个对称的位置，统计乘积×方案数
我是直接统计一个半圆
然后最后枚举两个弧拼起来统计答案
这玩意……堆砖的工作……
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define N 50010
#define L (1<<19)+10
#define mod 998244353
#define RG register
#define LL long long
int n,g[N],f0[N],f1[N],f2[N],pf[N];
inline int quick_mod(int di,int mi)
{
RG int ret=;
for(;mi;mi>>=,di=(LL)di*di%mod)
if(mi&)ret=(LL)ret*di%mod;
return ret;
}
int poww[L],rev[L],bin[],logi[L],inv[L],len=;
inline void dft(int *a,int ra,int opt)
{
RG int i,j,d=logi[len]-logi[ra],l,tmp,wn,*w,*x,*y;
for(i=;i<ra;++i)if(i<(rev[i]>>d))swap(a[i],a[rev[i]>>d]);
for(d=;d<=ra;d<<=)
for(i=,l=(d>>),wn=(opt==?(len/d):(-len/d));i<ra;i+=d)
for(j=,x=a+i,y=x+l,w=poww+((opt==)?:len);j<l;++j,++x,++y,w+=wn)
tmp=(LL)(*w)*(*y)%mod,*y=(*x+mod-tmp)%mod,*x=(*x+tmp)%mod;
if(opt==-)
for(i=;i<ra;++i)a[i]=(LL)a[i]*inv[ra]%mod;
}
int tmp1[L],tmp2[L];
inline int solve1(int l,int r)
{
if(l==r)return ;
RG int i,mi=l+r>>,ra=r-l+,la=,r1=solve1(l,mi);
while(la<(ra+r1))la<<=;
for(i=;i<r1;++i)tmp1[i]=f0[l+i];
memset(tmp1+r1,,la-r1<<);dft(tmp1,la,);
for(i=;i<ra;++i)tmp2[i]=(LL)g[i]*pf[i]%mod;
memset(tmp2+ra,,la-ra<<);dft(tmp2,la,);
for(i=;i<la;++i)tmp2[i]=(LL)tmp2[i]*tmp1[i]%mod;
dft(tmp2,la,-);
for(i=mi+;i<=r;++i)f0[i]=(f0[i]+tmp2[i-l-])%mod;
for(i=;i<ra;++i)tmp2[i]=(LL)g[i]*pf[i+]%mod;
memset(tmp2+ra,,la-ra<<);dft(tmp2,la,);
for(i=;i<la;++i)tmp1[i]=(LL)tmp2[i]*tmp1[i]%mod;
dft(tmp1,la,-);
for(i=mi+;i<=r;++i)f1[i]=(f1[i]+tmp1[i--l])%mod;
for(i=;i<r1;++i)tmp1[i]=f1[l+i];
memset(tmp1+r1,,la-r1<<);dft(tmp1,la,);
for(i=;i<la;++i)tmp2[i]=(LL)tmp2[i]*tmp1[i]%mod;
dft(tmp2,la,-);
for(i=mi+;i<=r;++i)if(i-l->=)f0[i]=(f0[i]+tmp2[i-l-])%mod;
for(i=mi+;i<=r;++i)f2[i]=(f2[i]+tmp2[i--l])%mod;
for(i=;i<ra;++i)tmp2[i]=(LL)g[i]*pf[i+]%mod;
memset(tmp2+ra,,la-ra<<);dft(tmp2,la,);
for(i=;i<la;++i)tmp1[i]=(LL)tmp2[i]*tmp1[i]%mod;
dft(tmp1,la,-);
for(i=mi+;i<=r;++i)if(i-l->=)f1[i]=(f1[i]+tmp1[i-l-])%mod;
for(i=;i<r1;++i)tmp1[i]=f2[l+i];
memset(tmp1+r1,,la-r1<<);dft(tmp1,la,);
for(i=;i<la;++i)tmp2[i]=(LL)tmp2[i]*tmp1[i]%mod;
dft(tmp2,la,-);
for(i=mi+;i<=r;++i)if(i-l->=)f2[i]=(f2[i]+tmp2[i-l-])%mod;
solve1(mi+,r);
return ra;
}
signed main()
{
RG int i;
scanf("%d",&n);while(len<(n<<))len<<=;
for(bin[]=i=;i<=;++i)bin[i]=bin[i-]<<;
for(i=;i<=;++i)logi[bin[i]]=i;
for(inv[]=((mod+)>>),i=;i<=;++i)inv[bin[i]]=(LL)inv[bin[i-]]*inv[]%mod;
for(i=;i<len;++i)
if(i&)rev[i]=(rev[i>>]>>)|(len>>);
else rev[i]=rev[i>>]>>;
poww[]=poww[len]=,poww[]=quick_mod(,(mod-)/len);
for(i=;i<len;++i)poww[i]=(LL)poww[i-]*poww[]%mod;
for(i=;i<=n+;++i)pf[i]=(LL)i*i%mod;
g[]=,g[]=,g[]=,g[]=;
for(i=;i<=n;i+=)g[i]=(g[i-]+g[i-])%mod;
f0[]=,f1[]=,f2[]=;
for(i=;i<=n;++i)
{f0[i]=(LL)g[i]*pf[i]%mod;f1[i]=(LL)g[i]*pf[i+]%mod;f2[i]=(LL)g[i]*pf[i+]%mod;}
solve1(,n);
RG int ans=(LL)(g[n-]+g[n-])*pf[n-]%mod*n%mod;
for(i=;i<n;++i)ans=(ans+(LL)g[i-]*pf[i-]%mod*f0[n-i]%mod*(i-))%mod;
for(i=;i<n;++i)ans=(ans+(LL)*g[i-]*pf[i-]%mod*f1[n-i-]%mod*(i-))%mod;
for(i=;i<=n-;++i)ans=(ans+(LL)g[i-]*pf[i-]%mod*f2[n-i-]%mod*(i-))%mod;
printf("%d\n",ans);
}
cf848E
八，LOJ2331
2017清华集训的题目
从dalao们的博客来看，是最水的一道题？
那还是我太菜了233333……怼了好几天最后还是怂了题解
我一开始想的是分权值讨论，然后从大到小搞
然后一开始以为相同区间的可以合并，然后就是一个$v^{len}-(v-1)^{len}$
结果发现不太对……如果区间有重复的话就会完蛋
到最后这个贡献我也不会dp
发现我们可以离散之后分段考虑，一段之内的贡献是一样的
然后裸转移是$O(n)$的，可以通过前缀和然后搞个倍数乘除一下优化成$O(1)$
太神了……
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define RG register
#define LL long long
#define mod 998244353
#define N 2010
inline int quick_mod(int di,int mi)
{
RG int ret=;
for(;mi;mi>>=,di=(LL)di*di%mod)
if(mi&)ret=(LL)ret*di%mod;
return ret;
}
struct node
{
int l,r,val;
node(int a=,int b=,int c=){l=a,r=b,val=c;}
}q[N],s[N];
int tmp[N],keypt[N],len[N],pt[N];
int lcnt,cnt,scnt,A;
int f[][N],g[][N],lim[N];
int l[N],sl[N];
int pre1[N],pre2[N],pre3[N],inv2[N],inv3[N];
inline int dp(int val)
{
if(val==)return ;
RG int i,j,cur=;
f[][]=g[][]=;s[].r=;
pre1[]=pre2[]=pre3[]=inv2[]=inv3[]=;
for(i=;i<=lcnt;++i)
{
g[][i]=,f[][i]=,sl[i]=sl[i-]+l[i];
pre1[i]=(quick_mod(val,l[i])-quick_mod(val-,l[i])+mod)%mod;
pre2[i]=quick_mod(val-,sl[i]);inv2[i]=quick_mod(pre2[i],mod-);
pre3[i]=quick_mod(val,sl[i]);inv3[i]=quick_mod(pre3[i],mod-);
}
for(i=;i<=scnt;++i)
{
cur^=;
for(j=;j<s[i].l;++j)f[cur][j]=g[cur][j]=;
for(j=s[i].l;j<=s[i].r;++j)
{
f[cur][j]=f[cur^][j];
if(j>s[i-].r)
f[cur][j]=(f[cur][j]+ (LL)g[cur^][s[i-].r] * pre2[s[i-].r] %mod * pre3[j-] %mod * inv3[s[i-].r] %mod * pre1[j] )%mod;
g[cur][j]=(g[cur][j-]+(LL)f[cur][j]*inv2[j])%mod;
}
for(j=s[i].r+;j<=lcnt;++j)g[cur][j]=g[cur][j-],f[cur][j]=;
}
return (LL)g[cur][lcnt]*pre2[lcnt]%mod;
}
inline bool mt(const node &a,const node &b)
{return a.val==b.val?a.r<b.r:a.val<b.val;}
inline void work()
{
RG int i,j,n,m,a,b,val,ge=,ans;
scanf("%d%d%d",&n,&m,&A);
for(i=;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&val);
q[i]=node(a,b,val);
tmp[++ge]=a,tmp[++ge]=b;
}
tmp[++ge]=,tmp[++ge]=n;
sort(tmp+,tmp+ge+),ge=unique(tmp+,tmp+ge+)-tmp-;
for(cnt=,i=;i<=ge;++i)
{
keypt[++cnt]=tmp[i],len[cnt]=;
if(i<ge&&tmp[i]+<tmp[i+])
keypt[++cnt]=tmp[i]+,len[cnt]=tmp[i+]-tmp[i]-;
}
sort(q+,q+m+,mt);
bool can;RG int v,maxn;
memset(lim,,sizeof(lim));
for(i=;i<=m;++i)
{
q[i].l=lower_bound(keypt+,keypt+cnt+,q[i].l)-keypt;
q[i].r=lower_bound(keypt+,keypt+cnt+,q[i].r)-keypt;
for(can=,maxn=,j=q[i].l;j<=q[i].r;++j)
if(!lim[j])lim[j]=q[i].val,can=;
else maxn=max(maxn,lim[j]);
if(!can&&maxn<q[i].val){puts("");return;}
}
ans=;
for(i=;i<=m;)
{
for(scnt=,v=q[i].val,j=i;v==q[j].val&&j<=m;++j)s[++scnt]=q[j];
for(i=j,lcnt=,j=;j<=cnt;++j)
if(lim[j]==v)l[pt[j]=++lcnt]=len[j];
for(j=;j<=scnt;++j)
{
while(lim[s[j].l]!=v)++s[j].l;
while(lim[s[j].r]!=v)--s[j].r;
s[j].l=pt[s[j].l],s[j].r=pt[s[j].r];
}
ans=(LL)ans*dp(v)%mod;
}
for(i=;i<=cnt;++i)
if(!lim[i])ans=(LL)ans*quick_mod(A,len[i])%mod;
printf("%d\n",ans);
}
int main()
{
RG int i,j,t;
scanf("%d",&t);
while(t--)work();
}
LOJ2331
九，LOJ2330
依然是清华集训的题目
依旧没做出来
依旧怂了题解
我们从第三个部分分开始考虑，只输出根的答案
什么样的情况下能有答案呢？
相当于我们要把儿子们分成两半，让他们数量一样
并且能够互相抵消，最后让心停在根节点
那么……肯定是最大的那个儿子最难被抵消
我们考虑最大的那个儿子有多大
然后看其他儿子能不能把它抵消掉
我们定义$f(i)$为以$i$为根的子树最多能抵消多少对生长的贡献
如果一个点子树大小是偶数，
那么我们考虑最大的那个子树，我们肯定优先把它消掉
如果它能被消掉，我们其他子树里的就可以对着叉,怎么叉都可以叉掉
那么我们考虑，优先让这个最大的子树$s1$自相残杀，再用其他儿子来帮他
最多能消掉最大子树的节点数就是$size[rt]-1-size[s1]+f[s1]*2$
那么如果这个数大于等于$size[s1]$，这个树就可以全部消掉，$f[rt]=(size[rt]-1)/2$
而对于处理不是根的点，我们把根到它缩成一条路径，这样和刚才计算根是一样的
然后就可以打了，复杂度是$O(Tn)$的
#include <cstdio>
#include <cstring>
using namespace std;
#define RG register
#define N 100010
char B[<<],*S=B,*T=B;
#define getc (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
inline int read()
{
RG int x=;RG char c=getc;
while(c<''|c>'')c=getc;
while(c>=''&c<='')x=*x+(c^),c=getc;
return x;
}
int W,n,e,adj[N];
struct edge{int zhong,next;}s[N<<];
inline void add(int qi,int zhong)
{s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}
int ans[N],size[N],maxn[N],son1[N],son2[N];
inline void dfs1(int rt,int fa)
{
size[rt]=;son1[rt]=son2[rt]=;
for(RG int u,i=adj[rt];i;i=s[i].next)
if((u=s[i].zhong)!=fa)
{
dfs1(u,rt);size[rt]+=size[u];
if(size[u]>size[son1[rt]])son2[rt]=son1[rt],son1[rt]=u;
else if(size[u]>size[son2[rt]])son2[rt]=u;
}
if(son1[rt])
{
RG int left=size[rt]--size[son1[rt]];
if(size[son1[rt]]<=left+(maxn[son1[rt]]<<))maxn[rt]=size[rt]->>;
else maxn[rt]=maxn[son1[rt]]+left;
}
}
inline void dfs2(int rt,int fa,int dep,int maxson)
{
if((n-dep)&)ans[rt]=;
else
{
RG int bs=((size[maxson]>size[son1[rt]])?maxson:son1[rt]);
ans[rt]=(size[bs]<=n-dep-size[bs]+(maxn[bs]<<));
}
for(RG int u,i=adj[rt];i;i=s[i].next)
if((u=s[i].zhong)!=fa)
if(u==son1[rt])dfs2(u,rt,dep+, (size[maxson]>size[son2[rt]])?maxson:son2[rt]);
else dfs2(u,rt,dep+, (size[maxson]>size[son1[rt]])?maxson:son1[rt]);
}
inline void work()
{
RG int i,a,b;
n=read();
e=;memset(adj,,n+<<);
memset(son1,,n+<<);
memset(son2,,n+<<);
for(i=;i<n;++i)
a=read(),b=read(),add(a,b),add(b,a);
dfs1(,);dfs2(,,,);
if(W==)printf("%d",ans[]);
else for(i=;i<=n;++i)printf("%d",ans[i]);
printf("\n");
}
int main()
{
W=read();int t=read();
while(t--)work();
}
LOJ2330
十，codeforces379E
这题的动归定义其实没那么难
但是……这是个仙人掌啊……仙人掌啊……
所以代码实现就特别完蛋了
我想的是把每个环拆成链，维护链顶链底的状态
打了180行还是错的，细节还贼多
这就比较坑了……于是我找了个标程，发现人家和我的定义一样
但是只有我傻傻的手动分类讨论，人家用for循环枚举加几个简单的ifelse判断就行了
于是深刻的研究了一下std……仙人掌的题目我还的确没做过，这题是不错的入门(?)题
code：
#include <cstdio>
#include <cstring>
using namespace std;
#define RG register
#define inf 0x3f3f3f3f
#define N 2510
inline int max(int a,int b){return a>b?a:b;}
int n,m,e,adj[N];
struct edge{int zhong,next;}s[N<<];
inline void add(int qi,int zhong)
{s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}
int size[N],f[N][N][][],vis[N],top[N];
int g[N][][];
inline void dfs(int rt,int fa)
{
size[rt]=;
++vis[rt];
f[rt][][][]=f[rt][][][]=,f[rt][][][]=;
bool isend=;
for(RG int u,i=adj[rt];i;i=s[i].next)
{
if(vis[u=s[i].zhong]<&&u!=fa)
if(!vis[u])
{
dfs(u,rt);
memset(g,-0x3f,sizeof(g));
if(top[u])
{
if(top[u]==rt)
{
for(RG int j=size[rt];~j;--j)
for(RG int k=size[u];~k;--k)
for(RG int a=;a<;++a)
for(RG int b=;b<;++b)if(a^b^)
for(RG int c=;c<;++c)
g[j+k][a][c]=max(g[j+k][a][c],f[rt][j][a][c]+f[u][k][b][a]);
}
else
{
top[rt]=top[u];
for(RG int j=size[rt];~j;--j)
for(RG int k=size[u];~k;--k)
for(RG int a=;a<;++a)
for(RG int b=;b<;++b)if(a^b^)
for(RG int c=;c<;++c)
g[j+k][a][c]=max(g[j+k][a][c],f[rt][j][a][]+f[u][k][b][c]);
}
}
else
{
for(RG int j=size[rt];~j;--j)
for(RG int k=size[u];~k;--k)
for(RG int a=;a<;++a)
for(RG int b=;b<;++b)if(a^b^)
for(RG int c=;c<;++c)
g[j+k][a][c]=max(g[j+k][a][c],f[rt][j][a][c]+f[u][k][b][]);
}
size[rt]+=size[u];
for(RG int j=size[rt];~j;--j)
for(RG int a=;a<;++a)
for(RG int b=;b<;++b)
f[rt][j][a][b]=g[j][a][b];
}
else isend=,top[rt]=u;
}
if(isend)
for(RG int i=;i<=size[rt];++i)
{
for(RG int a=;a<;++a)f[rt][i][a][]=f[rt][i][a][]=f[rt][i][a][];
f[rt][i][][]=f[rt][i][][]=-inf;
}
++vis[rt];
}
int main()
{
// freopen("Ark.in","r",stdin);
RG int i,a,b;
scanf("%d%d",&n,&m);
for(i=;i<=m;++i)
scanf("%d%d",&a,&b),add(a,b),add(b,a);
memset(f,-0x3f,sizeof(f));
dfs(,);
for(i=;i<=n;++i)
printf("%d ",max(max(f[][i][][],f[][i][][]),f[][i][][]));
}
codeforces379G
十一，codeforces804F
这题太神了！！！！！
膜拜出题的伊朗神犇
题目显然可以分成两问，第一部分统计最后都有谁能拿到假金块
第二部分用第一部分的结果统计答案
可是我两个部分都不会啊
这可怎么办呢
然后在思考半个多小时无果的情况下我打开了题解
看了快俩小时才看懂那是什么……
大概的推导过程是这样的：
首先我们考虑两个被有向边链接的点$u$和$v$，设其大小为$s_{u}$和$s_{v}$，定义$g=gcd(s_{u},s_{v})$
那么如果$i \% g == j \% g$，那么i和j之间应该有边，即“如果i有金块，那么i会给j一个假金块”
这样的贡献是很显然的。那么我们来考虑复杂一点的情况：如果有链$u->v->w$，现在我们考虑$u$对$w$的贡献。
图中定义$g=gcd(s_{u},s_{v})$：
我先解释一下新出现的f是啥：
我们定义$f(v,g)$为一个假想帮派，其大小为$g$，并且满足如果帮派$v$中第$i$个人有金块，那么$f(v,g)$中第$i\%g$个人就有金块
这样的话，由于u对w的贡献应该体现在“u使v出现了v自己没有的金块，然后v又把这个金块给了w”
那么我们$u$对$w$的贡献就可以体现为一个$f(u,gcd(s_{u},s_{v}))$对$w$的贡献
这样也不难理解……因为如果v用从u那里拿到的金块去贡献w，那贡献的单元一定是$f(u,gcd(s_{u},s_{v}))$
那么我们推广一下：假如有一条链$w_{1}->w_{2}->......->w_{n}$,
那么$w_{1}$对$w_{n}$的贡献应该可以体现为$f(w_{1},gcd(s_{w_{1}},s_{w_{2}},.....s_{w_{n-1}}))$
但是原图并不保证是个$DAG$，所以我们考虑，如果有一个闭合回路$v->w_{1}->w_{2}->......->w_{n}->v$,
那么$v$对自己的贡献是什么呢？
类比上面的做法，应该可以体现为$f(v,gcd(s_{v},s_{w_{1}},s_{w_{2}},.....s_{w_{n}}))$
那么我们现在可以处理环内部的贡献了，那么我们考虑把环缩成点，考虑整体对其他联通块的贡献
结合刚才我们的定义，现在我们应该有一个对于某个环定义的$h(S,g)$，
依然是大小为g的帮派，但是现在只要强连通分量S中有某一个元素$w_{i}$中存在i有金块，那么h中$i\%g$就有一个金块
在定义了h之后，我们计算环中的答案也容易了：对于$S$中帮派v，如果$h(S,g)$中第i个有金块，那么所有$v_{j}(j\%g==i)$都会有金块，
因为环上每个点也会被这个环所有点进行贡献
再考虑$SCC$之间的贡献：我们缩完点之后，原图变成了$DAG$完全图
那么这样的图里面一个存在一条哈密顿路径，即经过所有点的路径。这是很显然的。
那么我们按拓扑序遍历这个路径，每次用前面一个$SCC$的$h$去贡献后面一个$SCC$的$h$
这样我们就得到了最后的每个$h$，再按刚才说的方法统计就可以求出每个帮派最多有多少金块了
那么对于每个帮派，我们现在得到了它最少&最多可以卖出多少金块，分别定义为$mn$和$mx$
然后考虑统计答案，我们枚举每个帮派$v$作为被逮捕的$b$个帮派中实力最小的进行统计，
首先值得注意的是，我们这时候固定每个帮派的实力就是它能卖出的最多的金块
因为如果对于某种前a个的方案中，有的帮派没有卖出$mx$个，那么我们可以把他们换成卖出$mx$个，这样a集合是不变的。
所以我们就钦定帮派们都卖出了mx个
那么我们考虑另外一个帮派$u$，如果……
$mn_{u}>mx_{v}$，那么u一定实力比v大，设这样的一共有c1个帮派
$mx_{u}>mx_{v}$，那么u可能实力比v大，设这样的一共有c2个帮派（这里，当$mx$相等的时候，我们按照编号大小比较，这样就不重不漏了）
所以我们枚举有几个可能比v实力大的帮派最后被选中，设个数为$j$
那么对答案的贡献就是$C(c2,j)*C(c1,b-1-j)$
我们只要限制好枚举边界($j<b,j<=c2,j+c1<a$)就可以统计答案了
这样我们就解决了这道神题！
这题给我的触动是不小的……
第一部分推导的思路非常清晰，从简单情况发现规律，辅助变量$f$和$h$的引入，一条边到链到环的推导……这样的推导真的让人感觉非常畅快。
还有第二部分的统计答案，巧妙的枚举了实力最小的帮派，使得统计变得轻松。
这题目真的是666啊……
最后附上code：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define RG register
#define N 5010
#define mod 1000000007
#define LL long long
#define min(x,y) ((x)<(y)?(x):(y))
char B[<<],*S=B,*T=B;
#define getc (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
inline int read()
{
RG int x=;RG char c=getc;
while(c<''|c>'')c=getc;
while(c>=''&c<='')x=*x+(c^),c=getc;
return x;
}
inline int get01()
{
RG char c=getc;
while(c<''|c>'')c=getc;
return c^;
}
int n,a,b,ge[N],e,adj[N];
vector<int>mem[N],con[N],can[N];
struct edge{int zhong,next;}s[N*N>>];
inline void add(int qi,int zhong)
{s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}
int dfn[N],low[N],num,sta[N],top;
int sz[N],belong[N],tot,mn[N],mx[N],C[N][N];
inline int gcd(int a,int b){return b==?a:gcd(b,a%b);}
#define vi vector<int>::iterator
inline void tarjan(int rt)
{
RG int i,u;
dfn[rt]=low[rt]=++num;sta[++top]=rt;
for(i=adj[rt];i;i=s[i].next)
if(!dfn[u=s[i].zhong])tarjan(u),low[rt]=min(low[rt],low[u]);
else if(!belong[u])low[rt]=min(low[rt],dfn[u]);
if(dfn[rt]==low[rt])
{
++tot;
do belong[u=sta[top--]]=tot,sz[tot]=gcd(sz[tot],ge[u]),con[tot].push_back(u);while(u!=rt);
can[tot].resize(sz[tot]);
for(vi it=con[tot].begin();it!=con[tot].end();++it)
for(vi j=mem[*it].begin();j!=mem[*it].end();++j)
can[tot][*j % sz[tot]]=;
}
}
int main()
{
// freopen("Ark.in","r",stdin);
RG int i,j,x,ans=,cnt1,cnt2;
n=read();a=read();b=read();
for(i=;i<=n;++i)for(j=;j<=n;++j)if(get01())add(i,j);
for(i=;i<=n;++i)
for(ge[i]=read(),j=;j<ge[i];++j)
if(get01())++mn[i],mem[i].push_back(j);
for(i=;i<=n;++i)if(!dfn[i])tarjan(i);
for(i=tot;i>;--i)
for(sz[i-]=gcd(sz[i],sz[i-]),j=;j<sz[i];++j)
if(can[i][j])can[i-][ j % sz[i-] ]=;
for(i=;i<=n;++i)
for(x=belong[i],j=;j<ge[i];++j)
mx[i]+=can[x][j%sz[x]];
for(C[][]=i=;i<=n;++i)
for(C[i][]=j=;j<=i;++j)
C[i][j]=(C[i-][j]+C[i-][j-])%mod;
for(i=;i<=n;++i)
{
for(cnt1=,j=;j<=n;++j)if(mn[j]>mx[i])++cnt1;
if(cnt1>=a)continue;
for(cnt2=,j=;j<=n;++j)
if(mn[j]<=mx[i]&&(mx[j]>mx[i]||(mx[j]==mx[i]&&j>i)))++cnt2;
for(j=min(b-,min(cnt2,a-cnt1-));j>=;--j)
ans=(ans+(LL)C[cnt2][j]*C[cnt1][b--j])%mod;
}
printf("%d\n",ans);
}
codeforces804F
十二，总结
其实还有很多很棒的题目没有来得及写详细的题解
但是……接下来还要去盐焗其他知识，没有时间了，就凉凉了……
在这里做个小总结……
dp问题大概分为两类，计数和最优化，没了:)
写一些零散的思路吧
dp我们首先要有个状态
怎么设计状态是困扰广大OIER的千古难题
所以我也不会23333
不过一般来说，我们dp要找一些关键的量进行限制
一般限制的这些量会对结果产生影响……之类的
比如很多序列上的问题定义“最后一个在i”等等
我记得之前看见过一句很好的话：
“对于很多构造题和dp题，不妨先想想最优解是什么样子的，看看它有什么特征，再考虑如何设计状态&转移”
计数题的最大套路就是容斥了……
感觉容斥原理的应用可以“以时间换思考难度”，
使得本来根本没法处理的限制变得可做
同时，容斥原理在很多题目中还是正确性的保证
比如：
uoj193的环套树计数我们要枚举叶子，
但是可能剩下的点在有的联边情况下也变成了叶子，于是要容斥
uoj37的DAG计数同理，
枚举入度为0的点之后我们也不知道剩下的点里面有没有入度为0的点，于是要容斥
与容斥相对的处理方法就是考虑“计数如何不重不漏”了
这个就要用心考察每一个变量，看看枚举什么可以区分每一种状态了……
很难说这个东西具体怎么用，但是我感觉在做了上面两个uoj之后有一点点容斥的手感了
对于所有题目都可能适用的方法：正难则反（或者叫补集转换？）
第一次具体意识到“正难则反”是看到clj老师的计数pdf的时候
那些题目真的把我碾爆了QAQ
有的时候，如果我们正着处理合法(不合法)不好处理，而总状态很好计算，
我们就可以思考反过来处理不合法(合法)状态能不能行，然后就没准能做了
比较经典的是uoj37，这个题从正着dp“对于某个点集，其诱导子图的SCC数量”转换成了反着dp缩点之后DAG的方案数
还有昨天看的wc2007石头剪刀布，不直接统计三元环而是反过来统计$C(n,3)-cnt$(不是三元环)
对于所有题目都可能适用的方法：模型转换
这个就更加玄乎了
一般是从原本的问题，寻找其等价问题进行处理，从而简化问题
大多数时候，我们根本不知道如何模型转换
但是就算是咸鱼我们也要赌一赌国运
联想一下题目中的某些条件能不能换成别的等价的问题然后处理
我印象中最典型的就是权值转计数类问题了
我们给予题设权值一个实际意义，然后就把难处理的权值转成了计数问题
比如有一次模拟赛，权值是“len×cnt1”，我们就计数“任选一个染绿，再任选一个1染红（可重复染色），那么方案数就是len×cnt1
还有一次是权值是数量的平方，于是我们转换成二元组计数，维护两个独立的状态，
他们可以分别转移，最后答案就是平方后的结果
还有uoj193，这个权值定义是“环套树非叶子节点个数”，
我们就计数“每个点可以染黑白两种颜色，叶子只能染白”的数量，
然后正难则反枚举黑叶子集合容斥
这种转换似乎很常见的……但是该想不出来还想不出来
网格图利器：插头dp（轮廓线）
很多时候一个轮廓线干上去我们就会发现转移特别舒服
个人感觉常用于“需要决策每个格子放什么”的问题
不一定只用于传统的逐格转移
我们可以维护已选集合的轮廓（HEOI2018D1T1），也可以按行转移
总之网格图上轮廓线还是有前途的233
期望概率怎么做？
首先一个抓手就是期望的线性性
比如，很多题目都定义“在第i轮还没有结束的概率”，
然后利用期望的线性性加起来这就是期望轮数
还有一个就是积分的应用
以及前后缀不一定用于优化dp，状态定义里使用前后缀也许可以写出方便转移的式子
这次没做到期望概率的题目，还需要加强啊……
有一个很清真的想法就是“对于任何东西都可以定义函数”
不一定dp只能对下标定义啊……
比如我可以对于一张图定义一个函数，然后这个函数能够转移之类的
也就是说，我把所有东西都看成元素，这样也许能找到元素之间的关系来转移
数据范围极小怎么办？
我们还是别想爆搜了233333
那么我们一般考虑状压
状压的好帮手就是容斥(子集反演)啦
最近发现了状压的新套路
比如，当状态集合有2个，但是我们能发现包含关系的时候，可以压成3进制来做/直接哈希表硬上
以及一些小科技：fwt；枚举子集；用lowbit枚举所有的1而不是直接枚举判断是不是1
差分的应用也是特别6的
从原来的序列转换成维护差分数组，可能大大减少可能状态/维护难度
比如说单调的前后缀最值，以及一些单调不降的数组，我们可以用其差分值代表原序列
很大的可能就是变成了01然后可以状压了
权值范围很小，还和二进制有关？按位考虑也许是个好方法
数学(gcd，根号相关)dp题？想跟根号有关的性质，找到突破口
如果题设目标是对环上东西的一个DP，有一种可能的状态定义是
“对于一段圆弧(把环拆成链)，其两端的状态分别是xx和yy的计数/最优解”
第一次见到这种想法是在cf848e上
今天听wq讲了bzoj3746加深了一点点印象
但是感觉如果遇到题还是可能想不起来啊……
这其实就把原来环上的问题简化为序列了，就可以用类区间dp的方法dp了
优化方法：改变数组定义
改变数组定义……看命了，能不能想出来的确是智商的问题
优化方法：辅助数组/预处理
有的时候我们会觉得dp细节很多，手动讨论很烦？
曾经我见过的一个不错的方法就是写4个calc函数然后来回来去的调用
这样的话代码非常简洁，并且思路也很清晰
我觉得个人的一大缺点就是太喜欢手动讨论了
这样的话代码会很长，细节也更多更不容易调试
所以……要多试着改变这一点
优化方法；决策单调性（单调队列/栈，四边形不等式）
这个方法似乎我分配的科技点比较少23333
太玄了，也说不好什么就一定能用，什么就一定不能用
需要我们观察转移方程，有单调性就能用呗……
优化方法：log((cdq)分治，(wqs)二分/三分)
其实二分三分算是决策单调性？
这样一般可以把原本的$n^{2}$变成$nlogn$，非常优秀
upd:2018-4-17
今天考试的T1(loj6032)非常不错
提示我们还有一种可行的模型转化方法是建立分治结构/重构树
我能想到的应用是克鲁斯卡尔重构树，最小割树，以及多点最短路
比如这个dp，就是把原来的序列建成重构树，
利用“建出来的区间两侧隔板高度都比它高，不用考虑边界”这一优秀性质来dp
同时wq想到的处理方法也是非常不错的：把条件和隔板一起排序，
直接找到每个条件对应在哪个节点被利用
优化方法；矩阵乘法(自动机)/倍增/特征多项式
如果我们发现dp过程和当前位置i没有什么关系，即每一步的转移都是类似的
那么我们可以考虑用上面的方式来加速转移
优化方法；前后缀和，卷积
这个有时候可以通过化简/变形dp转移方程发现特定形式，从而发现优化方法
优化方法：数据结构
打着打着就发现从dp题变成了数据结构题23333
不过有的时候用数据结构的确可以从枚举转移变成直接查询转移，优化复杂度
大概用于“用来转移的状态处于一个连续区间”的时候
十三，题表
按推荐等级排序~(level大的更加666)
$Level 6$ 共11题 强力推荐
uoj37 uoj193 uoj316 uoj372
bzoj3746 codechef_SEPT11_CNTHEX
cf804F cf855G cf923G cf865E
TopCoder_SRM_641_Hard(有兴趣可以考虑一下加强版问题:n<=1e5)
$Level 5$ 共11题
cf848e cf814E cf938F bzoj3326
uoj141 uoj348 loj553 bzoj1435
Topcoder_SRM_639_Div1_Level2
Topcoder_SRM_547_Div1_Level3
bzoj4871
$Level 4$ 共13题
loj2330 loj2331 bzoj4712 bzoj4513
cf903F cf814D cf755G cf379G uoj370
cf917C cf917D cf722E cf590D
$Level 3$ 共5题
loj2325 uoj129 uoj110 uoj300
uoj139 hihoCoder_challenge_19A/1279
$Level 2$ 共1题
loj6301
$Level 1$ 共1题
cf814C
$Unrated$
(我没有做也没有想所以没办法评级咯……)
hdu4809 51nod1684 loj2450 bzoj3830
bzoj3711 bzoj3717 bzoj2216 bzoj2091
bzoj3831 hdu5513 loj6274 uoj140
cf773f uoj11 cf468e bzoj4036
bzoj4557 bzoj4859 bzoj4818 loj520
loj2321 loj2324 loj2180 loj2255
loj530 loj515
final update：2018-4-17 16:08:31