注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 573 Div1  

2013-04-08 16:57:47|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实比较无聊吧。。。做SRM真的是纯粹的去颓废啊。。。250和500分的题做了一个晚上。。。
怎么讲呢,850分的题目还是很神的,反正我是不会做。
点(0,0)到(x,y),每次只能往上往下往左往右移动1,走m步,求方案数。
真心不会做啊。。。然后果断去看题解,题解用了一个很巧妙的方法——
用(x+y,x-y)替代了(x,y),那么每次都是将横坐标变化1,纵坐标变化1。。这有什么好处呢?横纵坐标分离了,完全不相干!!所以就可意暴枚然后组合数计算了
我想之所以优化了复杂度大概是利用了方程的一些不变性吧,也没有太细想了,只觉得很神奇

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

struct WolfPack
{
const static int Mod=1000000007;
const static int MAXX=300002;
int C[MAXX];

LL power(LL a,LL b)
{
LL k=1;
for(;b;b/=2,a=a*a%Mod)
if(b%2==1)
k=k*a%Mod;
return k;
}

int solve(vector<int> a,int m)
{
int ans=0,x,i;
REP2(x,-MAXX,MAXX)
{
LL tot=1;
REP2(i,0,a.size())
{
int d=abs(a[i]-x);
//x-y=d
//x+y=m
//2*x=(m+d)/2
if( d>m || (m+d)%2==1 )
tot=0;
else
tot=tot*C[(d+m)/2]%Mod;
}
ans+=tot;
if(ans>=Mod)
ans-=Mod;
}
return ans;
}

int calc(vector<int> x, vector<int> y,int m)
{
int i;
REP2(i,0,x.size())
{
int a=x[i];
int b=y[i];
x[i]=a+b;
y[i]=a-b;
}
fill(C,C+MAXX,0);
C[0]=1;
REP(i,1,m)
C[i]=(LL)C[i-1]*(m-i+1)%Mod*power(i,Mod-2)%Mod;
return (LL)solve(x,m)*solve(y,m)%Mod;
}
};




  评论这张
 
阅读(175)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017