Tag-组合数

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-10-12 15:07:44 |  0 Comments  |  NTT 数学 组合数 生成函数

HAOI2018 染色 NTT 组合数 生成函数

图片标题

题解

首先声明……其实我们的答案跟Wi没太大关系,这一部分只需要在最后的时候对应乘上即可,此题最核心的部分是计算选择了i种颜色的方案数。
首先我们来看如果我们选择了i种颜色使它们恰好出现了S次,那么选择颜色种类的方案数即为Cmi,然后我们去用这i个颜色涂这n个位置的时候,实际上就是一个可重排列的计算数,方案总数为n!(S!)i(niS)!,然后剩下的位置任意涂色,一共还剩n-i*S个位置,每个位置有m-i种颜色选择,所以方案数为(mi)niS
我们记fi=Cmin!(S!)i(niS)!(mi)niS
然而这并不是恰好有i种颜色恰好都出现k次。实际上在我们在后面自由涂色的时候,我们依旧有可能会将一种颜色涂成恰好出现k次。
So……这时候我们就用到容斥原理了。假设ansi为恰好i种颜色都恰好出现k次,由容斥原理有:
ansi=j=imin(m,n/S)(1)jiCjifjj

 2019-10-12 15:06:43 |  0 Comments  |  NTT 数学 组合数

HAOI2018 染色 NTT 组合数

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxm = 1e5+5;
const int maxn = 1e7+5;
typedef long long ll;
const ll mod = 1004535809;
ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn];
ll b[maxm<<2];
int rev[maxm<<2];
void init(int x){
    fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1ll;
    for(int i = 2;i <= x;++i){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
    return;
}
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b){
        if(b & 1)
            ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}
ll g;
int len,lg;
void NTT_init(int k){
    len = 1;lg = 0;
    for(len = 1;len < k;len <<= 1,lg++);
    for(int i = 0;i < len;++i)
        rev[i] = (rev[i>>1]>>1) | ((i & 1) << (lg - 1));
}
void NTT(ll *a,int len,int f){
    for(int i = 0;i < len;++i){
        if(i < rev[i])
            swap(a[i],a[rev[i
 2017-01-23 22:21:38 |  0 Comments  |  组合数 高精度

清北省选模拟赛 T1 积水 ——组合数+高精度

                                            积水

问题描述

       清北学堂某幢楼的屋顶上要安装一根横梁,其横截面是一个有N个顶点的直角多边形,也就是说,多边形是每个内角不是90°就是270°,将多边形放入直角坐标系中,它的每条边都与坐标轴平行。为了减轻承重,横梁不能出现在下雨天积水的情况,而且由于施工队不靠谱,横梁的安放角度是不确定的,所以需要保证横梁在被转了0°、90°、180°和270°时都不会积水。例如,图1和图2 的横截面都表示了一根合法的横梁,但图3和图4就显然不合法了。

          图1                          图2                       图3                           图4


       现在,给出直角多边形的顶点数N,求有多少个长度为N的01序列对应了某种合法的横梁横截面。

输入格式

       一行1个整数N。

输出格式

       一行1个整数,表示满足要求的01序列数量。

样例输入

6

样例输出

6

数据范围

对于10%的数据,n<=15;

对于30%的数据,n<=50000;

对于50%的数据,n<=106

对于100%的数据,n<=1010000

题解

省选模拟赛完挂,感觉自己吃枣药丸。。。

这是我省选模拟唯一做出来的题(做了3个小时,高精度调了老长时间,感觉自己码力巨弱,连普及组的选手都快不如了)……

不多说,看这道题的性质。

数据是1010000啊,所以这道题一定有什么性质……

我们枚举序列,注意到如果有两个以上的0连续出现(哪怕是一个在开头一个在结尾),这样的序列一定是不合法的,这是第一条性质。

第二个注意到,90度的角(个数记为x)和270的角(个数记为y)对整个多边形的贡献(总角度)一定满足多边形内角和公式180°(n-2),化简后即x+3y=2(n-2);并且x+y=n。所以我们在这里得到了什么?一个二元一次方程组!也就是说,对于某个确定的n,其多边形中的x和y一定是唯一确定的。

这两条性质对我们解这道题产生了极大的帮助。

然后我们开始列限制条件:

            1.首先根据第二个性质,我们知道,x=n/2+2,y=n/2-2,x-y=4.

            2.根据第二个性质,我们很容易得到,考虑合法的方案而不是不合法的方案才

Title - Artist
0:00