牛客挑战赛40

发表于 分类于

自闭了。。。B一直卡在那，赛后把链表改成vector就过了。。。

A

对 $m$ 进行分解以后，变成 $a\sqrt b$ 的形式。

然后变成整数拆分，问 $x_1+x_2+\cdots+x_n=a$ 有多少组本质不同的非负整数解。

那么DP，设 $f_{i,j}$ 表示用了 $i$ 个数，和为 $j$ 的方案数。

$f_{i,j}=f_{i-1,j-1}+f_{i,j-i}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
   y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
   return ans;
}
const int N=1005;
int n,m,sum;
ll f[N][N],ans;
int main()
{
    n=read(); m=read(); sum=1;
    fo(i,2,sqrt(m)+1)
    {
        if(m%(i*i)==0)
        {
            for(;m%(i*i)==0;m/=(i*i)) sum*=i;
        }
    }
    m=sum+n;
    f[0][0]=1;
    fo(i,1,m)
    {
        fo(j,0,i)
            f[i][j]=Add(f[i-1][j-1],f[i-j][j]);
    }
    printf("%d",f[m][n]);
    return 0;
}

B

由于那些数是随机的，跟 GDOI2017 一样，我们将这些数按位拆分成 $4$ 份，每份 $16$ 位。如果异或后不相同的位数小于等于 $3$ 的话，那么至少有一份是相同的。

那么枚举相同的那份，用一个vector将那一份相同的数列出来，然后一一比较是否满足条件。

这样做，每个 vector 的期望长度就是 $\frac{n}{2^{16}}$，每次需要枚举 $4$ 份，每次判断的次数是 $3$ 次，那么期望时间复杂度就是 $O(\frac{n}{2^{16}}\times 12m)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define fi first
#define se second
#define ull unsigned ll
inline ull read()
{
    ull x=0; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
#define CASET fo(___,1,read())
inline bool check(ull x)
{
    int t=0;
    for(;x;x-=x&-x) if(++t>3) return 0;
    return t<=3;
}
inline ull G(ull x)
{
    x^=(x<<13);
    x^=(x>>7);
    x^=(x<<17);
    return x;
}
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
   y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
   return ans;
}
const int N=1e6+5;
ull a[N];
vector<int> adj[4][1<<17]; 
int ne[N][4];
int n,m;
int main()
{
    srand(20030403);
    n=read(); m=read();
    cin>>a[1];
    fo(i,2,n) a[i]=G(a[i-1]);
    random_shuffle(a+1,a+n+1);
    ull x,k=(1<<16)-1,t;
    fo(i,1,n)
    {
        t=a[i];
        ff(j,0,4)
        {
            adj[j][t&k].pb(i);
            t>>=16;
        }
    }
    ull y,z;
    ll ans=0;
    for(bool flag;m--;)
    {
        scanf("%llu",&y);
        z=y;
        flag=0;
        ff(j,0,4)
        {
            x=y&k;
            for(auto v:adj[j][x])
                if(check(a[v]^z))
                {
                    flag=1; break;
                }
            y>>=16;
            if(flag) break;
        }
        ans=ans+ans+flag;
        if(ans>=mod) ans-=mod;
    }
    printf("%lld",ans%mod);
    return 0;
}

C

对于两个长度为 $n$ 的 01 串，当且仅当 $1$ 的个数相同才能配对。

对 $1$ 的个数作前缀和，记为 $s_i$，那么两个串 $s_1,s_2$ 的贡献就是 $\sum_{i=1}^n|s_{1_i}-s_{2_i}|$。

根据这个就可以进行数位DP了。

设 $f_{i,j,x,y}$ 表示考虑到第 $i$ 位，当前两个串的 $1$ 的个数的差为 $j$，$x,y$ 为这两个串是否一直取最大值。

转移的时候分 $4$ 类讨论。

时间复杂度 $O(n^2)$。有个大常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define Abs(x) ((x)>0?(x):-(x))
const ll mod=998244353;
inline void Add(ll &x,ll y){x+=y; (x<mod)?0:(x-=mod);}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
   y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
   return ans;
}
const int N=1003;
const int M=1000;
ll f[N][N<<1][2][2],g[N][N<<1][2][2],ans;
char s[N];
int n;
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    f[0][M][1][1]=1; g[0][M][1][1]=0;
    int nx,ny;
    ll sg,sf;
    fo(i,1,n)
        fo(j,-i,i)
            fo(x,0,1) fo(y,0,1)
            {
                nx=x?(s[i]-'0'):1; ny=y?(s[i]-'0'):1;
                sg=g[i-1][j+M][x][y],sf=f[i-1][j+M][x][y];
                //0,0
                    Add(g[i][j+M][x&!nx][y&!ny],(sf*Abs(j)+sg)%mod),
                    Add(f[i][j+M][x&!nx][y&!ny],sf);
                //1,0
                if(nx)
                    Add(g[i][j+1+M][x][y&!ny],(sf*Abs(j+1)+sg)%mod),
                    Add(f[i][j+1+M][x][y&!ny],sf);
                //0,1
                if(ny)
                    Add(g[i][j-1+M][x&!nx][y],(sf*Abs(j-1)+sg)%mod),
                    Add(f[i][j-1+M][x&!nx][y],sf);
                //1,1
                if(nx&&ny)
                    Add(g[i][j+M][x][y],(sf*Abs(j)+sg)%mod),
                    Add(f[i][j+M][x][y],sf);
            }
    fo(i,0,1) fo(j,0,1) Add(ans,g[n][M][i][j]);
    printf("%lld",ans*((mod+1)/2)%mod);
    return 0;
}

D

set大力搞，启发式合并就好了。

E

随便暴力一下就好了。