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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 554 DIV1  

2012-09-02 02:03:43|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
rank66
比预期的要好,rating一路涨成1864
难道我会告诉你我写了前两题后一直在颓废吗?

1000分的题总算写好了,用的是最简单的距乘,卡了常数才过(关键在于取模)
其他的就不说了
想了想其实废状态还是有很多,可以从对称性下手优化

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
#include<ctime>
using namespace std;

typedef long long LL;
const LL Mod=1234567891;
const int NUM=10;

LL C,K,H;

struct state
{
int num[4];
void print()
{
int i;
for(i=0;i<4;++i)
printf("%d ",num[i]);
printf("\n");
}
};

int operator < (const state& a,const state& b)
{
int i;
for(i=0;i<4;++i)
if(a.num[i]!=b.num[i])
return a.num[i]<b.num[i];
return 0;
}

vector<state> st;
map<state,int> lab,sames,uu;
map< pair<int,int> ,int> cc;

void dfs1(int dep,int u,state now)
{
if(dep==4)
{
int same=0;
if(now.num[0]==now.num[1])++same;
if(now.num[0]==now.num[2])++same;
if(now.num[1]==now.num[3])++same;
if(now.num[2]==now.num[3])++same;
st.push_back(now);
lab[now]=(int)st.size();
uu[now]=u;
sames[now]=same;
return;
}
int i;
for(i=1;i<=u;++i)
{
now.num[dep]=i;
dfs1(dep+1,u,now);
}
now.num[dep]=u+1;
dfs1(dep+1,u+1,now);
}

state getstate(int* num)
{
int u=0,i,j,flag;
state now;
for(i=0;i<4;++i)
{
flag=0;
for(j=0;j<i;++j)
if(num[i]==num[j])
{
flag=1;
now.num[i]=now.num[j];
break;
}
if(!flag)
{
++u;
now.num[i]=u;
}
}
return now;
}

int n;

const int MAX=130;

LL ddd;
void mult (LL g[MAX][MAX],LL b[MAX][MAX])
{
LL c[MAX][MAX];
memset(c,0,sizeof c);
int i,j,k;
LL d=Mod*Mod;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
{
c[i][j]+=g[i][k]*b[k][j];
if(c[i][j]>d)
c[i][j]-=d;
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
g[i][j]=c[i][j]%Mod;
}
void print(LL g[MAX][MAX])
{
int i,j;
for(i=1;i<=n;++i,cout<<endl)
for(j=1;j<=n;++j)
cout<<g[i][j]<<" ";
}

LL begin[MAX][MAX];

int change(int a,int b)
{
if(!cc[make_pair(a,b)])
cc[make_pair(a,b)]=++n;
return cc[make_pair(a,b)];
}

LL power1(LL a,LL b)
{
LL k=1,c=a;
while(b)
{
if(b%2==1)
k=k*c%Mod;
c=c*c%Mod;
b/=2;
}
return k;
}

LL CCn(LL tot,LL C)
{
LL ans=1,p=C;
while(tot)
{
ans=ans*p%Mod;
--p;
--tot;
}
return ans;
}

void get(int* num,int mm)
{
int i,count=0;
state p=getstate(num),q=getstate(num+4);

if(sames[p]>K || uu[p]>C)return;
if(sames[q]>K || uu[q]>C)return;

for(i=0;i<4;++i)
if(num[i]==num[i+4])
++count;
if(count+sames[p]+sames[q]>K)
return;
int dd=0,ee=0;
for(i=0;i<4;++i)
{
dd=max(dd,num[i]);
ee=max(ee,num[i+4]);
}
if(ee>C)return;
LL pp=CCn(max(ee-dd,0),max(C-dd,(LL)0));
if(!pp)
return;
for(i=sames[p];i+count+sames[q]<=K;++i)
{
LL & kk=begin[change(lab[q],i+count+sames[q])][change(lab[p],i)];
kk=(kk+pp)%Mod;
}
}

void dfs2(int u,int* num,int mm)
{
if(u==8)
{
get(num,mm);
return;
}
int i;
for(i=1;i<=mm;++i)
{
num[u]=i;
dfs2(u+1,num,mm);
}
num[u]=mm+1;
dfs2(u+1,num,mm+1);
}

void power(LL k[MAX][MAX],LL a[MAX][MAX],LL b)
{
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
k[i][j]=0;
for(i=1;i<=n;++i)
k[i][i]=1;
while(b)
{
if(b%2==1)mult(k,a);
mult(a,a);
b/=2;
}
}

struct TheBrickTowerHardDivOne
{
int find(int CC,int KK,LL HH)
{
C=CC;K=KK;H=HH;
n=0;
dfs1(0,0,state());
int num[NUM],i;
dfs2(0,num,0);

for(i=0;i<15;++i)
if(sames[st[i]]<=K && uu[st[i]]<=CC)
change(i+1,sames[st[i]]);
++n;
for(i=0;i<15;++i)
if(sames[st[i]]<=K && uu[st[i]]<=CC)
{
begin[change(i+1,sames[st[i]])][n]=CCn(uu[st[i]],C);
}
begin[n][n]=1;
LL ans[MAX][MAX];
power(ans,begin,HH);
LL answer=0;
for(i=1;i<n;++i)
answer=(answer+ans[i][n])%Mod;
return (int)answer;
}
};



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

历史上的今天

评论

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

页脚

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