CQOI2018做题记录

T1.破解D-H协议

传送门

这个题就是BSGS的板子题……

然后这里补充一点嘛，就是第二重循环的枚举范围。我们是在枚举\(a^{tm-y}\)，把tm换成i，这个的最大值就是\(i - (m - 1) < c\)，即\(i < c + m - 1\)

#include<bits/stdc++.h>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = 200005;

const int mod = 999979;

int read()

{

    int ans = 0,op = 1;char ch = getchar();

    while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

    while(ch >= '0' && ch <= '9') ans *= 10,ans += ch - '0',ch = getchar();

    return ans * op;

}

int g,P,n,A,B;

struct Hash

{

   int sta[M],top,head[M<<3],ecnt,num[M],val[M],nxt[M];

   void init(){ecnt = 0;while(top) head[sta[top--]] = 0;}

   void insert(int x,int y)

   {

      int h = x % mod;

      for(int i = head[h];i;i = nxt[i]) if(num[i] == x) {val[i] = y;return;}

      if(!head[h]) sta[++top] = h;

      nxt[++ecnt] = head[h],head[h] = ecnt;

      num[ecnt] = x,val[ecnt] = y;

   }

   int query(int x)

   {

      int h = x % mod;

      for(int i = head[h];i;i = nxt[i]) if(num[i] == x) return val[i];

      return -1;

   }

}H;

int mul(int a,int b,int t){return 1ll * a * b % t;}

int qpow(int a,int b,int t)

{

   int p = 1;

   while(b)

   {

      if(b & 1) p = mul(p,a,t);

      a = mul(a,a,t),b >>= 1;

   }

   return p;

}

int gcd(int a,int b){return b ? gcd(b,a%b) : a;}

int exgcd(int a,int b,int &x,int &y)

{

   if(!b){x = 1,y = 0;return a;}

   int d = exgcd(b,a%b,y,x);

   y -= a / b * x;

   return d;

}

int inv(int a,int b)

{

   int x,y;

   exgcd(a,b,x,y);

   return (x % b + b) % b;

}

int BSGS(int a,int b,int c)

{

   int cnt = 0,G,d = 1;

   while((G = gcd(a,c)) != 1)

   {

      if(b % G) return -1;

      cnt++,b /= G,c /= G,d = mul(d,a/G,c);

   }

   b = mul(b,inv(d,c),c);

   H.init();

   int s = sqrt(c),p = 1;

   rep(i,0,s-1)

   {

      if(p == b) return i + cnt;

      H.insert(mul(p,b,c),i),p = mul(p,a,c);

   }

   int q = p,t;

   for(int i = s;i <= c + s - 2;i += s)

   {

      t = H.query(q);

      if(t != -1) return i - t + cnt;

      q = mul(q,p,c);

   }

   return -1;

}

int main()

{

   g = read(),P = read(),n = read();

   rep(i,1,n)

   {

      A = read(),B = read();

      int a = BSGS(g,A,P);

      int b = BSGS(g,B,P);

      printf("%d\n",qpow(g,mul(a,b,P-1),P));

   }

   return 0;

}

T2.社交网络

传送门

这个题是有向图有根树生成树计数，根必须为1.

其实和无向图的生成树计数基本是一样的……就是这次的基尔霍夫矩阵按照有向图来建造。

然后因为根是1，所以我们把矩阵的第一行和第一列删掉，剩下的用高斯消元就可以了。

#include<bits/stdc++.h>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = 255;

const int mod = 1e4+7;

int read()

{

    int ans = 0,op = 1;char ch = getchar();

    while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

    while(ch >= '0' && ch <= '9') ans *= 10,ans += ch - '0',ch = getchar();

    return ans * op;

}

int n,m,x,y,f[M][M];

int inc(int a,int b){return (a + b) % mod;}

int mul(int a,int b){return 1ll * a * b % mod;}

int qpow(int a,int b)

{

   int p = 1;

   while(b)

   {

      if(b & 1) p = mul(p,a);

      a = mul(a,a),b >>= 1;

   }

   return p;

}

int gauss()

{

   int ans = 1;

   rep(i,2,n)

   {

      rep(j,i+1,n) if(f[j][i]) {swap(f[j],f[i]),ans = mod - ans;break;}

      if(!f[i][i]) return 0;

      ans = mul(ans,f[i][i]);

      int inv = qpow(f[i][i],mod-2);

      rep(j,i+1,n)

      {

     int cur = mul(f[j][i],inv);

     rep(k,i,n) f[j][k] = inc(f[j][k],mod - mul(f[i][k],cur));

      }

   }

   return ans;

}

int main()

{

   n = read(),m = read();

   rep(i,1,m) x = read(),y = read(),f[x][x]++,f[x][y]--;

   printf("%d\n",gauss());

   return 0;

}

T3.交错序列

传送门

个人认为是最难的一道了……

\(x^ay^b\)难以处理，于是我们转化为\((n-y)^ay^b\)，那么展开以后就是\(\sum_{i=0}^a(-1)^{a-i}n^iC_a^iy^{a+b-i}\)

于是我们只要求出\(y^i\)的和就可以了。我们可以考虑DP。

用\(dp[i][j][0/1]\)表示当前选取到长度为i，当前位为0/1，当前序列中1的个数的j次方之和。

然后对于0/1变0的情况是没有什么变化的，就是\(dp[i][j][0] += dp[i-1][j][0/1]\)

如果这一位是1的话，根据二项式定理就可以得到\(dp[i][j][1] += \sum_{k=0}^jC_j^kdp[i-1][k][0]\)

于是这个可以用矩阵乘法优化。然后我写完之后还被卡常了……把矩乘内部开成ll，最内一层循环不取模就过了……

最后就按照上面的式子计算答案。

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = 200005;

const int N = 185;

const int mod = 999979;

int read()

{

   int ans = 0,op = 1;char ch = getchar();

   while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

   while(ch >= '0' && ch <= '9') ans *= 10,ans += ch - '0',ch = getchar();

   return ans * op;

}

int n,a,b,m,siz,C[N][N],ans;

int inc(int a,int b){return (a + b) % m;}

int mul(int a,int b){return 1ll * a * b % m;}

struct matrix

{

   ll f[N][N];

   matrix(){memset(f,0,sizeof(f));}

   void init(){rep(i,0,siz-1) f[i][i] = 1;}

   friend matrix operator * (const matrix &a,const matrix &b)

   {

      matrix c;

      rep(i,0,siz-1)

      rep(j,0,siz-1)

      {

	 rep(k,0,siz-1) c.f[i][j] += a.f[i][k] * b.f[k][j];

	 c.f[i][j] %= m;

      }

      return c;

   }

   friend matrix operator ^ (matrix a,int b)

   {

      matrix p;

      p.init();

      while(b)

      {

	 if(b & 1) p = p * a;

	 a = a * a,b >>= 1;

      }

      return p;

   }

}G;

int main()

{

   n = read(),a = read(),b = read(),m = read(),siz = (a+b+1) << 1;

   C[0][0] = 1;

   rep(i,1,a+b)

   {

      C[i][0] = 1;

      rep(j,1,i) C[i][j] = inc(C[i-1][j-1],C[i-1][j]);

   }

   rep(i,0,a+b)

   {

      G.f[i][i] = G.f[i][i+a+b+1] = 1;

      rep(j,0,i) G.f[i+a+b+1][j] = C[i][j];

   }

   G = G ^ n;

   int cur = 1;

   rep(i,0,a)

   {

      int now = ((a - i) & 1) ? -1 : 1;

      ans = inc(ans,mul(mul(cur,C[a][i]),mul(now,inc(G.f[a+b-i][0],G.f[siz-1-i][0]))));

      cur = mul(cur,n);

   }

   printf("%d\n",(ans % m + m) % m);

   return 0;

}

T4.解锁屏幕

传送门

这题挺好玩啊。

但是可以显而易见的看出是状压DP。然后转移也很好想……

\(dp[i][j]\)表示选取集合i，末尾为j的方案数。转移的时候枚举点，按照题中条件判断即可。然后注意在两点连线上的点需要预处理。

然后注意答案要连四个及以上的点，模数是1e8+7。其实很奇怪这玩意复杂度最坏是\(2^nn^2\)的，但是就是过了……

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = 1000005;

const int mod = 1e8+7;

int read()

{

    int ans = 0,op = 1;char ch = getchar();

    while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

    while(ch >= '0' && ch <= '9') ans *= 10,ans += ch - '0',ch = getchar();

    return ans * op;

}

struct dot

{

   double x,y;

}a[25];

int n,G[25][25],dp[1<<20][21],ans;

int inc(int a,int b){return (a+b) % mod;}

double slope(const int &f,const int &g) {return (a[g].y - a[f].y) / (a[g].x - a[f].x);}

bool in(int i,int j,int k)

{

   if((a[k].y >= a[i].y && a[k].y <= a[j].y) || (a[k].y >= a[j].y && a[k].y <= a[i].y))

   {

      if((a[k].x >= a[i].x && a[k].x <= a[j].x) || (a[k].x >= a[j].x && a[k].x <= a[i].x)) return 1;

   }

   return 0;

}

int count(int x)

{

   int cur = 0;

   while(x) cur += x & 1,x >>= 1;

   return cur;

}

int main()

{

   n = read();

   rep(i,0,n-1) scanf("%lf%lf",&a[i].x,&a[i].y),dp[1<<i][i] = 1;

   rep(i,0,n-1)

   rep(j,0,n-1)

   rep(k,0,n-1)

   {

      if(k == i || k == j) continue;

      if(in(i,j,k))

      {

     //printf("%d %d %d\n",i,j,k);

     if(a[k].x == a[i].x && a[k].x == a[j].x) G[i][j] |= (1<<k);

     else if(slope(i,j) == slope(k,j)) G[i][j] |= (1<<k);

      }

   }

   //rep(i,0,n-1)

      //{rep(j,0,n-1) printf("$%d ",G[i][j]);enter;}

   rep(i,1,(1<<n)-1)

   {

      rep(j,0,n-1)

      {

     if(!(i & (1 << j))) continue;

     rep(k,0,n-1)

     {

        if(i & (1<<k)) continue;

        if((i & G[j][k]) != G[j][k]) continue;

        dp[i | (1<<k)][k] = inc(dp[i][j],dp[i | (1<<k)][k]);

     }

      }

   }

   //rep(i,1,(1<<n)-1)

   //{rep(j,0,n-1) printf("#%d ",dp[i][j]);enter;}

   rep(i,1,(1<<n)-1)

   {

      if(count(i) < 4) continue;

      rep(j,0,n-1) if(i & (1 << j)) ans = inc(ans,dp[i][j]);

   }

   printf("%d\n",ans);

   return 0;

}

T5.九连环

传送门

听说这题在数学书上有……？还是必修五？

emm可能是A版……？反正我的B版上没有TAT。

然后通过爆搜通过百度知道，答案就是\(\lfloor\frac{2^n+1}{3}\rfloor\)

然后就写一下FFT就能过…… 不过我太懒了我用了python。代码没有。

T6.异或序列

这个以前写过。看这里

巴特西

CQOI2018做题记录

最新文章

热门文章