haoi2018

题解：

题目相对其他省难一点

不过弱省省选知识点都这么集中的么。。

4道数学题。。。

1.[HAOI2018]奇怪的背包

这题考场做就gg了。。。

其实我想到了那个性质。。 就是这个一定要是gcd的倍数

但是我傻逼的觉得这个不对。。 因为xi都要>=0

然后就看题解。。

仔细想了一下 这可是模意义下啊？？

你要是负数你一直加p答案不是不变的么。。。

然后有了这个性质我们考虑dp

直接$f[i][j]$表示考虑了前i个数，gcd为j这个复杂度比较gg

我们发现j一定是p的因数，所以离散化一下（hash表查找）

设p的因数个数为M

这个复杂度是$nMlogn$的 还是gg。。。

我们再看一看 每次加入一个数实际上是与它取gcd

而gcd一定也是y的因数 所以刚开始本质不同的数只有M种

对于相同的数，不取就一种方案，取就是$(2^k-1)$

然后这样dp就是$M^2logM$

讲道理M的上限是sqrt的。。（不知道差了多少倍 程序要跑太久。。）

但反正是能过了。。

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define mid ((h+t)>>1)
using namespace std;
const int INF=1e9;
namespace IO{
    char ss[<<],*A=ss,*B=ss;
    IL char gc()
    {
        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
    }
    template<class T>void read(T &x)
    {
        rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
    }
    char sr[<<],z[]; int Z,C=-;
    template<class T>void wer(T x)
    {
        if (x<) sr[++C]='-',x=-x;
        while (z[++Z]=x%+,x/=);
        while (sr[++C]=z[Z],--Z);
    }
    IL void wer1()
    {
        sr[++C]=' ';
    }
    IL void wer2()
    {
        sr[++C]='\n';
    }
    template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}
    template<class T>IL void mina(T &x,T y) {if (x>y) x=y;}
    template<class T>IL T MAX(T x,T y) {return x>y?x:y;}
    template<class T>IL T MIN(T x,T y) {return x<y?x:y;}
};
using namespace IO;
const int mo=5e6+;
struct Hash{
    int H[mo+],H1[mo+];
    IL void push(int x,int z)
    {
        int y=x%mo;
        while (H[y]!=&&H[y]!=x) ++y;
        H[y]=x; H1[y]=z;
    }
    IL int query(int x)
    {
        int y=x%mo;
        while (H[y]!=&&H[y]!=x) ++y;
        return H1[y];
    }
}H;
const int N=1e6+1e5;
const int M=3.5e4+;
int a[N],f[N],pp[M];
int g[][M],now[M],now2[M],o[N];
int gcd(int x,int y)
{
    return (!y)?x:gcd(y,x%y);
}
const int mo2=1e9+;
IL void js(register int &x,register int y)
{
    x+y>mo2?x=x+y-mo2:x=x+y;
}
int main()
{
    int n,q,p;
    read(n); read(q); read(p);
    rep(i,,n) read(a[i]);
    int k=sqrt(p);
    int cnt=;
    rep(i,,k)
      if (p%i==) f[++cnt]=i;
    k=cnt;
    dep(i,k,)
      if (p!=f[i]*f[i]) f[++cnt]=p/f[i];
    rep(i,,cnt) H.push(f[i],i);
    rep(i,,n) pp[H.query(gcd(a[i],p))]++;
    o[]=;
    rep(i,,) o[i]=o[i-]*%mo2;
    rep(i,,) o[i]=((o[i]-)%mo2+mo2)%mo2;
    g[][cnt]=;
    rep(i,,cnt)
    {
      int *g1=g[i%],*g2=g[(i+)%];
      memset(g[(i+)%],,sizeof(g[][])*(cnt+));
      if (pp[i])
      rep(j,,cnt)
        if (g1[j])
        {
            js(g2[H.query(gcd(f[i],f[j]))],(1ll*g1[j]*o[pp[i]])%mo2);
        }
      rep(j,,cnt) js(g2[j],g1[j]);
    }
    memcpy(now,g[(cnt+)%],sizeof(g[(cnt+)%]));
    rep(i,,cnt)
    {
      int w=p/f[i];
      int k=sqrt(w);
      rep(j,,k)
        if (w%j==)
        {
            int t=H.query(f[i]*j);
            if (t) js(now2[t],now[i]);
            if (j*j!=w)
            {
                t=H.query(f[i]*w/j);
                if (t) js(now2[t],now[i]);
            }
        }
    }
    rep(i,,q)
    {
        int x; read(x);
        x=H.query(gcd(x,p));
        wer(now2[x]); wer2();
    }
    fwrite(sr,,C+,stdout);
    return ;
}

2.[HAOI2018]反色游戏

这个感觉思路其实不难 但好像并没有往这上面想

第一感觉就是这个可以化成xor然后线性基高斯消元

最后线性基中为0的点就可以任取 答案为2^k 注意还要判断合不合法 不合法直接为0

然后发现就算没有多次询问就一组也过不了？？？

然后我就觉得应该是有个黑科技我没学过。。。。

先说一下部分分。。

50分暴力高斯消元就可以了 （$n^4$）

60分需要bitset优化($n^4/32$)

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
const int N=;
const int mo=1e9+;
int T,n,m;
struct re{
  int a,b;
};
vector<re> ve[N];
char c[N];
bitset<N> B[N],now;
int ans[N],f[N],g[];
bool cmp(int x,int y)
{
  return x>y;
}
int main()
{
  ios::sync_with_stdio(false);
  g[]=;
  rep(i,,) g[i]=(g[i-]*)%mo;
  cin>>T;
  rep(ttt,,T)
  {
    cin>>n>>m;
    rep(i,,n) ve[i].clear();
    rep(i,,m)
    {
      int x,y;
      cin>>x>>y;
      ve[x].push_back((re){i,y}); ve[y].push_back((re){i,x});
    }
    cin>>c;
    rep(i,,n-) f[i+]=c[i]-'';
    rep(i,,n)
    {
      bool tt=;
      int c3=;
      rep(j,,n)
        for (int k=;k<ve[j].size();k++)
          if (j==i||ve[j][k].b==i) c3++;
      c3/=;
      rep(j,,m) B[j]=,ans[j]=;
      rep(j,,n)
      if (j!=i)
      {
        now=; int ans2=f[j];
        for (int k=;k<ve[j].size();k++)
          if (ve[j][k].b!=i) now[ve[j][k].a]=;
        dep(k,m,)
          if (now[k])
          {
            if (B[k]!=)
            {
              now^=B[k],ans2^=ans[k];
              if (now==) break;
            }
            else
            {
              B[k]=now;
              ans[k]=ans2;
              break;
            }
          }
        if (now==&&ans2) tt=;
      }
      int cnt=;
      rep(j,,m) if (B[j]==) cnt++;
      cnt-=c3;
      if (!tt) cout<<<<" ";
      else cout<<g[cnt]<<" ";
    }
    cout<<endl;
  }
  return ;
}

70分我不知道是什么东西。。。 我会线段树分治做到（$n^3logn/32$） 但这个常数明显大而且肯定过不了70啊。。

然后考虑一下正解

发现这题要用线性基其实是假的

一条边只能连两个节点啊。。。

所以我们考虑合并

如果合并之前两点已经有关系说明这条边就任意了

于是简化一下要求的就是2^(n-m-联通块个数）

另外怎么判断合不合法的充要条件是 如果黑点数为奇数就不合法

来简单证明一下

必要性：改变的颜色数是边数*2的 黑点为奇数显然不行

充分性：如果改变了偶数个，每次我们就任取两个扩展一条他们之前的连边 如果重复就把边取反就可以了

于是我们要支持删一个点求联通块个数和有无奇数个黑点

分类讨论了

3.

由于后缀数组和后缀自动机有点忘了。。以后再补

day2为啥只有两题。。

4.[HAOI2018]苹果树

我用了跟题解不太一样的方法 当然题解更加简单。。

令$f(i)$表示i个点排成子树的方案数 （我刚开始并没有想到这个是n!）

$f(i)=\sum C(n,i)*f(i)*f(n-i)$

令$g(i)$表示i个点排成子树到根的路径和

$g(i)=\sum$

令$h(i)$表示i个点排成子树内部路径和

$h(i)=\sum$

题解的方法也比较常见

考虑每条边的贡献

#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
namespace IO{
    char ss[<<],*A=ss,*B=ss;
    IL char gc()
    {
        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
    }
    template<class T>void read(T &x)
    {
        rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
    }
    char sr[<<],z[]; int Z,CC=-;
    template<class T>void wer(T x)
    {
        if (x<) sr[++CC]='-',x=-x;
        while (z[++Z]=x%+,x/=);
        while (sr[++CC]=z[Z],--Z);
    }
    IL void wer1()
    {
        sr[++CC]=' ';
    }
    IL void wer2()
    {
        sr[++CC]='\n';
    }
    template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}
    template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}
    template<class T>IL T MIN(T x,T y){return x<y?x:y;}
    template<class T>IL T MAX(T x,T y){return x>y?x:y;}
};
using namespace IO;
const int N=;
int nn,mo;
int C[N][N],f[N],g[N],h[N];
IL void js(int &x,int y)
{
    x=x+y>mo?x+y-mo:x+y;
}
int main()
{
    read(nn); read(mo);
    int m=;
    rep(i,,m)
    {
      C[i][]=C[i][i]=;
      rep(j,,i-)
        C[i][j]=(C[i-][j-]+C[i-][j])%mo;
    }
    f[]=f[]=;
    rep(i,,nn)
    {
      int n=i-;
      rep(j,,n)
        js(f[i],1ll*f[j]*f[n-j]%mo*C[n][j]%mo);
      rep(j,,n)
        js(g[i],2ll*g[j]%mo*C[n][j]%mo*f[n-j]%mo);
      js(g[i],1ll*f[i]*n%mo);
      rep(j,,n)
        js(h[i],2ll*h[j]%mo*C[n][j]%mo*f[n-j]%mo);
      rep(j,,n)
        js(h[i],(2ll*j%mo*(n-j)%mo*f[j]%mo*f[n-j]%mo+2ll*g[j]%mo*(n-j)%mo*f[n-j]%mo)%mo*C[n][j]%mo);
      js(h[i],g[i]);
    }
 //   rep(i,1,nn) cout<<f[i]<<" "<<g[i]<<" "<<h[i]<<endl;
    cout<<h[nn]<<endl;
    return ;
}

5.[HAOI2018]染色

这个题型比较经典

首先我们考虑取出k个正好有s的

$C(n,s)*C(n-s,s)*...*C(n-k,s) $然后这个可以化简一下

然后因为这个已经保证了顺序 颜色只需要$C(m,k)$就行了（不是$A(s,k)$）

令$F(n,m)$表示n个点用m种颜色染，没有为k的方案数

这个比较显然可以容斥来做 式子太长不想写。。。

列出式子再带进去

我的ntt方法好像和网上不太一样

$ans=f(i)*\sum{g(j)*h(i+j)}$

然后我们变换一下 令$p(i)=h(t-i)$

这样就是卷积形式了

写代码的时候正推预处理了1e7的inv

然后发现这个跑的贼慢。。直接exgcd算比这个快多了

有一个常数更小的方法是先计算$(n!)$的逆元然后再倒推回去

这样就不需要除法和取模了

好久没打ntt。。

ntt的n 应该是算出结果的最高项次数

刚开始没算0的情况

这种题目基本最简单的数据对了就对了

所以可以自己造比较好手模的数据

代码：

#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for(int i=h;i<=t;i++)
#define dep(i,t,h) for(int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
namespace IO{
    char ss[<<],*A=ss,*B=ss;
    IL char gc()
    {
        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
    }
    template<class T> void read(T &x)
    {
        rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
    }
    char sr[<<],z[]; int Z,C=-;
    template<class T>void wer(T x)
    {
        if (x<) sr[++C]='-',x=-x;
        while (z[++Z]=x%+,x/=);
        while (sr[++C]=z[Z],--Z);
    }
    IL void wer1()
    {
        sr[++C]=' ';
    }
    IL void wer2()
    {
        sr[++C]='\n';
    }
    template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}
    template<class T>IL void mina(T &x,T y) {if (x>y) x=y;}
    template<class T>IL T MAX(T x,T y){return x>y?x:y;}
    template<class T>IL T MIN(T x,T y){return x<y?x:y;}
};
using namespace IO;
const int mo=;
const int N=1e6+;
const int M=1e6;
const int N1=1e7+;
const int N2=1e7;
int ww[N1],inv[N1],jc[N1],jc2[N1];
int cj[N],nicj[N];
int f[N],g[N],h[N];
void gcd(int x,int y,int &a,int &b)
{
    if (!y)
    {
        a=; b=; return;
    }
    gcd(y,x%y,b,a);
    b-=a*(x/y);
}
int ksm(int x,int y)
{
    if (y==) return();
    if (y==) return(x);
    int k=ksm(x,y/);
    k=(1ll*k*k)%mo;
    if (y&) k=(1ll*k*x)%mo;
    return k;
}
IL void js(register int &x,register int y)
{
    x=x+y>=mo?x+y-mo:x+y;
}
int l,n1,r[N],w[N],x[N],y[N],G=;
void ntt(int *a,int o)
{
    //n n1别写错
    for (int i=;i<n1;i++)
      if (i>r[i]) swap(a[i],a[r[i]]);
    for (int i=;i<n1;i*=)
    {
        int    wn=ksm(G,(mo-)/(i*)); w[]=;
        rep(j,,i-) w[j]=(1ll*w[j-]*wn)%mo;
        for(int j=;j<n1;j+=(i*))
        {
            rint *x=a+j,*y=a+i+j;
            for (rint k=;k<i;k++)
            {
                int t=1ll*w[k]*y[k]%mo;
                y[k]=x[k]-t<?x[k]-t+mo:x[k]-t;
                x[k]=x[k]+t>mo?x[k]+t-mo:x[k]+t;
            }
        }
    }
    if (o==-)
    {
        reverse(&a[],&a[n1]);
        for (int i=,inv=ksm(n1,mo-);i<n1;i++)
          a[i]=1ll*a[i]*inv%mo;
    }
}
int t;
void query()
{
    l=;
    for (n1=;n1<=t*;n1<<=) l++;
    for (int i=;i<n1;i++) r[i]=(r[i/]/)|((i&)<<(l-));
    ntt(f,); ntt(g,);
    for (int i=;i<n1;i++) f[i]=(1ll*f[i]*g[i])%mo;
    ntt(f,-);
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    int n,m,s;
    read(n); read(m); read(s);
    rep(i,,m) read(ww[i]);
    inv[]=;
    rep(i,,N2) inv[i]=(-1ll*(mo/i)*inv[mo%i]%mo+mo)%mo;
    jc2[]=; jc[]=; cj[]=; nicj[]=;
    rep(i,,N2) jc[i]=1ll*jc[i-]*i%mo,jc2[i]=1ll*jc2[i-]*inv[i]%mo;
    int x,y;
    gcd(jc[s],mo,x,y);
    x=(x+mo)%mo;
    rep(i,,M)
    {
      cj[i]=1ll*cj[i-]*jc[s]%mo;
      nicj[i]=1ll*nicj[i-]*x%mo;
    }
    t=MIN(m,n/s);
    rep(i,,t)
      if (i%==)
        f[i]=1ll*nicj[i]*jc2[i]%mo;
      else f[i]=(-1ll*nicj[i]*jc2[i]%mo+mo)%mo;
    rep(i,,t)
      g[i]=1ll*ksm((m-i),n-i*s)*jc2[n-i*s]%mo*jc2[m-i]%mo;
    reverse(g,g+t+);
    query();
    rep(i,,t) h[i]=(f[t-i]+mo)%mo;
/*    rep(i,0,t)
      rep(j,i,t)
        js(h[j-i],1ll*f[i]*g[j]%mo); */
    int ans=;
    rep(i,,t)
    {
        int t1=1ll*ww[i]*jc[n]%mo*nicj[i]%mo*jc[m]%mo*jc2[i]%mo;
        t1=1ll*t1*h[i]%mo;
        js(ans,t1);
    }
    cout<<ans<<endl;
    return ;
}