1
21
2016
0

【bzoj4403】序列统计

4403: 序列统计

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 94  Solved: 39
[Submit][Status][Discuss]

Description

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。

Input

输入第一行包含一个整数T，表示数据组数。第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。

Output

输出包含T行，每行有一个数字，表示你所求出的答案对106+3取模的结果。

Sample Input

2
1 4 5
2 4 5

Sample Output

2
5

HINT

 

提示

【样例说明】满足条件的2个序列为[4]和[5]。

【数据规模和约定】对于100%的数据，1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

 

Source

By yts1999

利用可重复的组合，可以推得方案数为C（n，n+r-l+1）-1。然后就用一下lucas定理就可以了。

附：lucas定理：C(m,n)%p=C(m/p,n/p)*C(m%p,n%p)。

代码：

 

#include<cstdio>
#define mod 1000003
using namespace std;
typedef long long ll;
int T;
ll n,L,R,fac[1000010];
ll ksm(ll x,ll y)
{
    ll ans=1;
    while (y)
    {
        if (y%2) ans=ans*x%mod;
        x=x*x%mod;
        y/=2;
    }
    return ans;
}
ll c(ll m,ll n)
{
    if (n<m) return 0;
    ll ans=fac[n];
    ans=ans*ksm(fac[m],mod-2)%mod;
    ans=ans*ksm(fac[n-m],mod-2)%mod;
    return ans;
}
ll lucas(ll m,ll n)
{
    if (!m) return 1;
    return lucas(m/mod,n/mod)*c(m%mod,n%mod);
}
int main()
{
    scanf("%d",&T);
    fac[0]=1;
    for (int i=1;i<=mod;i++) fac[i]=fac[i-1]*i%mod;
    while (T--)
    {
        scanf("%lld%lld%lld",&n,&L,&R);
        printf("%lld\n",(lucas(n,n+R-L+1)+mod-1)%mod);
    }
}
Category: 数学 | Tags:
12
19
2015
0

【bzoj1856】【Scoi2010】字符串

1856: [Scoi2010]字符串

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1118  Solved: 598
[Submit][Status][Discuss]

Description

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

Input

输入数据是一行，包括2个数字n和m

Output

输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

2

HINT

【数据范围】

对于30%的数据，保证1<=m<=n<=1000

对于100%的数据，保证1<=m<=n<=1000000

这是道好题啊。

我们先转化一下模型，我们先建一个平面直角坐标系，原点为（0,0），若当前位置选1，就横坐标加一，纵坐标加一，否则横坐标加一，纵坐标减一。由题意，目标点为（n+m，n-m），且不能到y=0以下的部分。所以，我们只要总方案数减去经过y=-1的方案数，易知总方案数为C（n+m，n）。

现在我们来讨论经过y=-1的方案数。

我们将第一次与y=-1的点的左边部分关于y=-1对称，最后方案数就等价于从（0，-2）走到（n+m，n-m）的方案数，我们设向上走了x步，向下走了y步，方案数即为（x+y，x),又x+y=n+m,x-y=n-m+2，解得x=n+1，y=m-1。

是不是感觉这方法很精妙啊，我也这么觉得啊。

代码：

 

#include<cstdio>
using namespace std;
typedef long long ll;
ll n,m,ans,mod=20100403;
ll ksm(ll x,ll y)
{
	ll ans=1;
	while (y)
	{
		if (y&1) ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
ll calc(ll x,ll y)
{
	ll sum1=1,sum2=1,sum3=1;
	for (ll i=1;i<=x;i++)
		sum1=sum1*i%mod;
	for (ll i=1;i<=y;i++)
		sum2=sum2*i%mod;
	for (ll i=1;i<=x-y;i++)
		sum3=sum3*i%mod;
	sum1=sum1*ksm(sum2,mod-2)%mod;
	sum1=sum1*ksm(sum3,mod-2)%mod;
	return sum1;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	ans=(calc(n+m,n)-calc(n+m,n+1)+mod)%mod;
	printf("%lld\n",ans);
}
Category: 数学 | Tags:
12
14
2015
0

【JSOI2015】染色问题

容斥原理，我们枚举选i行，选j列，选k中颜色，我们强行让i行以外，j列以外的所有点不能被涂色，那么，只有i*j个格子可以涂色，注意，是可以涂色，也可以不涂色。所以我们的答案就是sigma(c(n,i)*c(m,j)*c(c,k)*(-1)n+m+c-i-j-k*(k+1)i*j)(0<=i<=n,0<=j<=m,0<=k<=c),这样是n3的，能过的。若要log优化，详见Gold_7博客：http://gold7.is-programmer.com/

代码：

 

#include<cstdio>
#include<algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
int n,m,c;
ll p[410][160010],C[410][410],ans;
int main()
{
	scanf("%d%d%d",&n,&m,&c);
	for (int i=0;i<=max(max(n,m),c);i++)
		C[i][0]=1;
	for (int i=1;i<=max(max(n,m),c);i++)
		for (int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for (int i=1;i<=c+1;i++)
	{
		p[i][0]=1;
		for (int j=1;j<=n*m;j++)
			p[i][j]=p[i][j-1]*i%mod;
	}
	for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
			for (int k=0;k<=c;k++)
			{
				ll sum=C[n][i]*C[m][j]%mod*C[c][k]%mod*p[k+1][i*j]%mod;
				if ((n+m+c-i-j-k)%2) ans=(ans-sum+mod)%mod;else ans=(ans+sum)%mod;
			}
	printf("%lld\n",ans);
}
Category: 数学 | Tags:
12
8
2015
0

【JSOI2015】非诚勿扰

我们很容易想到的算法n4，枚举任意两个女该，算出她们对答案的贡献，因此再枚举每个人选的男孩，算出选这个男孩的概率，两者相乘就是贡献。选这个男孩的概率，就是这个男孩的概率除以选所有男孩的概率之和。

假如我们现在要求a这个女孩在共n个候选人中选第k个男孩（就是候选人从小到大第k个）的概率。

分子=(1-p)k-1*p+(1-p)k-1*p*(1-p)n+(1-p)k-1*p*(1-p)2n+……+(1-p)k-1*p*(1-p)oo

=(1-p)k-1*p*(((1-p)oo-1)/(-p))

=(1-p)k-1

多么完美的一个数啊！！

分母=（1-p)0+(1-p)1+(1-p)2+……+(1-p)n-1

=((1-p)n-1)/(-p)

这样就求出了第a个女孩选第k个男孩的概率。

有了这些精妙的公式，就很容易优化到了n2。

接下来的优化很明显，先将读入的a排序，再用数据结构（如树状数组，线段树）去维护前缀和就可以了。

代码：

 

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,sum[500010],cnt,num[500010];
double p,q[500010],tr[500010],ans;
struct node{int a,b;}pai[500010];
bool cmp(const node x,const node y){if (x.a==y.a) return x.b<y.b;return x.a<y.a;}
void add(int x,double val)
{
    while (x<=n)
    {
        tr[x]+=val;
        x+=((x)&(-x));
    }
}
double ask(int x)
{
    if (!x) return 0;
    double ans=0;
    while (x)
    {
        ans+=tr[x];
        x-=((x)&(-x));
    }
    return ans;
}
double ksm(double x,int y)
{
    double ans=1;
    if (!y) return ans;
    while (y)
    {
        if (y&1) ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%lf",&p);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&pai[i].a,&pai[i].b);
        sum[pai[i].a]++;
    }
    sort(pai+1,pai+m+1,cmp);
    for (int i=1;i<=m;i++){if (pai[i].a!=pai[i-1].a) cnt=0;num[i]=++cnt;}
    for (int i=1;i<=n;i++)
    if (sum[i]) q[i]=(ksm(1-p,sum[i])-1)/(-p);
    for (int i=m;i>=1;i--)
    {
        ans+=ksm(1-p,num[i]-1)/q[pai[i].a]*ask(pai[i].b-1);
        add(pai[i].b,ksm(1-p,num[i]-1)/q[pai[i].a]);
    }
    printf("%.2lf\n",ans);
}
Category: 数学 | Tags:
12
1
2015
0

【JSOI2015】子集选取

结论题。

手算一下小数据，就可以轻松得到一个结论，然后大样例就过了，然后。。。就A了

结论为：2n*k

代码：

 

#include<cstdio>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,k;
ll ksm(ll x,ll y)
{
	ll ans=1;
	while (y)
	{
		if (y%2==1) ans=ans*x%mod;
		x=x*x%mod;
		y=y/2;
	}
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	printf("%lld\n",ksm(2,n*k));
}
Category: 数学 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com