前言:

跟着大佬上分不愁

我等蒟蒻又被吊打啦!

OrzImmortals

ARC 058

C - こだわり者いろはちゃん / Iroha's Obsession

题意

给定数字N,K,和K个数字$D_i(0\le D_i \le 9)$,求一个最小数C$(C\ge N)$使得C在十进制下各个位上没有出现D中的数字。

方法

感觉不太难,应该是从高位向低位推,如果有冲突的数字就把前几位(十进制表示下)扩大使得这几位没有出现冲突的数字,后面的变成0即可。

然而看神仙题解,

考虑直接暴力枚举, 如果符合条件直接输出就好了

好吧够直接,暴力美学。。。

正解本人不会打,溜了溜了。

D - いろはちゃんとマス目 / Iroha and a Grid

正经题目来了

题意

有一个$H\times W$的矩阵,只能向右/向下走,问不经过左下角$A\times B$的矩阵的路径数。

题解

思路

首先复习预习一波组合数学计算无限制的路径数。假设我们有一个$n\times m$的矩阵,从$(1,1)$到$(n,m)$的路线总会走过$n+m-2$个点,而其中纵向移动的有$n-1$步,所以总路径数即为从$n+m-2$步中选$n-1$步的方案数,即$$\dbinom{n+m-2}{n-1}$$

再来考虑有障碍的情况:

source:官方题解pdf

如图,我们把图分成两部分来看,可通过部分以$H-A-1,H-A$为分界线分成了上下两个矩形。显然所有的路径都经过$(H-A-1,i),(H-A,i)~~(i\in [W-B,W])$,因此总方案数=经过分界线上每个点的方案数之和。

根据乘法原理即为$$\sum_{i=B+1}^{i\le W}{\dbinom{(H-A)+i-2}{(H-A)-1}\cdot \dbinom{A+(W-B)-2}{A-1}}$$

代码
#include<bits/stdc++.h>
#define mul(x,y) (((x)%P*(y))%P)
#define pls(x,y) ((x)%P+(y))%P
using namespace std;
const long long P=1e9+7;
const int N=100020;
long long qpow(long long x,long long k)
{
    long long rt=1,base=x;
    while(k)
    {
        if(k&1)rt=mul(rt,base);
        base=mul(base,base),k>>=1;
    }return rt;
}
int fac[N*2];
long long solve(int h,int w)
{
    long long rt=0;
    rt=fac[h+w-2];
    rt=mul(rt,mul(qpow(fac[h+w-2-h+1],P-2),qpow(fac[h-1],P-2)));
    return rt;
}
int main()
{
    int H,W,A,B;
    long long ans=0;
    scanf("%d%d%d%d",&H,&W,&A,&B);
    fac[0]=1;for(int i=1;i<=H+W-2;i++)fac[i]=mul(fac[i-1],i);
    for(int i=B+1;i<=W;i++)
        ans=pls(ans,mul(solve(H-A,i),solve(A,W-i+1)));
    cout<<ans;
    return 0;
}