Dylan's Blog
0%

Posted on Edited on In

问题描述：

简单来说就是让你计算：

输入：

两个数N、G

输出：

一个数，表示答案除以999911659的余数

思路：

很好的一道题呢，涵盖了大部分数论知识点呢：欧拉定理、中国剩余定理，Lucas定理，组合数取模，逆元….

不过思路不会很复杂。首先指数那么大，肯定不难想到利用欧拉定理将指数缩小，原理可以看这篇文章。所以我们可以将指数变为$\sum_{d|n}C_n^d mod 999911658$，求这个就是求组合数取模，用lucas定理。。。

那么问题来了，我们普通的Lucas定理中模数要求是质数，但这题中模数不是质数，因此我们要用扩展Lucas。首先将模数质因数分解，分解为2，3，4679，35617四个质数。分别在模这四个质数的意义下求出我们要的结果$a_1, a_2, a_3, a_4$。这样答案就可以表示为： $ans \equiv a_1 (mod 2) $ $ans \equiv a_2 (mod 3) $ $ans \equiv a_3 (mod 4769) $ $ans \equiv a_4 (mod 35617) $ 那这样就是中国剩余定理的形式，解出$ans$并利用快速幂$G^{ans}$就好了。

代码：

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 <cstring>
#include <cmath>
#define LL long long
#define mod 999911659
#define MAXN 40005
using namespace std;

const LL prime[5]={0, 2, 3, 4679, 35617};

LL n, g, num[MAXN], fac[MAXN], inv[MAXN];

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

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

LL lucas(LL n, LL m, LL p)
{
    if(m==0) return 1;
    return comb(n%p, m%p, p)*lucas(n/p, m/p, p)%p;
}

LL crt()
{
    LL ans=0;
    for(int i=1; i<=4; i++)
    {
        LL m=(mod-1)/prime[i];
        ans=(ans+num[i]*m%(mod-1)*ksm(m, prime[i]-2, prime[i]))%(mod-1);
    }
    return ans;
}

int main()
{
    scanf("%lld%lld", &n, &g);
    if(g==mod) {printf("0\n"); return 0;}
    for(int i=1; i<=4; i++)
    {
        fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(int j=2; j<=prime[i]; j++)
        {
            fac[j]=fac[j-1]*j%prime[i];
            inv[j]=inv[prime[i]%j]*(prime[i]-prime[i]/j)%prime[i];
        }
        for(int j=2; j<=prime[i]; j++) inv[j]=inv[j-1]*inv[j]%prime[i];

        for(int j=1; j*j<=n; j++)
        {
            if(n%j) continue;
            num[i]=(num[i]+lucas(n, j, prime[i]))%prime[i];
            if(j*j==n) continue;
            num[i]=(num[i]+lucas(n, n/j, prime[i]))%prime[i];
        }
    }
    printf("%lld\n", ksm(g, crt(), mod));
}

Posted on Edited on In

问题描述：

脸哥最近在玩一款神奇的游戏，这个游戏里有 $n $件装备，每件装备有$ m$ 个属性，用向量$z_i(a_j ,…..,a_m)$ 表示。每个装备需要花费 $ci$，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

如果脸哥买了 $z_{i1},…..z_{ip}$这$ p$ 件装备，那么对于任意待决定的 $z_h$，不存在 $b_1,….,b_p$ 使得 $b_1z_{i1} + … + b_pz_{ip} = z_h$（$b$ 是实数），那么脸哥就会买 $z_h$，否则 $z_h$ 对脸哥就是无用的了，自然不必购买。脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

输入：

第一行两个数 $n$，$m$。接下来$ n $行，每行 $m$ 个数，其中第$ i $行描述装备$ i $的各项属性值。 接下来一行$ n $个数，其中$ c_i $表示购买第 $i $件装备的花费。

输出：

一行两个数，第一个数表示能够购买的最多装备数量，第二个数表示在购买最多数量的装备的情况下的最小花费

思路：

题目说简单一点就是你要在一组向量中，要求出最大的线性无关子集，也就是线性基。

线性基的求法就是把$n$个向量看成是$n*m$的系数矩阵，然后进行高斯消元，剩下的非零向量就是线性基，那么最多的装备数量就是线性基的大小。但是我们还要维护它的最小花费，这时我们就可以使用贪心的策略了，可以将价格排一个序，消元时尽可能用价格低的消去其他的，这样就可以了。

这个的证明也很有趣，因为线性基是是线性无关的，如果有一个价格更低的能被它们表示，那么我们可以放进去一个价格低的，取出一个价格高的。这样，价格高的一定能被新的线性基表示，所以我们可以使用这种贪心策略。

代码：

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
#include <bits/stdc++.h>
#define LB long double
#define eps 1e-6
#define MAXN 505
using namespace std;

int n, m, num, val, f[MAXN];

struct Weap {LB z[MAXN]; int val;} weap[MAXN];

bool CMP(Weap x, Weap y) {return x.val<y.val;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%llf", &weap[i].z[j]);
    for(int i=1; i<=n; i++) scanf("%d", &weap[i].val);

    sort(weap+1, weap+n+1, CMP);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(fabs(weap[i].z[j])<eps) continue;
            if(f[j]==0)
            {
                f[j]=i;
                num++; val+=weap[i].val;
                break;
            }
            else
            {
                LB rate=weap[i].z[j]/weap[f[j]].z[j];
                for(int k=j; k<=m; k++) weap[i].z[k]-=rate*weap[f[j]].z[k];
            }
        }
    printf("%d %d\n", num, val);
}

Posted on Edited on In

7月28日 Codeforces Round #498 题目链接：http://codeforces.com/contest/1006

A - Adjacent Replacements & B - Polycarp’s Practice

比较水呢。。不说

C- Three Parts of the Array

思路： 也很水呢。。。就是一个双指针，记录两边的和就好了。其余的看代码。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, l, r;
LL lsum, rsum, a[1000005], ans;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    l=1, r=n;
    while(l<=r)
    {
        if(lsum==rsum) ans=lsum;
        if(lsum<=rsum) lsum+=a[l], l++;
        else rsum+=a[r], r--;
    }
    if(lsum==rsum) ans=lsum;
    printf("%lld\n", ans);
}

D - Two Strings Swaps

思路： 毒瘤，卡了超级久。。。首先思路很简单，因为$a_i$, $a_{n+1-i}$, $b_i$, $b_{n+1-i}$直间能够任意交换，所以我们可以把这4个元素看成一块，计算出要改几个字符。

关于答案的的计算方法很毒瘤，就是分类讨论！！有很多情况，也有很多细节，在讨论过程中思路一定要清晰，千万不要漏情况了。。我就漏了QWQ

代码：

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

int n, ans;
char a[100005], b[100005];
map<char, int> mp;

int main()
{
    scanf("%d", &n);
    scanf("%s", a+1);
    scanf("%s", b+1);
    for(int i=1; i<=(n+1)/2; i++)
    {
        if(i+i==n+1)
        {
            if(a[i]!=b[i]) ans++;
            continue;
        }
        mp.clear();
        mp[a[i]]++, mp[a[n+1-i]]++;
        mp[b[i]]++, mp[b[n+1-i]]++;
        if(mp.size()==2 && mp[a[i]]!=2) ans++;
        if(mp.size()==3)
        {
            if(a[i]==a[n+1-i]) ans+=2;
            else ans++;
        }
        if(mp.size()==4) ans+=2;
    }
    printf("%d\n", ans);
}

E - Military Problem

思路： 首先一棵子树在DFS序上是连续的，我们可以利用这个性质，然后这道题就是水题了。我们只要一遍DFS处理处子树大小和整棵树的DFS序，如果$k$大于了$x$的子树大小，那么答案就是-1，否则就是DFS序在$x$后$k-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
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;

int n, q, cnt, id, siz[MAXN],ver[MAXN], dfn[MAXN], head[MAXN];

vector<int> g[MAXN];

void dfs(int x, int fa)
{
    siz[x]=1;
    dfn[x]=++id; ver[id]=x;
    for(int i=0; i<g[x].size(); i++)
    {
        int to=g[x][i];
        if(to==fa) continue;
        dfs(to, x);
        siz[x]+=siz[to];
    }
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=2; i<=n; i++)
    {
        int temp;
        scanf("%d", &temp);
        g[i].push_back(temp);
        g[temp].push_back(i);
    }
    dfs(1, 0);
    for(int i=1; i<=q; i++)
    {
        int x, k;
        scanf("%d%d", &x, &k);
        if(k>siz[x]) printf("-1\n");
        else printf("%d\n", ver[dfn[x]+k-1]);
    }
}

F - Xor-Paths

思路： 看范围就知道是双向爆搜。。。然后就直接码就好了，然后就是中间相交处理答案时有一些细节要注意。中间的那一条是计算过两次的，所以在更新$cnt$数组是还要异或一下那个数字。

代码：

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

int n, m;
LL k, ans, a[35][35];
map<LL, LL> cnt[35][35];

void dfs1(int x, int y, LL num)
{

    if(x+y==(n+m)/2+1) {cnt[x][y][num^a[x][y]]++; return;}
    if(x<n) dfs1(x+1, y, num^a[x+1][y]);
    if(y<m) dfs1(x, y+1, num^a[x][y+1]);
}

void dfs2(int x, int y, LL num)
{

    if(x+y==(n+m)/2+1) {ans+=cnt[x][y][num^k]; return;}
    if(x>1) dfs2(x-1, y, num^a[x-1][y]);
    if(y>1) dfs2(x, y-1, num^a[x][y-1]);
}

int main()
{
    scanf("%d%d%lld", &n, &m, &k);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%lld", &a[i][j]);
    dfs1(1, 1, a[1][1]);
    dfs2(n, m, a[n][m]);
    printf("%lld\n", ans);
}

Posted on Edited on In

7月26日 Educational Codeforces Round 47 题目链接：http://codeforces.com/contest/1009

A - Game Shopping & B - Minimum Ternary String

简单，不讲。。。

C - Annoying Present

思路： 其实也比较水。。。首先参数$x$对答案的贡献是不会变的，根据一些小学数学知识可以知道：当$d$为正时，选取的位置越靠边贡献越大；当$d$为负时，选取的位置越靠中间贡献越大。因此分类讨论一下就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL ans, n, m, x, d;;

int main()
{
    scanf("%lld%lld", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%lld%lld", &x, &d);
        ans+=n*x;
        if(d>0) ans+=(n-1)*n/2*d;
        else
        {
            if(n&1) ans+=(n/2)*(n/2+1)*d;
            else ans+=n*n/4*d;
        }
    }
    printf("%lf\n", (double)ans/n);
}

D - Relatively Prime Graph

思路： 虽然是构造一张图，其实和图论没有什么关系。。。

看懂题意以后可以发现你就是要在$1-n$内找出$m$对互素的数，于是可以暴力枚举，知道枚举出$m$对数。因为这是实在是太暴力了，比赛时还在怀疑算法不够优秀。其实互质数对的分布是玄学的，所以一般是不好卡你暴力的，再加上CF的神机，放心的打就好了。（实测46ms) 代码：

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

int n, m, cnt;
pair<int, int> ans[100005];

int gcd(int x, int y) {return y==0 ? x : gcd(y, x%y);}

void solve()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
            if(gcd(i, j)==1)
            {
                ans[++cnt].first=i; ans[cnt].second=j;
                if(cnt==m) return;
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    if(m<n-1)
    {
        printf("Impossible\n");
        return 0;
    }
    solve();
    if(cnt<m) printf("Impossible\n");
    else
    {
        printf("Possible\n");
        for(int i=1; i<=m; i++) printf("%d %d\n", ans[i].first, ans[i].second);
    }
}

E - Intercity Travelling

思路： 一看题目，哇，和JXOI的风格好像的QVQ，都是小清新的期望计数题。虽然是期望，不过同样是套了期望的说法的一些计数类问题。

首先想到$n^2$的暴力DP，先处理前缀和。设$g[i]$为有多少种方法到达$i$点，$f$就是答案所求的东西，那么DP的方法就如下面代码所示：

1
2
3
4
5
6
7
8
9
10
11
12
g[0]=1;
for(int i=1; i<=n; i++)
{
    scanf("%lld", &a[i]);
    a[i]=(a[i]+a[i-1])%p;
}
for(int i=1; i<=n; i++)
    for(int j=0; j<i; j++)
    {
        f[i]=(f[i]+f[j]+a[i-j]*g[j])%p;
        g[i]=(g[i]+g[j])%p;
    }

然后我们打表发现$g[i]$就是$2^{i-1}$，又发现$f[i]$只由$a$中的元素组成，且组成方法与$a$中元素的值无关。于是再次打表，打出$f[i]$由$a$中的元素怎么构成，于是发现其中$h[n+1-i]$为构成$f[n]$(即答案)中$a[i]$的系数。即： 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define LL long long
#define MAXN 1000006
#define p 998244353
using namespace std;

LL n, ans, h[MAXN], g[MAXN], a[MAXN], sum[MAXN];

int main()
{
    scanf("%lld", &n);
    g[1]=g[0]=1;
    for(int i=2; i<=n; i++) g[i]=(g[i-1]*2)%p;
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]=(a[i]+a[i-1])%p;

    for(int i=1; i<=n; i++)
    {
        h[i]=(sum[i-1]+g[i-1])%p;
        sum[i]=(sum[i-1]+h[i])%p;
    }
    for(int i=1; i<=n; i++) ans=(a[i]*h[n-i+1]+ans)%p;
    printf("%lld\n", ans%p);
}

F - Dominant Indices

思路： 一直没有学树上启发式合并。膜题解发现要用这种操作，于是学了一下。个人理解就是遍历每个节点，然后从每个节点再开始另一个搜索，处理出该节点子树的信息，这样显然最坏是$O(N^2)$的。然而我们可以从先遍历节点，回溯时保留父亲节点重儿子的信息，这样从父亲节点开始的另一个搜索就可以不用搜重儿子。于是我们保证了时间复杂度在$O(logn)$。

这道题也是类似，要求子树重节点最多的那一层，于是就按照启发式合并去做就好了。 代码：

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

int n, cnt, maxnum, maxans, siz[MAXN], head[MAXN], dep[MAXN], ans[MAXN], num[MAXN], tag[MAXN];

struct Edge {int next, to;}edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs1(int x, int fa)
{
    siz[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        siz[x]+=siz[to];
    }
}

void update(int x)
{
    if(num[dep[x]]>maxnum) maxnum=num[dep[x]], maxans=dep[x];
    if(num[dep[x]]==maxnum && dep[x]<maxans) maxans=dep[x];
}

void add(int x, int fa, int op)
{
    num[dep[x]]+=op;
    update(x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        add(to, x, op);
    }
}

void dfs2(int x, int fa, int keep)
{
    int maxson=-1, maxsize=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        if(siz[to]>maxsize) maxson=to, maxsize=siz[to];
    }

    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to==maxson) continue;
        dfs2(to, x, 0);
    }
    if(maxson!=-1) dfs2(maxson, x, 1);

    num[dep[x]]++;
    update(x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to==maxson) continue;
        add(to, x, 1);
    }
    ans[x]=maxans;

    if(keep==0)
    {
        num[dep[x]]--;
        update(x);
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(to==fa) continue;
            add(to, x, -1);
        }
        maxnum=maxans=0;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);  
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]-dep[i]);
}

Posted on Edited on In

问题描述：

有一个球形空间产生器能够在$n$维空间中产生一个坚硬的球体。现在，你被困在了这个$n$维球体中，你只知道球面上$n+1$个点的坐标，你需要以最快的速度确定这个$n$维球体的球心坐标，以便于摧毁这个球形空间产生器。

输入：

第一行是一个整数$n(1<=N=10)$。接下来的$n+1$行，每行有$n$个实数，表示球面上一点的$n$维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。

输出：

有且只有一行，依次给出球心的$n$维坐标，两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。

思路：

这应该是比较裸的高斯消元了。球心到$n+1$个点距离相等，那么我们把距离当作常量就有$n+1$个方程。把常量减去后就剩下$n$个方程$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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define MAXN 20
#define eps 1e-8
using namespace std;

int n;
double a[MAXN][MAXN], b[MAXN], c[MAXN][MAXN];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n+1; i++)
        for(int j=1; j<=n; j++) scanf("%lf", &a[i][j]);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            c[i][j]=2*(a[i][j]-a[i+1][j]);
            b[i]+=a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j];
        }

    for(int i=1; i<=n; i++)
    {
        for(int j=i; j<=n; j++)
            if(fabs(c[j][i])>eps)
            {
                for(int k=1; k<=n; k++) swap(c[i][k], c[j][k]);
                swap(b[i], b[j]);
            }
        for(int j=1; j<=n; j++)
            if(i!=j)
            {
                double rate=c[j][i]/c[i][i];
                for(int k=i; k<=n; k++) c[j][k]-=c[i][k]*rate;
                b[j]-=b[i]*rate;
            }
    }
    for(int i=1; i<n; i++) printf("%.3lf ", b[i]/c[i][i]);
    printf("%.3lf\n", b[n]/c[n][n]);
}