HDU HDOJ 3398 String 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3398

题目要我们计算1,0的排列方式总数,并且对任意长的字符串,1的数量大于等于0的数量

我们可以把题目转化为从(0,0)点到(m,n)点的方法总数,且路径不经过y=x-1这条直线

然后我们可以把从(-1,-1)到(m,n)的所有路径按以y=x-1翻转,所得到的路径显然就是经过y=x-1的所有方案

所以最终结论就是C(n+m,n) - C(m+n,m - 1),结果再mod一个20100501就可以了

结论出来但是我这里还WA了很久,因为为了避免减法对mod的影响,我开始把公式化简成了

C(n+m,n) - C(m+n,m - 1) = (m+n)!* (n+1-m) / ((n+1)! * m!)

结果无情的WA掉,而用不化简的组合的减法反而AC,我就莫名了。

最后求教我们的大牛:神奇的ben1222。他帮我看了很久最后发现我的a^b % c的运算中有溢出,但是不化简的式子华丽的没被测试数据发现。然后…

贴代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

const long md = 20100501;

/**
 * a的b次方Mod c
 * 参数为整数
 * 使用时注意修改类型
 */
long PowerMod(long long a,long b,long c)
{
    long long tmpInt = 1;
    while (b > 0)
    {
        if (b & 1)
            tmpInt = (tmpInt * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return tmpInt;
}

/**
 * 线性筛法求素数表
 * 复杂度: O(n)
 */
const long MAXP = 2000005;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
    long i, j;
    for(i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++] = i;
        for(j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))
                break;
        }
    }
}

/**
 * 排列组合数(素数表示法)
 */
// 全排列
// 参数: A(n), *p 传出数的数组表示指针
// 返回值:结果包含的素数个数
long Arrangement(long n, long p[])
{
    long t, i;
    for(i = 0; i < num_prime && prime[i] <= n; i ++)
    {
        t = n;
        while(t)
            *(p + i) += t / prime[i], t /= prime[i];
    }
    return i;
}

long numRec[3][MAXP / 10];
//long numRec[MAXP / 10];
int main()
{
    long t,n,m,r,i;
    long tmp;
    long long res;
    GetPrime_Init();
    scanf("%ld", &t);
    while(t --)
    {
        cin>> n>> m;
        res = 1;
        memset(numRec, 0, sizeof(numRec));
        r = Arrangement(m + n, numRec[0]);
        Arrangement(n + 1, numRec[1]);
        Arrangement(m, numRec[2]);
        //res = (((m + n)! * (n + 1 - m)) / ((n + 1)! * m!)) % md;
        tmp = n + 1 - m;
        for(i = 0; tmp > 1 && i < num_prime && prime[i] <= tmp; i ++)
            while(tmp > 1 && tmp % prime[i] == 0)
                numRec[0][i] ++, tmp /= prime[i];

        for(i = 0; i <= r; i ++)
            res = (res * PowerMod(prime[i], numRec[0][i] - numRec[1][i] - numRec[2][i], md)) % md;


        printf("%lld\n", res);
    }
    return 0;
}

PS:我们神奇的ben1222的博客是WordPress的诶,忍不住贴一下:http://www.ben1222.com/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

28. 搜索二维矩阵二分法

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性: 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 样例...

16020
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

454100
来自专栏null的专栏

挑战数据结构和算法——栈的push、pop序列

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判...

33760
来自专栏数据小魔方

字符串提取函数

今天要跟大家分享三个excel中使用频率最高的字符串提取函数——left/right/mid函数。 ▽▼▽ 这三个函数分别对用截取某一单元格文本的左、右、中间某...

36550
来自专栏数据结构与算法

洛谷P3807 【模板】卢卡斯定理exgcd

题目背景 这是一道模板题。 题目描述 给定n 求  保证P为prime C表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式: 第一行...

39160
来自专栏用户2442861的专栏

awk工作常用技巧

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

9620
来自专栏机器学习算法与Python学习

Numpy

Numpy Numpy是Python中用于科学计算的核心库。它提供了高性能的多维数组对象,以及相关工具。(本文文末的原文链接为numpy的官方文档) NumPy...

35070
来自专栏C/C++基础

迷宫问题(maze problem)——深度优先(DFS)与广度优先搜索(BFS)求解

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

1.8K20
来自专栏程序生活

Python 中argparse模块的使用

如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

7700
来自专栏数据结构与算法

2806 红与黑 个人博客:doubleq.win

个人博客:doubleq.win 2806 红与黑  时间限制: 1 s  空间限制: 64000 KB  题目等级 : 白银 Silver 题解  查看运行结...

29640

扫码关注云+社区

领取腾讯云代金券