Dylan's Blog
0%

Posted on Edited on In

问题描述：

给你一个$h*w$的网格，其中有$n$个黑色的格子，它们的位置为$(x_i, y_i)$。你从左上角开始，每一步只能向左或者下移动，并且不能经过黑色格子，问你有多少种到达右下角的方案。

输入：

第一行给你三个数$h, w, n$（$1<=h, n<=10^5, 1<=n<=200$）

输出：

输出对$10^9+7$取模的方案数

思路：

感觉JXOI很喜欢考计数类DP，然而自己菜的一比。。。

首先我们就是要考虑如何设计一个状态，能够统计DP时的信息，并且能够根据这个状态不重不漏地进行DP（我觉得计数类DP就是这个难，状态转移反而容易一些）。因为黑色格子不多，所以我们的复杂度应该和黑色的格子有关。我们可以先将黑色格子按照横纵坐标排序，然后设$f[i]$为到达$i$个黑色格子且不经过前$i-1$个黑色格子的可能路径数。特别的，设$f[n+1]$的坐标为$(h+1, w+1)$，那么答案就是$f[n+1]$了。

接下来我们考虑如何计算和转移。我们可以先计算出到达第$i$个黑色格子所有路径，这个的数量为$C_{x_i+y_i-2}^{x_i-1}$，原因是一共要向下或向左走$x_i+y_i-2$步，然后其中要任选$x_i-1$步向左走。然后还要减去经过前面黑色格子的路径数，因此我们可以推出DP方程为: 还要特别注意的是如果$x_j>x_i$或者$y_j>y_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
#include <bits/stdc++.h>
#define MAXN 300005
#define p 1000000007
#define LL long long
using namespace std;

int h, w, n;
LL f[MAXN], fac[MAXN], inv[MAXN];

struct Node {int x, y;} a[MAXN];

bool CMP(Node x, Node y)
{
    if(x.x==y.x) return x.y<y.y;
    else return x.x<y.x;
}

LL comb(LL n, LL m)
{
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

void init()
{
    inv[0]=fac[0]=fac[1]=inv[1]=1;
    for(int i=2; i<=MAXN-5; i++)
    {
        fac[i]=(fac[i-1]*i)%p;
        inv[i]=inv[p%i]*(p-p/i)%p;
    }
    for(int i=2; i<=MAXN-5; i++) inv[i]=(inv[i]*inv[i-1])%p;
}

int main()
{
    init();
    scanf("%d%d%d", &h, &w, &n);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    a[n+1].x=h; a[n+1].y=w;
    for(int i=1; i<=n+1; i++)
    {
        f[i]=comb(a[i].x+a[i].y-2, a[i].x-1);
        for(int j=1; j<i; j++)
        {
            if(a[j].x>a[i].x || a[j].y>a[i].y) continue;
            f[i]=(f[i]-f[j]*comb(a[i].x+a[i].y-a[j].x-a[j].y, a[i].x-a[j].x))%p;
        }
    }
    printf("%lld\n", (f[n+1]+p)%p);
}

Posted on Edited on In

问题描述：

在$N*M$的网格中有一个起始位置为$(x, y)$的robot。它每一步会随机的执行四个操作中一个：待在原地，向左，向右，向下（它是不能够移动到网格之外的）。然后问你它移动到第$N$行的步数期望值为多少。

输入：

第一行两个整数$N，M$，表示$N*M$的网格（$1<=n, m<=1000$） 第二行两个整数$x，y$，表示起始位置为$(x, y)$

输出：

输出到第$n$行的期望步数

思路：

这道题中的状态转移方程并不难想到。但是我们发现这些状态会相互影响，并且无法推出其中的任何一个。对于这种期望DP就要用到另一种套路“高斯消元”。

按照套路我们依然从后往前推，第$n$行的所有期望值都为0，我们把这个作为初值向前DP。对于每一行我们都能根据转移方程列出一个方程组，而且我们发现其中的每个方程只有2-3个变量（边界时为两个，其余为3个）。于是我们可以不用普通$O(N^3)$的高斯消元，而是可以YY出一个类似的$O(n)$的消元方法，然后对于每一行都进行一遍这个操作，总复杂度为$O(nm)$。

代码：

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define MAXN 1005
using namespace std;

int n, m, x, y;
double a[MAXN][5], g[MAXN], f[MAXN], w[MAXN];

void guass()
{
    for(int i=1; i<m; i++)
    {
        double rate=a[i+1][0]/a[i][1];
        a[i+1][0]-=a[i][1]*rate;
        a[i+1][1]-=a[i][2]*rate;
        w[i+1]-=w[i]*rate;
    }
    f[m]=w[m]/a[m][1];
    for(int i=m-1; i>=1; i--) f[i]=(w[i]-a[i][2]*f[i+1])/a[i][1];
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for(int i=1; i<=m; i++)
    {
        g[i]=2;
        if(i>1) g[i]++;
        if(i<m) g[i]++;
        g[i]=1.0/g[i];
    }
    for(int i=n-1; i>=x; i--)
    {
        for(int j=1; j<=m; j++)
        {
            if(j!=1) a[j][0]=-g[j];
            a[j][1]=1-g[j];
            if(j!=m) a[j][2]=-g[j];
            w[j]=g[j]*f[j]+1;
        }
        guass();
    }
    printf("%lf\n", f[y]);
}

Posted on Edited on In

问题描述：

对于给定的整数$a，b，d$，有多少正整数对$x，y$，满足$x<=a，y<=b$并且$gcd(x,y)=d$

输入：

第一行包含一个正整数$n$，表示一共有$n$组数据$（1<=n<= 50000）$ 接下来$n$行，每行表示一个询问。每行三个正整数，分别为$a,b,d$（$1<=d<=a,b<=50000$）

输出：

对于每组询问，输出一个正整数，表示满足条件的整数对数

思路：

这是一个莫比乌斯反演的模版题，莫比乌斯反演虽然听起来很高级但内容还是比较好理解的。

首先是莫比乌斯函数$\mu(n)$，这是一个表示容斥系数的函数。它的定义是这样的：当n有相等的质因子$\mu(n)=0$；当n没有相等质因子且质因子个数为偶数$\mu(n)=1$；当$n$没有相等质因子且质因子个数为奇数$\mu(n)=-1$。

然后关于莫比乌斯反演有下面两个形式：我们设存在两个函数$F(n), f(n)$

形式一：如果满足条件 那么就有： 形式二：如果满足条件 那么就有： 关于证明，我这么菜自然是不懂的。

对于这道题，设$x=\lfloor a/d\rfloor$， $y=\lfloor b/d \rfloor$。显然可以将题目转化为求这样一个式子： 然后我们设$f(n)$为在范围内$gcd(i,j)=n$的的个数，设$F(n)$为在范围内$n|gcd(i,j)$的个数，因此 那么很显然，函数$f(d),F(n)$满足反演的第二种形式且$f(1)$就是我们所求答案。于是利用反演得到：

于是直接计算就是这样的（实测70分）:

1
2
for(int j=1; j<=min(a, b); j++) ans+=mob[j]*(a/j)*(b/j);
//注意这里的mob是未经前缀和处理的

然后可以发现$a/j, b/j$的取值是一段一段的，所以我们利用数论分块的方法进行优化。数论分块可以看这道题:BZOJ1257 余数之和，然后代码是这样的：

1
2
3
4
5
6
for(int l=1, r; l<=min(a, b); l=r+1)
{
    r=min(a/(a/l), b/(b/l));
    ans+=(mob[r]-mob[l-1])*(a/l)*(b/l);
}
//注意这里的mob是经过前缀和处理的

代码：

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 <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#define MAXN 500005
#define LL long long
using namespace std;

int n, a, b, d, cnt, pri[MAXN], tag[MAXN], mob[MAXN];

void init()
{
    mob[1]=1;
    for(int i=2; i<=50000; i++)
    {
        if(!tag[i]) pri[++cnt]=i, mob[i]=-1;
        for(int j=1; j<=cnt && pri[j]*i<=50000; j++)
        {
            tag[i*pri[j]]=1;
            if(i%pri[j]==0) {mob[i*pri[j]]=0; break;}
            else mob[i*pri[j]]=-mob[i];
        }
    }
    for(int i=2; i<=50000; i++) mob[i]+=mob[i-1];
}

int main()
{
    init();
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int ans=0;
        scanf("%d%d%d", &a, &b, &d);
        a/=d; b/=d;
        for(int l=1, r; l<=min(a, b); l=r+1)
        {
            r=min(a/(a/l), b/(b/l));
            ans+=(mob[r]-mob[l-1])*(a/l)*(b/l);
        }
        printf("%dn", ans);
    }
}

Posted on Edited on In

问题描述

给你 $n$ 个盒子，第 $i$ 个盒子中有 $a_i$ 枝花，同一盒子内花颜色相同，不同盒子内花颜色不同，你需要从中选出 $s$ 枝花，问你有多少中不同的方案。

输入

第一行两个数$n$，$s$ ($n \leq 20, s \leq 10^{14}$) 第二行 $n$ 个数，第 $i$ 个数表示 $a_i$ ($a_i \leq 10^{12}$)

输出

输出方案数对 $1000000007$ 取模的值

思路

这个就是多重集的组合数，当 $\forall a_i$ 都 $a_i>s$ 时根据「插板法」可以知道答案是 ${s+n-1} \choose {n-1}$。但当 $s$ 较大时，会有 $s>a_i$ 的情况出现，这时可以比较自然地想到利用容斥原理计算合法的方案数。我们可以枚举出现这种情况的集合 $S$，然后套上容斥，最终的答案就是：

需要注意的是计算组合数时，要用 Lucas 定理对组合数取模，防止爆 longlong。

对于这种组合问题，也可以从生成函数的角度去看，可以推出和上面一样的式子。我们将它的生成函数写出来：

然后利用等比数列求和公式化简为：

将原式后半部分泰勒展开：

这个式子的第 $x^s$ 项的系数就是我们要的答案。对于后半部分，它又是一个生成函数，根据它的组合意义我们同样根据「插板法」可以知道 $x^s$ 的系数是 ${s+n-1} \choose {n-1}$。而前半部分，我们可以将这 $n$ 项暴力拆分，并分别计算它对 $x^s$ 项系数的贡献。将这些加起来，就刚好与用容斥原理推出的式子一样。

代码

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

int n, ans, inv[MAXN];
LL s, a[MAXN];

int comb(int x, int y)
{
    if(x<y) return 0;
    int ans=1;
    for(rint i=0; i<y; ++i)
    {
        ans=1LL*ans*(x-i)%P;
        ans=1LL*ans*inv[i+1]%P;
    }
    return ans;
}

int main()
{
    scanf("%d%lld", &n, &s);
    for(rint i=0; i<n; ++i) scanf("%lld", &a[i]);
    inv[0]=inv[1]=1;
    for(rint i=2; i<=n; ++i) inv[i]=1LL*inv[P%i]*(P-P/i)%P;
    for(rint sta=0; sta<(1<<n); ++sta)
    {
        LL num=s, cnt=0;;
        for(rint i=0; i<n; ++i)
            if((sta>>i)&1)
            {
                cnt++;
                num-=(a[i]+1);
            }
        if(cnt&1) ans=(ans-comb((num+n-1)%P, n-1)+P)%P;
        else ans=(ans+comb((num+n-1)%P, n-1))%P;
    }
    printf("%d\n", ans);
    return 0;
}

Posted on Edited on In

8月3日 Codeforces Round #501 题目链接：http://codeforces.com/contest/1015

A - Points in Segments & B - Obtaining the String

比较水，不说了。。。

C - Songs Compression

思路： 很显然是一个贪心，按照能够压缩的大小排个序，能够选的就尽量选。然后就好了。

代码：

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, m;
LL tot;

struct A {int x, y;} a[1000005];

bool CMP(A x, A y) {return x.x-x.y>y.x-y.y;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    for(int i=1; i<=n; i++) tot+=a[i].x;
    if(tot<=m) {printf("0\n"); return 0;}
    for(int i=1; i<=n; i++)
    {
        tot-=(a[i].x-a[i].y);
        if(tot<=m) {printf("%d\n", i); return 0;}
        if(i==n) printf("-1\n");
    }
}

D - Walking Between Houses

思路： 蛮有趣的题，类似于构造吧。

我们设当前可以走$k$步，要走$s$距离，我们就以$(s+k-1)/k$为基准值，每一步走的距离都尽量靠近这个值（其实我也不清楚为什么是对的，只是觉得数据不好卡这个算法）。然后注意要特判两种为NO的情况。

代码：

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL n, k, s;
int ans[1000000], cnt;

void dfs(int pos, LL k, LL s)
{
    if(k==0 && s==0) return;
    LL dis=(s+k-1)/k;
    if(pos-dis>=1) pos=pos-dis;
    else if(pos+dis<=n) pos=pos+dis;
    else
    {
        LL t1=n-pos, t2=pos-1;
        if(t1>t2) pos=n, dis=t1;
        else pos=1, dis=t2;
    }
    ans[++cnt]=pos;
    dfs(pos, k-1, s-dis);
}

int main()
{
    scanf("%lld%lld%lld", &n, &k, &s);
    if(s>k*(n-1) || k>s) {printf("NO\n"); return 0;}
    printf("YES\n");
    dfs(1, k, s);
    for(int i=1; i<=cnt; i++) printf("%d ", ans[i]);
}

E1 - Stars Drawing (Easy Edition)

思路： 这个数据范围比较小，就是毒瘤模拟。。。我们枚举每个星星的中心，然后选尽可能大的，这个贪心比较显然。所以这个总复杂度为$O(N^3)$的。

代码：

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
#include <bits/stdc++.h>
#define LL long long
#define MAXN 1005
using namespace std;

int n, m, cnt, maxlen, x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN];
bool vis[MAXN][MAXN];
char mmp[MAXN][MAXN];

void check()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(mmp[i][j]=='*' && !vis[i][j]) {printf("-1\n"); exit(0);}
}

void find(int px, int py, int len)
{
    bool flag=1;
    if(px-len<1 || py-len<1 || px+len>n || py+len>m) return;
    for(int i=py; i<=py+len; i++) if(mmp[px][i]!='*') {flag=0; break;}
    for(int i=py; i>=py-len; i--) if(mmp[px][i]!='*') {flag=0; break;}
    for(int i=px; i<=px+len; i++) if(mmp[i][py]!='*') {flag=0; break;}
    for(int i=px; i>=px-len; i--) if(mmp[i][py]!='*') {flag=0; break;}
    if(flag) maxlen=len;
    find(px, py, len+1);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", mmp[i]+1);
    for(int px=1; px<=n; px++)
        for(int py=1; py<=m; py++)
        {
            maxlen=0;
            find(px, py, 1);
            if(maxlen)
            {
                x[++cnt]=px; y[cnt]=py; z[cnt]=maxlen;
                for(int i=py; i<=py+maxlen; i++) vis[px][i]=1;
                for(int i=py; i>=py-maxlen; i--) vis[px][i]=1;
                for(int i=px; i<=px+maxlen; i++) vis[i][py]=1;
                for(int i=px; i>=px-maxlen; i--) vis[i][py]=1;
            }
        }
    check();
    printf("%d\n", cnt);
    for(int i=1; i<=cnt; i++) printf("%d %d %d\n", x[i], y[i], z[i]);
}

E2 - Stars Drawing (Hard Edition)

思路： 这里可以用一个常规的优化，就是用$O(N^2)$的预处理，$O(N^2)$计算，答案来代替$O(N^3)$的普通算法。

不过预处理和计算都比较的巧妙。可以利用类似DP的方法算出每个位置上下左右有多少个连续的‘*’，那么星星最大的大小就是它们的最小值，于是预处理就是$O(N^2)$。

计算每个位置有没有星星覆盖可以利用前缀和的思想，对于位置在$x,y$且大小为$l$的星星，我们可以在$(x-l, y)$处打上$+1$的标记，在$(x+l+1, y)$打上$-1$的标记。类似的，也可以在$(x, y-l)$打上$+1$，$(x, y+l+1)$打上$-1$的标记。最后再扫一遍就可以确定星星的覆盖情况。

代码：

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#define MAXN 1005
#define LL long long
using namespace std;

int n, m, up[MAXN][MAXN], down[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN];
int cnt, tag1[MAXN][MAXN], tag2[MAXN][MAXN], x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN];
char mp[MAXN][MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", mp[i]+1);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(mp[i][j]=='*') up[i][j]=up[i-1][j]+1;
            if(mp[i][j]=='*') left[i][j]=left[i][j-1]+1;
        }
    for(int i=n; i>=1; i--)
        for(int j=m; j>=1; j--)
        {
            if(mp[i][j]=='*') down[i][j]=down[i+1][j]+1;
            if(mp[i][j]=='*') right[i][j]=right[i][j+1]+1;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            int l=min(min(up[i][j], down[i][j]), min(left[i][j], right[i][j]))-1;
            if(l<=0) continue;
            tag1[i-l][j]++; tag1[i+l+1][j]--;
            tag2[i][j-l]++; tag2[i][j+l+1]--;
            x[++cnt]=i; y[cnt]=j; z[cnt]=l;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            tag1[i][j]+=tag1[i-1][j];
            tag2[i][j]+=tag2[i][j-1];
            if(mp[i][j]=='*' && tag1[i][j]==0 && tag2[i][j]==0)
            {
                printf("-1\n");
                return 0;
            }
        }
    printf("%d\n", cnt);
    for(int i=1; i<=cnt; i++) printf("%d %d %d\n", x[i], y[i], z[i]);
}