2020-09-07 10:21 已编辑算法工程师

关注

【题解】牛客IOI周赛18-提高组

本场比赛来自湖南师大附中高一学生@ $CCA$ ，同时感谢本校学长@ $Xinxie$

总结：题目难度控制得还行，不过部分分并没有很大区分度，且 $AK$ 人数过多，这是我没有想到的。

师大附中 $1$ 人

北京大学 $1$ 人

人大附中 $2$ 人

长郡中学 $8$ 人

中山市第一中学 $1$ 人

合肥工业大学 $1$ 人

北京市第八十中学 $1$ 人

首都师大附中 $1$ 人

北大附中 $4$ 人

北京航空航天大学 $1$ 人

其他（未知） $2$ 人

总计 $23$ 人，让我们恭喜他们！

$T1$

第一档暴力分直接模拟。

$Code$

#include
using namespace std;
const int N = 5e5 + 10;
const int M = 10 + 5;
int n , m , k , l[M] , r[M] , a[N];
int main(){
    //freopen("data.in" , "r" , stdin);
    //freopen("brute.out" , "w" , stdout);
    scanf("%d %d %d" , &n , &m , &k);
    for(int i = 1; i <= m; i++)
        scanf("%d %d" , &l[i] , &r[i]);
    for(int i = 1; i <= n; i++) a[i] = i;
    while(k--) for(int i = 1; i <= m; i++){
        int d = (r[i] - l[i]) >> 1;
        for(int j = 0; j < d; j++)
            swap(a[l[i] + j] , a[r[i] - j]);
    }
    for(int i = 1; i <= n; i++) printf("%d " , a[i]);
    return 0;
}

第二档部分分可以将枚举的结果存下来，可以发现循环节比较小，找到以后 $k$ 对其取模即可。

正解：

我们可以先暴力做一次操作，复杂度 $O(nm)$ ，然后记 $p_i$ 为 $i$ 现在的位置，连接 $i->p_i$ 。

现在我们得到了一张图，图中有一些环，我们发现一次操作就是将所有的数在自己所属的环上跑一步，于是我们可以分别将 $k$ 对每个环的大小取模。

$Code$

#include
using namespace std;
const int N = 1e5 + 10;
const int M = 10 + 5;
int n , m , k , L[M] , R[M] , a[N] , ans[N];
int cnt , vis[N] , bel[N] , num[N] , to[N];
int Stack[N] , top;
void dfs(int p){
    vis[p] = true , bel[p] = cnt , num[cnt]++;
    if(!vis[to[p]]) dfs(to[p]);
}
void Circle(int u){
    int d = k % num[bel[u]]; top = 0;
    for(int i = u; !vis[i]; i = to[i])
        Stack[top++] = i , vis[i] = true;
    memset(vis , false , sizeof(vis));
    for(int j = 0 , i = u; !vis[i]; i = to[i] , j++)
        ans[i] = Stack[(j - d + top) % top] , vis[i] = true;
}
int main(){
    scanf("%d %d %d" , &n , &m , &k);
    for(int i = 1; i <= m; i++)
        scanf("%d %d" , &L[i] , &R[i]);
    for(int i = 1; i <= n; i++) a[i] = i;
    for(int i = 1; i <= m; i++){
        int d = (R[i] - L[i] + 1) >> 1;
        for(int j = 0; j < d; j++)
            swap(a[L[i] + j] , a[R[i] - j]);
    }
    for(int i = 1; i <= n; i++) to[a[i]] = i;
    for(int i = 1; i <= n; i++)
        if(!vis[i]) cnt++ , dfs(i);
    memset(vis , false , sizeof(vis));
    for(int i = 1; i <= n; i++)
        if(!vis[i]) Circle(i); 
    for(int i = 1; i <= n; i++) printf("%d " , ans[i]);
    return 0;
}

$T2$ :

先求出所有的方案数，显然为 $2^{n-1}$ 。

然后再求出不合法的方案数， $DP$ 方程为：

$Dp[ i ] = ∑(j : 1 -> k)dp[ i – t[ j ] ]$

矩阵加速优化线性 $DP$ 后求出不合法方案，再用所有方案减去不合法方案就可以了。

$Code$

#include
using namespace std;
#define int long long
const int max_l = 100 + 5;
struct Square
{
    long long g[max_l][max_l];
    void clear(){
        memset( g , 0 , sizeof(g) ) ;
    }
    void beg()
    {
        clear() ;
        for(int i = 1 ; i <= 100 ; i++ ) g[i][i] = 1 ;
        return ;
    }
}A;
long long n , mod , sum;
int k , t[max_l];
long long dp[max_l];
void Input ()
{
    scanf("%lld %lld %d" , &n , &mod , &k);
    A.clear() ; 
    for(int i = 1; i <= k; i++) scanf("%d" , &t[i]);
    for(int i = 1; i <= k; i++)
        if( 100 >= t[i] ) A.g[100 - t[i] + 1][100] = 1;
    for(int i = 1; i <= 99; i++)
        A.g[i + 1][i] = 1;
}
void DP ()
{
    dp[0] = 1;
    for(int i = 1; i <= 100; i++)
        for(int j = 1; j <= k; j++)
            if(i >= t[j])
                dp[i] = (dp[i] + dp[i - t[j]]) % mod;
}
long long f (long long p)
{
    if(p == 1) return 2;
    long long s = f(p / 2);
    if(p & 1) return (s * s * 2) % mod;
    else return (s * s) % mod;
}
Square mul (Square a , Square b)
{
    Square c;
    c.clear() ;
    for(int i = 1; i <= 100; i++)
        for(int j = 1; j <= 100; j++)
            for(int d = 1; d <= 100; d++)
                c.g[i][j] = (c.g[i][j] + a.g[i][d] * b.g[d][j]) % mod;
    return c;
}
Square ksm (Square a , long long p)
{
    Square ans;
    ans.beg() ;
    while( p )
    {
        if( p & 1 ) ans = mul( ans , a ) ;
        a = mul( a , a ) ;
        p = p >> 1 ;
    }
    return ans ;
}
signed main()
{
    Input();
    DP();
    if( n <= 100 ){
        printf("%lld\n" , f( n - 1 ) - dp[n] % mod ) ;
        return 0 ;
    }
    A = ksm(A , n );
    Square t ; t.clear() ;
    for(int i = 1 ; i <= 100 ; i++ ) t.g[1][i] = dp[i - 1] % mod ;
    t = mul( t , A ) ;
    printf("%lld\n" , ( ( f( n - 1 ) - t.g[1][1] ) % mod + mod )% mod ) ;
    return 0;
}

$T3$ :

$\rm Sol:$

$——by\; \rm Xinxie$

说在前面：经过多方考证，组合并不属于数论范畴

$\rm Sol:$

此篇题解仅供参考。

题意

给定一个值域大小和序列长度，求出对于以此构造一个 “单峰序列” 的方案数。

思想

对于一些奇怪的数据点或者平凡的做法我们放在后面讨论，目前考虑如何运用组合数学来求解此题。

我们发现对于单峰序列的最大值的两侧而言，分别成不下降和不上升子序列。但是由于他们在构造的过程中本质相同，我们仅考虑讨论不下降作为本题的关键。

我们考虑从 $[1,n]$ 中选择 $m$ 个数来构造不下降子序列。由于假定我们知道了选择的 $m$ 个数中，对于 $[1,n]$ 中的每个数他所出现的个数时，我们就可以确定对于这一次的构造是固定的。

通俗地讲，就是我们假设选择的 $m$ 个数中 $1$ 出现了 $x_1$ 次， $2$ 出现了 $x_2$ 次，以此类推直到 $n$ 出现了 $x_n$ 次。那么对于这一种情况所能够构成的不下降子序列必然是 $x_1$ 个 $1$ 后面接上 $x_2$ 个 $2$ 直到 $x_n$ 个 $n$ 作为结束。那么我们对于转化之后的问题的本质有了清晰的了解。

$\sum_{i=1}^{n} {x_i} = m \tag{1}$

现在考虑的问题的本质就是求解关于式 $\text(1)$ 成立的非负整数解的个数。而这个东西则是组合数中的一个经典问题，即多重集合的组合问题。而答案则是 $\binom{n+m-1}{m}$ ，如果对此没有了解的同学可以去学习一下，也有所了解的同学也建议在看完题解后去完成 CF57C Array 。本题的灵感也正来源于此。

在发现本题正是一道关于多重集的组合数问题后，于是题目又进一步被转化成对于枚举最大值所出现的位置和最大值的大小后，再计入最大值两边的不下降及不上升子序列的贡献。然而只是这样的想法并不能解决问题，因为对于最大值在一个序列中出现一次以上的话，这样的想法必然会出现重复计入贡献。比如 $1,2,3,3,2,1$ 这个序列在枚举最大值为 $3$ 时，枚举最大值出现位置为 $3$ 和 $4$ 时将会计入两次贡献。

于是我们只需要进一步的考虑增加一个维度。考虑枚举最大值的大小之后，再枚举最大值的起始位置和最大值出现在序列中的长度，或者是枚举最大值出现在序列中的区间左右端点。于是我们就将本题转化为求解下式：

$\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{m} \binom{i+j-3}{i-2} \binom{m+i-j-k-1}{i-2} \tag{2}$

也许您在看完式 $\text{(2)}$ 并略加思考后会产生疑问，于是特此声明，本文由于对公式简明的要求，对于一切涉及负整数的组合数所计入的值均为 $0$ ，并且在本文中将不存在实际意义。

我们再简化一下式 $\text{(2)}$ 的形式：

$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \binom{i+j-1}{i-1} \sum_{k=0}^{m-1} \binom{m+i-j-k-2}{i-1} \tag{3}$

于是时间复杂度为 $\text{O}({n}{m}^{2})$ 的做法就比较显然了，直接按照式 $\text{(2)}$ 或者式 $\text{(3)}$ 写代码。

考虑如何化解式 $\text{(3)}$ ？我们考虑在之后的证明中使用组合数恒等式。

$\sum_{k=0}^{m-1} \binom{m+i-j-k-2}{i-1} \tag{4}$

考虑到对于枚举 $[i][j]$ 后是固定的，通过求解式 $\text{(4)}$ 可以将本题时间复杂度进一步优化。

$\sum_{i=0}^{n} \binom{i}{m} = \binom{n+1}{m+1} \tag{5}$

由于对于式 $\text{(4)}$ 的组合数而言，是在 “ $n$ 选 $m$ ” 的意义中保持 $m$ 不变而 $n$ 变化的，很容易直接联想到式 $\text{(5)}$ ，然后直接运用化差思想（即对于 $[i,j]=[0,j]-[0,i-1]$ ）就可以把时间复杂度降为 $\text{O}({n}{m})$ 。

$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \binom{i+j-1}{i-1} \binom{m+i-j-1}{i} - \binom{i+j-1}{i-1} \binom{i-j-1}{i} \tag{6}$

这时仔细观察式 $\text{(6)}$ ，我们很容易发现对于 $\binom{i-j-1}{i}$ 由于 $i-j-1$ ，所以意义和值为 $0$ 。

$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \binom{i+j-1}{i-1} \binom{m+i-j-1}{i} \tag{7}$

如果这时发现没有太直接的想法时，我们就应该考虑如何转化一下公式的表达方式。很多时候题目的妙处不是不存在，而是你无法直接的观察发现，这时就需要耐心的探索。

$\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1} \tag{8}$

这个最基础却也是最著名的帕斯卡公式就是我们的选择。通过式 $\text{(7)}$ 和式 $\text{(8)}$ 的综合，此时我们可以发现 $\binom{i+j-1}{i-1}$ 可以转化为 $\binom{i+j}{i} - \binom{i+j-1}{i}$ 。

$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \binom{i+j}{i} \binom{m+i-j-1}{i} - \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \binom{i+j-1}{i} \binom{m+i-j-1}{i} \tag{9}$

当我们得到式 $\text{(9)}$ 时，便可以考虑再进行进一步转化。这里我们可以探究一下式 $\text{(9)}$ 的妙处所在，在通过一系列的组合数简化后，我们令 $a = i$ ， $b = i - 1$ ， $c = m -i - 1$ 。

$\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \binom{a+j}{a} \binom{c+j}{c} - \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \binom{b+j}{b} \binom{c+j}{c} \tag{10}$

式 $\text{(10)}$ 的出现的确会给本题带来新的思路，但是考虑到正解的思路并非如此，就不再具体阐述。

重新考虑到对于式 $\text{(9)}$ 的组合数枚举 $[i]$ 固定后是在 “ $n$ 选 $m$ ” 的意义中保持 $m$ 不变而 $n$ 变化的，但是对于一个 $n_1$ 呈增加趋势和另一个 $n_2$ 呈减少趋势的乘积的处理，我们无法直接使用上文证明中引入的式 $\text{(5)}$ ，而是考虑一个更加有力的组合数恒等式（公式的证明见卷尾）。

$\sum_{l=0}^{n} \binom{n-l}{r} \binom{m+l}{k} = \binom{n+m+1}{r+k+1} \tag{11}$

式 $\text{(11)}$ 的出现对于本文的证明有了很大帮助。我们考虑令 $l = j$ ， $n_1 = m + i - 1$ ， $m_1 = i$ ， $r_1 = k_1 = i$ ， $n_2 = m + i - 1$ ， $m_2 = i - 1$ ， $r_2 = k_2 = i$ 。

$\sum_{i=0}^{n-1} \sum_{l=0}^{n_1} \binom{n_1-l}{r_1} \binom{m_1+l}{k_1} - \sum_{i=0}^{n-1} \sum_{l=0}^{n_2} \binom{n_2-l}{r_2} \binom{m_2+l}{k_2} \tag{12}$

通过我们对于 $l,n_1,m_1,r_1,k_1,n_2,m_2,r_2,k_2$ 的定义，其实式 $\text{(9)}$ 和式 $\text{(10)}$ 的本质相同。

$\sum_{i=0}^{n-1} \binom{m+i+i}{i+i+1} - \sum_{i=0}^{n-1} \binom{m+i+i-1}{i+i+1} \tag{13}$

通过综合式 $\text{(11)}$ 和式 $\text{(12)}$ 得到式 $\text{(13)}$ ，也就是本题的最终做法。时间复杂度为 $\text{O}(n)$ 。

实现

时间复杂度为 $\text{O}({{n}{m}^{2}})$ ， $\text{O}({n}{m})$ ， $\text{O}({n})$ 的做法都在上文中给出，现在我们讨论一下一些特殊数据点和平凡的做法。

$m = 2$ 及 $3 \leq m \leq 5$

对于 $m = 2$ 的情况，认真思考一下，你就会发现没有不符合条件的序列，所以答案就是所有的序列个数，即 ${n}^{2}$ 。

这两档部分分的设定的本意是提示下一档分数的复杂度是 $\text{O}(n{m}^{2})$ ，也可以通过手玩一些数据找到规律，并且也便于一些不了解组合数学的同学提供一些暴力分数。

$\text{O}({n}^{m})$

这个没什么好说的吧， $dfs$ 暴力构造序列就是了，然后就能拿到签到分。

$O(n\log n)$

本题出现这种奇怪的复杂度只会有两种可能。

如果您还不会再 $\text{O}(n)$ 的复杂度内求出逆元，那么您就完美的错过通过本题的机会。

如果您不会本题的 $\text{O}(n)$ 的做法，但是您发现了式 $(9)$ 的妙处，那么可能存在多项式做法(纯属猜测)

关于公式十一的补充证明（可以忽略）

（证明过程是出题人的思考过程，可能比较繁琐，也可能有更优化的证明方式，这说明出题人很菜）

在“说在前面”一栏中说道的下发文件正是这个公式，我说是可以自行推导，下面我来说推导过程，来证明出题人并非卡公式：

我们来观察原式（把柿子十的 $abc$ 带入）：

$\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \binom{i+j}{i} \binom{m-i+j-1}{m-i-1} - \sum_{i=1}^{m-1} \sum_{j=0}^{n-1} \binom{i+j-1}{i-1} \binom{m-i+j-1}{m-i-1}$

我们令 $F(n, m) = \sum_{i=0}^{m} \sum_{j=0}^{n} \dbinom{i+j}{i} \dbinom{m-i+j}{m-i}$

善于观察的同学应该发现，柿子 $⑩=F(n, m - 1) - F(n, m - 2)$ （把右边那一坨的所有 $i$ 减去 $1$ ），所以现在问题只需要快速求出 $F(n, m)$ 即可

为了方便，我一下称 $\binom{a}{b}$ 中，a为分子，b为分母

至于 $F(n, m)$ ，我们发现i的影响相对较大，所以我们交换枚举顺序： $F(n, m) = \sum_{j=0}^{n}\sum_{i=0}^{m} \dbinom{i+j}{i} \dbinom{m-i+j}{m-i}=\sum_{j=0}^{n}\sum_{i=0}^{m} \dbinom{j+i}{j} \dbinom{m+j-i}{j}$ 。不难发现，对于一个固定的j，分子的和为定值，分母不变

看上去这个柿子就是枚举了前面有多少个数选j个，后面多少个数选j个，理论上应该就是等于 $\dbinom{m + 2 * j}{2 * j}$ 的。

但仔细一想，同一种方案可能会被重复计算！那么会被重复计算多少次呢？对于每一种 $\dbinom{m + 2 * j}{2 * j}$ 所对应的方案，通过手玩几组数据，我们可以发现，他会被重复计算第j个数和第 $j+1$ 个数位置之差次。

举个例子，假设一种方案选择的是： $a_1,a_2, a_3, ……, a_{j}, a_{j+1}, ……, a_{2 * j}$ ，那么这个方案会被计算 $a_{j+1}-a_j$ 次，所以问题转化成，你有 $m+2\times j$ 个数，选择 $2\times j$ 个，问所有方案中 $a_{j+1} - a_{j}$ ，换个思考方式，是不是就相当于在 $a_{j}$ 和第 $a_{j+1}$ 中间再插入一个数呢？

所以 $F(n, m)$ 就很显然了，为 $\dbinom{m + 2 * j + 1}{2 * j+1}$ ，证毕

关于本题生成函数做法：

———— $by\; EmptySoulist$

$Sol:$

还是注意到这个式子：

$\sum_{k=0}^m\sum_{i=0}^n\dbinom{i+k}{k}\dbinom{n+k-i}{k}$

注意到上面的式子的第一项 $(i+k,n+k+1-i)$ 的和恒为定值，他暗示着这个式子是一个卷积。

同时，注意到我们是使用的 $\dfrac{1}{(1-x)^k}$ 的展开式的 $x^i$ 的系数而推得 $\dbinom{i+k}{i}$ ，实际上后面的这个式子本质上均为两个 $OGF$ 展开式的系数，所以回代得到：

$\sum_{k=0}^m\sum_{i=0}^n\dfrac{1}{(1-x)^{k+1}}[x^i]\times \dfrac{1}{(1-x)^{k+1}}[x^{n-i}]$

于是我们的展开式本质上是两个 $OGF$ 卷积的 $x^n$ 次系数，得到原式即：

$\sum_{k=0}^m\dfrac{1}{(1-x)^{2k+2}}[x^n]$

$\sum_{k=0}^m\dbinom{2k+n+2}{n}$

$Code$

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template 
inline T read()
{
    T x=0,f=1;char c=getchar();
    while(!isdigit(c))
    {if(c=='-') f=-f;c=getchar();}
    while(isdigit(c))
    {x=(x<<3)+(x<<1)+(c-48);c=getchar();}
    return x*f;
}
#define lint long long int
#define ulint unsigned lint
const int inf=1e9+1e7;
const int MAXN=15e6+1e1;
const lint Mod=1e9+7;
lint fac[MAXN];
lint inv[MAXN];
lint qpow(lint A,int B)
{
    lint res=1;
    while(B>0)
    {
        if(B&1) (res*=A)%=Mod;
        (A*=A)%=Mod;
        B>>=1;
    }
    return res;
}
lint C(int A,int B)
{
    if(A<0||B<0) return 0;
    else return ( A<B ? 0 : (((fac[A]*inv[B])%Mod)*inv[A-B])%Mod );
}
void print(int m,int n)
{
    lint ans1=0,ans2=0;
    for(int i=0;i<n;i++) (ans1+=C(m+(i<<1),i<<1|1))%=Mod;
    for(int i=0;i<n;i++) (ans2+=C(m+(i<<1)-1,i<<1|1))%=Mod;

    printf("%lld\n",(ans1-ans2+Mod)%Mod);
    return;
}
int main(void)
{
    int t=read();
    int maxn=15e6;
    fac[0]=inv[0]=1;
    for(int i=1;i<=maxn;i++) fac[i]=(fac[i-1]*i)%Mod;
    inv[maxn]=qpow(fac[maxn],Mod-2);
    for(int i=maxn;i;i--) inv[i-1]=(inv[i]*i)%Mod;
    while(t--) print(read(),read());
    return 0;
}

好啦，本场比赛就到此结束了，感谢各位的积极参与！