codeforces 690D2 D2. The Wall (medium)(组合数学)
题目链接:
2 seconds
256 megabytes
standard input
standard output
Heidi the Cow is aghast: cracks in the northern Wall? Zombies gathering outside, forming groups, preparing their assault? This must not happen! Quickly, she fetches her HC2 (Handbook of Crazy Constructions) and looks for the right chapter:
How to build a wall:
- Take a set of bricks.
- Select one of the possible wall designs. Computing the number of possible designs is left as an exercise to the reader.
- Place bricks on top of each other, according to the chosen design.
This seems easy enough. But Heidi is a Coding Cow, not a Constructing Cow. Her mind keeps coming back to point 2b. Despite the imminent danger of a zombie onslaught, she wonders just how many possible walls she could build with up to n bricks.
A wall is a set of wall segments as defined in the easy version. How many different walls can be constructed such that the wall consists of at least 1 and at most n bricks? Two walls are different if there exist a column c and a row r such that one wall has a brick in this spot, and the other does not.
Along with n, you will be given C, the width of the wall (as defined in the easy version). Return the number of different walls modulo106 + 3.
The first line contains two space-separated integers n and C, 1 ≤ n ≤ 500000, 1 ≤ C ≤ 200000.
Print the number of different walls that Heidi could build, modulo 10^6 + 3.
5 1
5
2 2
5
3 2
9
11 5
4367
37 63
230574 题意; 给n个砖,给定了宽c,问你有多少种墙;
这也是[1,n]的按顺序拆分成c个数的种数;也是把[1,n]放在c个盒子里(允许有空盒)的方案数; 思路: dp[n][m]=dp[n][m-1]+dp[n-1][m]+...+dp[0][m]+dp[n-1][m]+dp[n-2][m]+...+dp[1][m];
把n个相同的球放在m个盒子里(允许有空盒)的方案数为C(n+m-1,m-1);
dp[n][m]=C(n+m-1,m-1)=(n+m-1)/n*C(n+m-2,m-1)=(n+m-1)/n*dp[n-1][m];
取模的时候要快速幂求一下逆; AC代码:
#include <bits/stdc++.h>
/*
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
*/
using namespace std;
#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
if(!p) { puts(""); return; }
while(p) stk[++ tp] = p%, p/=;
while(tp) putchar(stk[tp--] + '');
putchar('\n');
} const LL mod=1e6+;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=5e5+;
const int maxn=;
const double eps=1e-; LL n,m,dp[N]; LL pow_mod(LL x,LL y)
{
LL s=,base=x;
while(y)
{
if(y&)s=s*base%mod;
base=base*base%mod;
y>>=;
}
return s;
} void Init()
{
dp[]=;
for(LL i=;i<=n;i++)
{
dp[i]=(dp[i-]*(i+m-)%mod)*pow_mod(i,mod-)%mod;
}
} int main()
{
read(n);read(m);
Init();
LL sum=;
for(LL i=;i<=n;i++)
{
sum=(sum+dp[i])%mod;
}
cout<<sum<<"\n"; return ;
}
最新文章
- OpenCV IplImage FlyCapture2 Image Conversion 两种图像类的相互转化
- 如何将SQL Server 2008库导入2000中
- 【解决】python2.x版本的Django下admin管理页面css无效
- Activity中setResult(int resultCode, Intent data)与onActivityResult(int requestCode, int resultCode, Intent data)方法的调用
- AccessToMySql数据库的导入以及java生成.exe文件
- (四)Lua脚本语言入门
- 通过路由url携带参数进行参数传递
- (一一七)基本文件操作 -SDWebImage清除缓存 -文件夹的大小计算
- Python中的那些“坑”
- java动态代理实现与原理详细分析
- 牛客网 2018年东北农业大学春季校赛 I题 	wyh的物品
- HDU 1284(钱币兑换 背包/母函数)
- 5 -- Hibernate的基本用法 -- 要点
- python3使用csv包,读写csv文件
- 【BZOJ4916】神犇和蒟蒻 解题报告
- SQLSERVER——查看阻塞信息(sp_who_lock优化无误版)
- web编码
- Sybase:SybaseIQ的几个系统过程
- pat1080. Graduate Admission (30)
- visual studio cl -d1reportSingleClassLayout查看内存f分布