zcmimi's blog

arrow_back组合数共15篇文章

avatar
zc
2020-03-11 00:41:00
查看原题

点击跳转

给出n,m{n+m} \choose m

avatar
zc
2020-03-10 22:33:00
查看原题

点击跳转

题意:

G^{\sum d|{N\choose d}}\bmod 999911659

1 \le G \le 10^9,1 \le N \le 10^9

999911659是质数,根据欧拉定理:

G^{\sum d|{N\choose d}}\bmod 999911659 = G^{\sum d|{N\choose d} \bmod 999911658}\bmod 999911659

关键求\sum d|{N\choose d} \bmod 999911658

模数太大,直接lucas取模会炸

我们可以考虑将模数分解质因数

999911658=2\times 3 \times 4679 \times 35617

可以用lucas枚举约数算出

\begin{cases} a_1=\sum d|{N\choose d} \pmod 2 \\ a_2=\sum d|{N\choose d} \pmod 3 \\ a_3=\sum d|{N\choose d} \pmod {4679} \\ a_4=\sum d|{N\choose d} \pmod {35617} \end{cases}

然后通过crt求:

\begin{cases} x \equiv a_1 \pmod 2 \\ x \equiv a_2 \pmod 3 \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_4 \pmod {35617} \end{cases}

avatar
zc
2019-12-31 20:01:00
查看原题

点击跳转

分类讨论:

Tarjan跑出割点,然后DFS搜索所有的联通快

计算每一个联通快中的割点数目

分类讨论:

  1. 没有割点

    至少需要建立两个出口

    从任意非割点的地方选择两个点建立

  2. 这个分组只有一个割点

    只需要在分组内设立一个出口

    可以设立在任意一个非割点的地方

  3. 有两个及以上个割点,则无需建立,可以直接到达其他联通块

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_{i=1}^k a_i = x^x \mod 1000 (a_i \in \N^*)

\because 总和一定为x^x \mod 1000,并且分为k个数,

n = x^x \mod 1000

这样相当于在n-1个空位中插k-1块隔板

\therefore ans = C(n-1,k-1)

\because k \le 100,n\le 1000

\therefore我们用杨辉三角(用滚动数组,否则可能re)就可以了,但是要高精度

当然如果直接计算组合数更快

杨辉三角版:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

这个题解棒棒哒

答案就是C(n+m,m)-C(n+m,m-1)

2/2
Search
search