洛谷10月月赛II题解

时间：2022-04-04 22:09:20

咻咻咻

令人窒息的洛谷月赛，即将参加NOIp的我竟然只会一道题（也可以说一道也不会），最终145的我只能惨惨的迎接剩下的16天（吧）

下面是题解的代码（填坑），神奇的是这四道题都需要DP。参加SXOI的大佬真是tql，此处手动@ljt12138@__stdcall

T1找性质，popcnt为1的加上popcnt为0的就是答案（然而当时没想到只打了暴力）

#include<bits/stdc++.h>

typedef long long ll;

ll a, b, c, d, n, x;

int cnt[65536], sz[2];

int main(){

  scanf("%d%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d, &x);

  for(int i = 0; i < 65536; i++) cnt[i] = cnt[i >> 1]^(i&1);

  for(int i = 1; i <= n; i++){

    x = (a*x%d*x%d+b*x%d+c)%d;

    sz[cnt[x & 65535] ^ cnt[x >> 16]]++;

  }

  printf("%lld\n", (long long)sz[0]*sz[1]);

  return 0;

}

T2枚举公差和塔即可

#include<bits/stdc++.h>

const int M = 998244353;

inline int chk(int x){return x >= M? x-M : x;}

int n, max, ans=1, h[1000001];

int d[1001][40001];

int main() {

    scanf("%d", &n);

    for(int i = 1; i <= n; i++) scanf("%d", &h[i]), max = std::max(max, h[i]);

    for(int i = 2; i <= n; i++){

        for(int j = 1; j < i; j++){

            int num = d[j][h[i] - h[j] + 20001]+1;

            d[i][h[i]-h[j]+20001] += num;

            if(d[i][h[i]-h[j]+20001]>=M) d[i][h[i]-h[j]+20001] -= M;

        }

        for(int j = -max+20000; j <= max+20000; j++) ans = chk(ans+d[i][j]);

        ans = chk(ans+1);

    }

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

    return 0;

}

T3是一个DAG上的最长路问题，看懂题解后发现真**简单

#include<bits/stdc++.h>

const int N = 2e6+4;

int n, k, s, f[N]; std::vector<int> ans[21];int a[N];

bool vis[N];

int main(){

  scanf("%d%d", &n, &k); s = (1 << k) -1;

  for(int i = 1; i <= n; i++) scanf("%d", &a[i]), vis[a[i]] = true;

  for(int i = s; i>=0; i--){

    if(vis[i]) f[i]++;

    for(int j = 1; j < s; j <<= 1)

      if(i&j) f[i^j] = std::max(f[i^j], f[i]);

  }

  printf("1\n%d\n", f[0]);

  for(int i = s; i>=0; i--) if(vis[i]) ans[f[i]].push_back(i);

  for(int i = 1; i <= f[0]; i++){

    int size = ans[i].size(); printf("%d ", size);

    for(int j = 0; j < size; j++) printf("%d ", ans[i][j]);

    puts("");

  }

  return 0;

}

T4是一道自始至终都没看懂的数论题，只好先拿租酥雨大佬的代码填填坑

#include<bits/stdc++.h>

const int mod = 1000000007;using std::map; using std::pair;

inline void inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}

inline void dec(int &x,int y){x-=y;x<0?x+=mod:x;}

int fastpow(int a,int b){

    int res=1;

    while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}

    return res;

}

int n,P,R,B,sqr,S,inv[5005],C[505][505],ans;

struct poly{

    int a[505];

    poly(){memset(a,0,sizeof(a));}

    poly operator * (poly b){

        poly c;

        for (int i=0;i<=n;++i)

            for (int j=0;j<=i;++j)

                c.a[i]=(c.a[i]+1ll*a[j]*b.a[i-j]%mod*C[i][j])%mod;

        return c;

    }

}dp[3][2][80],zero;

map<pair<pair<int,int>,int>,int>M;

int calc(int u,int v,int w){

    return (dp[0][0][u%sqr]*dp[0][1][u/sqr]*dp[1][0][v%sqr]*dp[1][1][v/sqr]*dp[2][0][w%sqr]*dp[2][1][w/sqr]*zero).a[n];

}

int main(){

    scanf("%d%d%d", &n, &P, &R);

	B=R/P;while (sqr*sqr<P) ++sqr;

    inv[1]=1;for (int i=2;i<P;++i) inv[i]=inv[P%i]*(P-P/i)%P;

    for (int i=C[0][0]=1;i<=n;++i)

        for (int j=C[i][0]=1;j<=i;++j)

            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

    for (int i=0;i<3;++i){

        dp[i][0][0].a[0]=dp[i][1][0].a[0]=dp[i][0][1].a[0]=1;

        for (int j=1;j<=n;++j) dp[i][0][1].a[j]=(fastpow(B+(i>0),j)+fastpow(B+(i>1),j))%mod;

        for (int j=2;j<=sqr;++j) dp[i][0][j]=dp[i][0][j-1]*dp[i][0][1];

        for (int j=1;j<=sqr;++j) dp[i][1][j]=dp[i][1][j-1]*dp[i][0][sqr];

    }

    for (int i=0;i<=n;++i) zero.a[i]=fastpow(B,i);

    S=fastpow(R,n);inc(ans,S);dec(ans,fastpow(R-B,n));

    for (int i=1;i<P;++i){    int u=0,v=0,w=0;

        for (int j=1;j<P;++j){

            int x=inv[j]*i%P;

            if (x<j){ if (j<=R-B*P) ++w;  else if (x<=R-B*P) ++v;  else ++u;}

        }

        pair<pair<int,int>,int>pr=std::make_pair(std::make_pair(u,v),w);

        if (M.find(pr)==M.end()) M[pr]=calc(u,v,w);

        inc(ans,S);dec(ans,M[pr]);

    }

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

    return 0;

}

总之，这是一场体验极差的比赛。甚至有可能是NOIp的前奏

相关文章