Dylan's Blog
0%

Posted on Edited on In

2月10日 Yahoo Programming Contest 2019 题目链接：https://atcoder.jp/contests/yahoo-procon2019-qual

D - Ears

思路： 我们可以将 Snuke 走过的路抽象成这五个部分： 无论 Snuke 怎么走都会符合这个模型，只是可能有一些部分不会出现。如果发现了这个，后面只要直接 DP 就可以了。设 $f[i][j]$ 为第 $i$ 个位置属于第 $j$ 个部分的代价，转移时加上每个部分相应的代价即可。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define P 
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, a[MAXN];
LL ans=1e18, f[MAXN][5];

LL cost(int x, int op)
{
    if(op==0 || op==4) return x;
    if(op==1 || op==3)
    {
        if(!x) return 2;
        else return x&1;
    }
    if(op==2)
    {
        if(!x) return 1;
        else return !(x&1);
    }
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[i]);
    memset(f, 0x3f, sizeof(f));
    for(rint i=0; i<=4; ++i) f[0][i]=0;
    for(rint i=1; i<=n; ++i)
        for(rint j=0; j<=4; ++j)
        {
            if(j) f[i][j]=min(f[i][j], f[i][j-1]);
            f[i][j]=min(f[i][j], f[i-1][j]+cost(a[i], j));
        }
    for(rint i=0; i<=4; ++i) ans=min(ans, f[n][i]);
    printf("%lld\n", ans);
}

E - Odd Subrectangles

思路： 如果行的集合已知，有一个很巧妙的性质：如果这些行的 $m$ 位的异或和不全为 $0$，那么有 $2^{m-1}$ 个列的集合满足题目要求；否则不会有列的集合满足要求。

因此答案就变成了有多少个行的集合它们 $m$ 位的异或和不全为 $0$，这个东西和线性基的大小有关。设线性基的大小为 $siz$，那么不在线性基中 $n-r$ 个行构成的集合中的所有子集，线性基中都有唯一的集合和该子集异或和全为 $0$，因此答案就是 $2^{m-1}*(2^n-2^{n-siz})$。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 305
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, siz, a[MAXN][MAXN], bas[MAXN][MAXN], temp[MAXN], vis[MAXN];

int ksm(int x, int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=1LL*ans*x%P;
        x=1LL*x*x%P; y>>=1;
    }
    return ans;
}

void insert(int a[])
{
    memcpy(temp, a, sizeof(temp));
    for(rint i=1; i<=m; ++i)
        if(temp[i])
        {
            if(!vis[i])
            {
                for(rint j=1; j<=m; ++j) bas[i][j]=temp[j];
                vis[i]=1;
                siz++;
                break;
            }
            for(rint j=1; j<=m; ++j) temp[j]^=bas[i][j];
        }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; ++i)
        for(rint j=1; j<=m; ++j) scanf("%d", &a[i][j]);
    for(rint i=1; i<=n; ++i) insert(a[i]);
    printf("%d\n", 1LL*(ksm(2, n)-ksm(2, n-siz)+P)*ksm(2, m-1)%P);
}

F - Pass

思路： 有一个性质是第 $i$ 个球一个是从 $1～i$ 中的一个人手上来的。因此对于序列唯一的限制就是序列中前 $i$ 个中红球数量不能超过前 $i$ 个人手中的红球数量，对于黑球也同理，且序列中后 $n$ 球没有任何限制。然后就可以根据这个性质简单 DP 即可。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 2005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, ans, r[MAXN], b[MAXN], c[MAXN*2][MAXN*2], f[MAXN][MAXN];
char s[MAXN];

int main()
{
    scanf("%s", s+1);
    n=strlen(s+1);
    c[0][0]=1;
    for(rint i=1; i<=n*2; ++i)
        for(rint j=0; j<=i*2; ++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    for(rint i=1; i<=n; ++i)
    {
        if(s[i]=='0') r[i]=2;
        if(s[i]=='1') r[i]=b[i]=1;
        if(s[i]=='2') b[i]=2;
        r[i]+=r[i-1], b[i]+=b[i-1];
    }
    f[0][0]=1;
    for(rint i=1; i<=n; ++i)
        for(rint j=max(0, i-b[i]); j<=min(i, r[i]); ++j)
        {
            f[i][j]=(f[i][j]+f[i-1][j])%P;
            if(j) f[i][j]=(f[i][j]+f[i-1][j-1])%P;
        }
    for(rint i=max(0, n-b[n]); i<=min(i, r[n]); ++i) ans=(ans+1LL*c[n][r[n]-i]*f[n][i]%P)%P;
    printf("%d\n", ans);
    return 0;
}

Posted on Edited on In

问题描述

有关系式 $fi = \left(\prod{j = 1}^{k} f{i - j}^{b_j}\right) \bmod p$，$p$ 为 $99844353$，并且设 $f_1 = f_2 = \ldots = f{k - 1} = 1$。题目告诉你 $b_1, b_2, \ldots, b_k$ 及 $f_n$，需要你求出 $f_k$。

输入

第一行一个正整数 $k$

第二行 $k$ 个整数表示 $b_1, b_2, \ldots, b_k$

第三行两个整数 $n, m$ 表示 $f_n=m$

输出

输出一个满足 $1 \leq f_k < p$ 的 $f_k$，如果有多个输出任意一个，如果不存在输出 $-1$

思路

思路不难，比较的套路，综合了很多知识点。

首先想到将系数递推关系写成矩阵的形式，然后利用矩阵快速幂将 $fn$ 写成 $f_n= \left(\prod{i = 1}^{k} f{k-i+1}^{a_i}\right) \bmod p$ 的形式，因为题目设 $f_1 = f_2 = \ldots = f{k - 1} = 1$，所以我们实际上要解一个形如 $x^a \equiv b \mod p$ 的方程。

解这个方程比较的套路。先将上面的方程写成离散对数的形式 $k^{a\log_kx} \equiv k^{\log_kb} \mod p$，再根据欧拉定理得到 $a\log_kx \equiv \log_kb \mod \varphi (p)$。其中 $k$ 应该要为 $p$ 的原根，因为这样 $k^1,k^2,…,k^{\varphi(p)}$ 是模 $\varphi(p)$ 的一个完全剩余系，这样就可以避免出现多个 $\log_kx$ 在模 $p$ 意义下的值相同。后面就很简单了，先用 BSGS 求出 $\log_kb$ 然后用 EXGCD 得到 $\log_kx$，最后用快速幂得出最终答案 $x$ 就好了。

代码

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
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 105
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, x, y, a[MAXN][MAXN], c[MAXN][MAXN], ans[MAXN][MAXN];

map<int, int> mp;

void mul(int a[MAXN][MAXN], int b[MAXN][MAXN])
{
    for(rint i=1; i<=n; ++i)
        for(rint j=1; j<=n; ++j)
        {
            c[i][j]=0;
            for(rint k=1; k<=n; ++k) c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%(p-1);
        }
    memcpy(a, c, sizeof(c));
}

void ksm1(int a[MAXN][MAXN], int y)
{
    for(rint i=1; i<=n; ++i) ans[i][i]=1;
    while(y)
    {
        if(y&1) mul(ans, a);
        mul(a, a); y>>=1;
    }
}

int ksm(int x, int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=1LL*ans*x%p;
        y>>=1; x=1LL*x*x%p;
    }
    return ans;
}

int bsgs(int a, int b)
{
    int siz=sqrt(p)+0.5, base=1;
    int t=b;
    mp[t]=0;
    for(rint i=1; i<=siz; ++i)
    {
        t=1LL*t*a%p;
        mp[t]=i;
        base=1LL*base*a%p;
    }
    t=1;
    for(rint i=1; i<=siz; ++i)
    {
        t=1LL*t*base%p;
        if(mp.count(t))
        {
            int x=i*siz-mp[t];
            return x;
        }
    }
    return -1;
}

int exgcd(int a, int b, LL& x, LL& y)
{
    if(!b)
    {
        x=1, y=0;
        return a;
    }
    int d=exgcd(b, a%b, x, y);
    int temp=x; x=y, y=temp-a/b*y;
    return d;
}

int solve(int a, int b, int c)
{
    LL x, y;
    int d=exgcd(a, b, x, y);
    //printf("%d %d %d %d!!!\n", a, b, c, d);
    if(c%d) return -1;
    x*=c/d;
    return (x%(b/d)+(b/d))%(b/d);
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[1][i]);
    for(rint i=2; i<=n; ++i) a[i][i-1]=1;
    scanf("%d%d", &m, &y);
    ksm1(a, m-n);
    x=solve(ans[1][1], p-1, bsgs(3, y));
    if(x==-1) printf("-1\n");
    else printf("%d\n", ksm(3, x));
    return 0;
}

Posted on Edited on In

问题描述

简单来说就是限制空间，给你一个大小为 $5500$ 的数组，除该数组外不能调用其他储存。

然后有一辆长度为 $n$ 的火车，第 $i$ 节车厢上有编号 $c_i$，你需要按顺序输出每 $k$ 节车厢中的最小编号。

输入 & 输出

因为交互题，内容较多，详细内容见链接 Train Tracking 题面。

思路

我们设 $f_i$ 为 从 $i-k+1$ 到 $i$ 中最小值的下标，对于 $f$ 不难想到用单调队列去优化，但是显然是不能将所有元素加入队列中，这时我们就可以利用分块。我们设 $siz$ 为块的大小，第一遍扫过去时只计算 $f_{x*siz+k}$，这样就只需要把每一个块中的最小值放入队列中，并记录下 $f_{x*siz+k}$ 给第二遍的时候用。

第二遍时我们就需要根据 $f_{x*siz+k}$ 计算出所有的 $f$。我首先可以先忽略掉下标小于 $f_0$ 的元素，然后用一个大小同为 $siz$ 的单调队列维护最前的一段，后面的只需要记录下最小值就行了。如果当前扫到的位置是所在块的最小值，那么就可以先输出这一块之前的答案，并建立新的单调队列。

代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include "grader.h"
/*
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, curcar, curpas, sub[5505], a[1000006];

int get(int id)
{
    return sub[id];
}

void set(int id, int val)
{
    sub[id]=val;
}

void shoutMinimum(int x)
{
    printf("%d\n", x);
}

int getTrainLength()
{
    return n;
}

int getWindowLength()
{
    return k;
}

int getCurrentCarIndex()
{
    return curcar;
}

int getCurrentPassIndex()
{
    return curpas;
}*/

void helpBessie(int val)
{
    int op=getCurrentPassIndex();
    int k=getWindowLength();
    int n=getTrainLength();
    int i=getCurrentCarIndex();
    int siz=1000, QWQ=4400, INF=0x3f3f3f3f;
    if(!op)
    {
        if(i==0) set(0, 0), set(1, -1);
        int head=get(1), tail=get(0);
        if(i%siz==0 || (i>=k && (i-k)%siz==0))
        {
            while(head>=tail && get(2*head+3)>=val) head--;
            head++;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        else
        {
            int headval=get(head*2+3);
            if(val<=headval)
            {
                while(head>=tail && get(2*head+3)>=val) head--;
                head++;
                set(2*head+2, i);
                set(2*head+3, val);
            }
        }
        if(i>=k-1 && (i+1-k)%siz==0)
        {
            while(head>=tail && get(tail*2+2)<=i-k) tail++;
            set(QWQ+(i+1-k)/siz, get(tail*2+2));
        }
        set(0, tail), set(1, head);
    }
    else
    {
        if(i<get(QWQ)) return;
        if(i==get(QWQ))
        {
            set(0, 0), set(1, -1);
            set(QWQ-1, 1);
            set(QWQ-2, INF);
            set(QWQ-3, 0);
        }
        int block=get(QWQ-1), l=get(QWQ-3);
        int head=get(1), tail=get(0);
        if(i-get(QWQ+block-1)<=siz)
        {
            while(head>=tail && get(2*head+3)>=val) head--;
            head++;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        else
        {
            int minnum=get(QWQ-2);
            if(val<minnum) set(QWQ-2, val);
        }
        if(l+k-1==i)
        {
            while(head>=tail && get(tail*2+2)<l) tail++;
            int a=get(QWQ-2), b=get(2*tail+3);
            shoutMinimum(a<b?a:b);
            l++;
        }
        while(siz*block+k-1<n && get(QWQ+block)==i)
        {
            while(l<=siz*block)
            {
                while(head>=tail && get(tail*2+2)<l) tail++;
                int a=get(QWQ-2), b=get(2*tail+3);
                shoutMinimum(a<b?a:b);
                l++;
            }
            block++;
            set(QWQ-2, INF);
            head=tail=0;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        set(QWQ-1, block), set(QWQ-3, l);
        set(0, tail), set(1, head);
    }
}

/*
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; ++i)
    {
        scanf("%d", &a[i]);
        curcar=i, curpas=0;
        helpBessie(a[i]);
    }
    for(int i=0; i<n; ++i)
    {
        curcar=i, curpas=1;
        helpBessie(a[i]);
    }
}*/

Posted on Edited on In

问题描述

我们知道，求任意图的最大独立集是一类 NP 完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。

例如，小 C 常用的一种算法是：

  1. 对于一个 $n$ 个点的无向图，先等概率随机一个 $1$ 到 $n$ 的排列 $p[1\ldots n]$。
  2. 维护答案集合 $S$ ，一开始 $S$ 为空集，之后按照 $i=1\ldots n$ 的顺序，检查 ${p[i]}\cup S$ 是否是一个独立集，如果是的话就令 $S={p[i]}\cup S$。
  3. 最后得到一个独立集 $S$ 作为答案。

小 C 现在想知道，对于给定的一张图，这个算法的正确率，输出答案对 $998244353$ 取模

输入

第一行两个非负整数 $n,m$ 表示给定的图的点数和边数。

接下来 $m$ 行，每行有两个正整数 $(u,v) (u\neq v)$ 描述这张图的一条无向边。

输出

输出正确率，答案对 $998244353$ 取模。

思路

这题比较巧妙的地方就是设计状态。考虑比较朴素的一种方法， $0$ 表示一个点未被选，$1$ 表示一个点选了但没在集合中，$2$ 表示一个点在集合中，这样的状态数就是 $n^3$，我们需要考虑的就是如何优化这种状态。

这里要跳出按照排列的顺序选点这个思维定式。只要选了点 $i$ 加入独立集中，那么与 $i$ 相邻的点在它之后任意时候选都不会产生影响，所以假设有 $s1$ 个点没有考虑，这其中有 $s2$ 个点是与 $i$ 相邻的，那么我们考虑这 $s2$ 个点在排列中的情况数，不难发现这个就是 $A_{s1}^{s2}$。注意我们这里说的是「考虑」而不是选取，也就是说先预先给 $s2$ 个点排好位置，而不是按照排列的顺序依次选了这些点。

所以我们可以这样设计状态，设 $f_{S, i}$ 为考虑了集合 $S$ 且其中独立集大小为 $i$ 的方案数。按照上文提到的考虑方法，可以知道只要是不属于集合 $S$ 的点一定可以加入 $S$ 中的独立集，因为与独立集相邻的点已经在 $S$ 中了。设已经考虑了点集 $S$ ，此时要加入点 $k$，与$k$ 相邻的点集为 $e_k$，还有 $s1$ 个点没有考虑，这其中有 $s2$ 个点是与 $k$ 相邻的，有转移方程

其中 $k\notin S$，$s1=n-|S|-1$，$s2=|e_k\bigcap(e_k\bigcup S)|$。这样转移总复杂度就是 $O(n^22^n)$ 了。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 25
#define MAXM (1<<20)+5
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, e[MAXN], f[MAXM][MAXN], bit[MAXM], fac[MAXN], inv[MAXN];

void init()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(rint i=0; i<(1<<n); ++i) bit[i]=bit[i>>1]+(i&1);
    for(rint i=2; i<=n; ++i) inv[i]=1LL*inv[p%i]*(p-p/i)%p;
    for(rint i=2; i<=n; ++i)
    {
        inv[i]=1LL*inv[i]*inv[i-1]%p;
        fac[i]=1LL*fac[i-1]*i%p;
    }
}

int A(int x, int y)
{
    return 1LL*fac[x]*inv[x-y]%p;
}

int main()
{
    scanf("%d%d", &n, &m);
    init();
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        x--, y--;
        e[x]|=(1<<y);
        e[y]|=(1<<x);
    }
    for(rint i=0; i<n; ++i) e[i]|=(1<<i);
    f[0][0]=1;
    for(rint sta=0; sta<(1<<n); ++sta)
        for(rint i=0; i<n; ++i)
        {
            if(!f[sta][i]) continue;
            for(rint j=0; j<n; ++j)
                if(!((sta>>j)&1))
                {
                    int nxt=sta|e[j], s1=n-bit[sta]-1, s2=bit[e[j]^(e[j]&sta)]-1;
                    f[nxt][i+1]=(f[nxt][i+1]+1LL*f[sta][i]*A(s1, s2)%p)%p;
                }
        }
    for(rint i=n; i>=0; i--)
        if(f[(1<<n)-1][i])
        {
            printf("%lld\n", 1LL*f[(1<<n)-1][i]*inv[n]%p);
            return 0;
        }
    return 0;
}