Codeforces Contest #1312 解题报告 & 部分翻译

比赛链接:Educational Codeforces Round 83 (Rated for Div. 2)

A Two Regular Polygons

1 题目大意

给你两个正多边形,一个 $n$ 条边 $A$ ,一个 $m$ 条边 $B$

问 $B$ 有没有可能被 $A$ 包含且所有顶点都与 $A$ 的某一个节点重合

有输出 YES ,否则输出 NO

2 Code

判 $n \bmod m = 0$ 就可以了

#include <cstdio>

int T;
int n, m;

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d%d", &n, &m );
        printf( "%s\n", ( n % m == 0 )? "YES": "NO" );
    }
}

B Bogosort

1 题目大意

给你一个长度为 $n$ 的序列 $a$, 你可以将 $a$ 重新排序,使其满足 $j – a_j \neq i – a_i$

输出任何一个即可

保证有解

$n \leq 100$

2 思路

$$
\begin{aligned}
j – a_j & \neq i – a_i \\
j – i & \neq a_j – a_i
\end{aligned}
$$

直接从大到小输出

3 Code

// Woshiluo Luo<[email protected]>  
// 2020/03/09 22:40:32 
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 110;

int T;
int n;
int a[N];

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
        }
        std::sort( a + 1, a + n + 1 );
        for( int i = n; i >= 1; i -- ) {
            printf( "%d ", a[i] );
        }
        printf( "\n" );
    }
}

C Adding Powers

1 题目大意

给你两个长度为 $n$ 的数列 $a,v$

其中 $a$ 通过输入提供,$v$ 初始所有值为 $0$

接下来,对于第 $i$ 次操作(从 $0$ 计数),你可以

  • 选择任意一个 $v_i$ 增加 $k^i$
  • 什么都不做

问你是否通过多次操作后,使 $v$ 变成 $a$

能输出 YES ,否则输出 NO

2 思路

首先对于每个数字 $a$, 考虑其是否可以变成多个 $k^i$ 的和(不能有重复的 $i$)

能的话算出来,看看有没有和之前重复的,有就不可能

不能的话直接没有可能

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 22:58:45
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 110;

int T;
int n;
long long k;
bool vis[N];
long long a[N];

inline void wrong() {
    printf( "NO\n" );
}

inline void right() {
    printf( "YES\n" );
}

void calc() {
    for( int i = 1; i <= n; i ++ ) {
        if( a[i] == 0 ) {
            continue;
        }
        long long cur = a[i];
        int cnt = 1;
        while( cur ) {
            int tmp = cur % k;
            if( tmp > 1 ) {
                wrong();
                return ;
            }
            if( tmp == 1 ) {
                if( vis[cnt] == false )
                    vis[cnt] = true;
                else {
                    wrong();
                    return ;
                }
            }
            cur /= k;
            cnt ++;
        }
    }
    right();
}

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        memset( vis, 0, sizeof(vis) );

        scanf( "%d%lld", &n, &k );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%lld", &a[i] );
        }

        calc();
    }
}

D Count the Arrays

1 题目大意

你需要寻找这样的数列个数

  • 有 $n$ 个元素
  • 每个数字都是 $1$ 到 $m$ 之间的整数
  • 只有恰好一对数字相等
  • 数列先严格递增,再严格递减

个数对 $998244353$ 取模后输出

$2 \leq n \leq m \leq 2 \times 10^5$

2 思路

式子题,看 Code 去

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 23:21:18
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 2e5 + 1e4;
const int mod = 998244353;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while(p) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}

inline int get_inv( int a ) { return ksm( a, mod - 2 ); }

int n, m, sum, ans;
int fact[N], inv[N];

void init() {
    fact[1] = 1;
    for( int i = 2; i <= m; i ++ ) {
        fact[i] = mul( fact[ i - 1 ], i );
    }
    inv[m] = get_inv( fact[m] );
    for( int i = m - 1; i >= 1; i -- ) {
        inv[i] = mul( inv[ i + 1 ], i + 1 );
    }
    inv[0] = 1;
    fact[0] = 1;
}

// Get C^a_b
inline int C( int a, int b ) {
    if( a <= 0 )
        return 1;
    if( b <= 0 )
        return 1;
    return mul( mul( fact[b], inv[ b - a ] ), inv[a] );
}

int main() {
#ifdef woshiluo
    freopen( "d.in", "r", stdin );
    freopen( "d.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    init();

    for( int i = n - 1; i <= m; i ++ ) {
        add_eq( sum, mul( C( n - 3, i - 2 ), mul( m - i + 1, n - 2 ) ) );
    }

    for( int i = 2; i < n; i ++ ) {
        add_eq( ans, mul( sum, C( i - 2, n - 3 ) ) );
    }

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

E Array Shrinking

1 题目大意

这好像是个原题

给你一个长度为 $n$ 的数列 $a$

如果 $a_i = a_{i + 1}$, 那么这两个数可以合并成 $a_i + 1$

问最小数列长度

$1 \leq a_i \leq 1000, 1 \leq n \leq 500$

2 思路

区间 dp

设 $f_{i,j}$ 为 $i$ 到 $j$ 最小长度

$merged_{i,j}$ 为 $i$ 到 $j$ 合并出来的数字

然后就是标准板子了

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/10 15:50:48
#include <cstdio>
#include <cstring>

#include <algorithm>

const int N = 510;

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

int n;
int a[N];
int f[N][N], merged[N][N];

int main() {
#ifdef woshiluo
    freopen( "e.in", "r", stdin );
    freopen( "e.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%d", &a[i] );
        f[i][i] = 1;
        merged[i][i] = a[i];
    }
    for( int len = 2; len <= n; len ++ ) {
        for( int left = 1, rig = len; rig <= n; left ++, rig ++ ) {
            f[left][rig] = rig - left + 1;
            for( int mid = left; mid < rig; mid ++ ) {
                int &f_left = f[left][mid], &f_rig = f[ mid + 1 ][rig],
                &merge_left = merged[left][mid], &merge_rig = merged[ mid + 1 ][rig];
                chk_Min( f[left][rig], f_left + f_rig );
                if( f_left == 1 && f_rig == 1 && merge_left == merge_rig ) {
                    f[left][rig] = 1;
                    merged[left][rig] = merge_left + 1;
                }
            }
        }
    }
    printf( "%d\n", f[1][n] );
}

可重组合与不相邻组合

可重组合

从 ${1, 2, 3 \cdots, n – 1, n}$ 中选出 $m$ 个元素,可以重复,有多少个不同的组合?

答案 $C_{n + m – 1}^{m}$

证明

显然,问题可以转换为 $m$ 个球放入 $n$ 个盒子,可以放无数个或者不放

即插入 $n – 1$ 个隔板,然后求全排列 $(m + n – 1)!$

但是隔板和球的顺序是无效的所以除去 $m! \times (n-1)!$


$$
\frac{(m + n – 1)!}{m! \times (n – 1)!} = C_{n + m -1}^m
$$

Continue reading “可重组合与不相邻组合”

玄学数学 — Luogu P1762 偶数

0x01 写在之前

题目链接: [https://www.luogu.org/problemnew/show/P1762]

这道题形象生动的说明了从几何层面来找规律是多么的方便

~~打表找规律是多么的我方便~~

0x02 题目

题目一看…

杨辉三角?

%2意义下的面积?

输出一下看看吧

1
1 1
1   1
1 1 1 1
1       1
1 1     1 1
1   1   1   1
1 1 1 1 1 1 1 1
1               1
1 1             1 1
1   1           1   1
1 1 1 1         1 1 1 1
1       1       1       1
1 1     1 1     1 1     1 1
1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1                               1
1 1                             1 1
1   1                           1   1
1 1 1 1                         1 1 1 1
1       1                       1       1
1 1     1 1                     1 1     1 1
1   1   1   1                   1   1   1   1
1 1 1 1 1 1 1 1                 1 1 1 1 1 1 1 1
1               1               1               1
1 1             1 1             1 1             1 1
1   1           1   1           1   1           1   1
1 1 1 1         1 1 1 1         1 1 1 1         1 1 1 1
1       1       1       1       1       1       1       1
1 1     1 1     1 1     1 1     1 1     1 1     1 1     1 1
1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

这是在每一位都%2后只输出1后得到的结果

好好看啊wq

你为什么不试试在这里面找找规律呢?

我们可以很明显的观察到,每一个三角形都是由下面一个三角形所叠加出来的

1
11

每个第$ 2^i $ 行,就是一个三角形的结尾

每个第$ 2^i $ 行,就是由三个第 $ 1 $ 到 $ 2^{i-1} $的三角形组成

看起来第$ 2^i $ 行的结果我们可以算出来:

$$ f(1)=1 $$
$$ f(i) = f(i/2)*3 $$

整理一下:
第 $ 2^i $ 行有 $ 3^{i-1} $ 个1

恩,快速幂大法解决就可以

问题在于,不是$2^i$的怎么办?

恩,先打表找规律吧>_<

    1 : 1                1
    2 : 1 1                3
    3 : 1   1                5
    4 : 1 1 1 1                9
    5 : 1       1               11
    6 : 1 1     1 1               15
    7 : 1   1   1   1               19
    8 : 1 1 1 1 1 1 1 1               27
    9 : 1               1               29
   10 : 1 1             1 1               33
   11 : 1   1           1   1               37
   12 : 1 1 1 1         1 1 1 1               45
   13 : 1       1       1       1               49
   14 : 1 1     1 1     1 1     1 1               57
   15 : 1   1   1   1   1   1   1   1               65
   16 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1               81
   17 : 1                               1               83
   18 : 1 1                             1 1               87
   19 : 1   1                           1   1               91
   20 : 1 1 1 1                         1 1 1 1               99
   21 : 1       1                       1       1              103
   22 : 1 1     1 1                     1 1     1 1              111
   23 : 1   1   1   1                   1   1   1   1              119
   24 : 1 1 1 1 1 1 1 1                 1 1 1 1 1 1 1 1              135
   25 : 1               1               1               1              139
   26 : 1 1             1 1             1 1             1 1              147
   27 : 1   1           1   1           1   1           1   1              155
   28 : 1 1 1 1         1 1 1 1         1 1 1 1         1 1 1 1              171
   29 : 1       1       1       1       1       1       1       1              179
   30 : 1 1     1 1     1 1     1 1     1 1     1 1     1 1     1 1              195
   31 : 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1              211
   32 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1              243 

随便推一个吧qwq

14?

首先先找到2的次幂–8

ans+=27

剩下的相当于是 第6层 ×2

以此类推qwq

以下是代码

#include <cstdio>
#include <cmath>
const long long mod=1000003;
long long sum,ans,n;
inline long long lowbit(long long x){return x&(-x);}
inline long long ksm(long long a,long long p){// 标准快速幂
    long long res=1,base=a;
    while(p){
        if(p&1) res=(res*base)%mod;
        base=(base*base)%mod;
        p>>=1;
    }
    return res;
}
long long dfs(long long now){
    long long tmp=lowbit(now);// lowbit 用于快速找到第一个我可以分层的地方
    if(tmp==now){
        ans=ksm(3,(std::log(now)/std::log(2)));// tmp==now 说明 now 是 2的次幂 ( log 快速求指数)
        return 2; // 翻倍
    }
    else{
        long long tmp1=dfs(now-tmp);// 剪掉算过的
        ans=(ans+tmp1*ksm(3,(std::log(tmp)/std::log(2))))%mod;
        return tmp1*2;
    }
}
int main(){
    scanf("%lld",&n);
    dfs(n);
    if(n%2==0) sum=(((1+n)%mod)*((n/2)%mod))%mod;
    else sum=((((1+n)/2)%mod)*(n%mod))%mod;
    // 都说这个地方要乘法逆元之类的高端操作...我就直接暴力了
    printf("%lld",((sum-ans)%mod+mod)%mod);
}
]]>

数论基础 – 排列组合 – Luogu P2822 组合数问题

排列组合

加法/乘法原理


加法原理是分类,乘法原理讲究分步

加法原理

有一个问题,它有 \(n\) 类解决办法,对于第 \(a\) 类解决办法,有 \(x_a\) 种方法完成 那么,总解决方法数就是: $x_1+x_2+x_3+\cdots+x_{n-1}+x_n$

乘法原理

有一个问题,它有 \(n\) 个步骤,对于第 \(a\) 个步骤,有 \(x_a\) 种方法完成 那么,总解决方法数就是: $x_1*x_2*x_3*\cdots*x_{n-1}*x_n$ 这两个规律是显而易见的,甚至被放到了小学奥数里…

排列组合


先亮公式 排列: $$A_n^m={{n!} \over {(n-m)!}}$$ 组合: $$C_n^m={{n!} \over {m!(n-m)!}}$$ P.S.: 组合一作 \(P_n^m\) 这是一种较老的表示方法,本博客中使用 \(c_n^m\) 特别定义: $0!=1$ 我相信你的内心一定是迷茫的,让我们来看看这两个东西定义与使用

排列

定义: 从 \(n\) 个数中任意取出 \(m\) 个数,求有多少种方法,不同顺序算作另一种
那么这种问题第一下就会想到乘法原理 对于第一位数, 有 \(n\) 种选法,对于第 2 位数, 有 \(n-1\) 种选法,对于第3位数, 有 \(n-3\) 种选法,对于第 \(y\) 位数, 有 \(n-(y-1)\) 种选法 根据乘法原理得$A_n^m=n*(n-1)*(n-2)*(n-3)*\cdots*(n-m)$ 即$A_n^m={{n!} \over {(n-m)!}}$

组合

定义: 从 \(n\) 个数中任意取出 \(m\) 个数,求有多少种方法,不同顺序算同一种
这个的区别在于不同的顺序在于同一组,不过这么相似,显然是通过上面的推得 也就是说我们要将 $A_n^m$ 中去重,那么我们就要考虑,从 \(m\) 个数中取出的长度为\(m\)的序列会有多少组不同的组合,由排列得 $A_m^m=m!$ $\therefore C_n^m={{n!} \over {m!(n-m)!}}$

组合的特别性质

第一个: $$C_n^m=C_n^(n-m)$$ 证明:$$\because C_n^{n-m}={n! \over {(n-m)![n-(n-m)]!}}={n! \over {(n-m)!n!}}$$ $$\because {C_n^m=n! \over {m!(n-m)!}}$$ $$\therefore {C_n^m=C_n^{n-m}}$$ 第二个: $$ C_n^m=C_{n-1}^m+C_{n-1}^{m-1} $$ 证明:$$ C_{n-1}^m+C_{n-1}^{m-1}={{(n-1)! \over {m!(n-m-1)!}} + {(n-1)! \over {(m-1)!(n-m)!}}} $$ $$={(n-1)(n-2)(n-3) \cdots m \over (n-m)!}+{(n-1)(n-2)(n-3) \cdots (m+1) \over (n-m-1)!}$$ $$={(n-1)(n-2)(n-3) \cdots (m+1)(n-m+m) \over (n-m)!}$$ $$={n! \over {m!(n-m)!}}$$ 这个实际上就是杨辉三角啦 第三个: $$C_n^0+C_n^1+C_n^2+\cdots+C_n^{n-1}+C_n^n=2^n$$ 这个的证明,再用等式的性质…..你们的博主还没有这么厉害… 实际上就是说,你想象一下对 \(n\) 个物品中随意取(1,n)个,这不就相当于你在你在 \(n\) 个物品中间,随意取几个吗 有点眼熟啊…这不是01背包思想吗!! 把每个物品当作一个 0/1 数值,选为 1 不选为 0 ,你么根据乘法原理,总共有 \(2\^n\) 种可能

P2282 组合数问题

题目链接:[https://www.luogu.org/problemnew/show/P2822]
题目第一眼过去想让人暴力套公式计算,但是…\(t<10^4+1\) 这个速度就比较温暖人心了,有没有什么快速解决的办法的呢? 当然有!杨辉三角了解一下 当然我们不能每个数组数据都处理一波,\(n<2000+1\),后面前缀和保留每一行,后面遍历行数前缀相加就可以了 千万不要忘记边做边取模

代码


#include <cstdio>
using namespace std;
long long t,k;
long long n,m;
long long c[2200][2200];
//   n     m
long long cnt=0;
long long sum[2200][2200];
inline long long min(long long a,long long b){return a<b?a:b;}
int main(){
    scanf("%lld%lld",&t,&k);
    for(int i=0;i<=2100;i++){//预处理
        if(i==0){
            for(int j=0;j<=i;j++){
                c[0][j]=1;
                if(c[0][j]%k==0) sum[0][j]=1;// 前缀和
                else sum[0][j]=0;
            }
        }
        else for(int j=0;j<=i;j++){
            if(j==0||j==i) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; // 记得取模
            if(j==0){
                if(c[i][j]%k==0) sum[i][j]=1;
                else sum[i][j]=0;
            }
            else {
                if(c[i][j]%k==0) sum[i][j]=sum[i][j-1]+1;
                else sum[i][j]=sum[i][j-1];
            }
        }
    }
    for(int i=1;i<=t;i++){//及其稀少的主部分
        cnt=0;// 别忘记设0
        scanf("%lld%lld",&n,&m);
        for(long long j=0;j<=n;j++){
            cnt+=sum[j][min(m,j)];
        }
        printf("%lld\n",cnt);
    }
}
为什么用long long呢,因为乘的时候可能会出事

END

为什么计算机要学习数论呢,诶我桌子上怎么这么多头发… ]]>