61.187.179.132:8080/JudgeOnline/showproblem
额。。水题直接上矩阵乘法。。
由于m比较小实际上没必要用KMP算法算出原始矩阵的，不过我乘机学习了一下KMP算法囧。。
还有就是我昨天一直在调我那个QTREE的程序。。到现在都没有调好。。我真是太菜了555.
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxm=20;
int n,m,mod,A[maxm],next[maxm+1];
struct Mat
{
int M[maxm][maxm];
Mat(){memset(M,0,sizeof(M));}
void operator=(const Mat&o)
{memcpy(M,o.M,sizeof(M));}
int& operator()(int i,int j){return M[i][j];}
Mat operator*(Mat&o)
{
Mat T;
rep(i,m)rep(j,m)rep(k,m)T(i,j)+=M[i][k]*o(k,j),T(i,j)%=mod;
return T;
}
}orig;
Mat Power(int n)
{
if(n==1) return orig;
Mat tmp=Power(n/2);
tmp=tmp*tmp;
if(n&1) tmp=tmp*orig;
return tmp;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m>>mod;char x;
rep(i,m) cin>>x,A[i+1]=x-‘0’;
next[1]=0;int t=0;
for(int i=2;i<=m;i++)
{
while(t>0&&A[t+1]!=A[i]) t=next[t];
if(A[t+1]==A[i])++t;
next[i]=t;
}
for(int i=0;i<m;++i)
{
rep(j,10)
{
int t=i;
while(t>0&&A[t+1]!=j)t=next[t];
if(A[t+1]==j)++t;
orig(t,i)++;
}
}
Mat ans=Power(n);int Ans=0;
rep(i,m) Ans+=ans(i,0),Ans%=mod;
cout<<Ans<<endl;
}

61.187.179.132:8080/JudgeOnline/showproblem
这道题很有意思啊。。就是说一棵树对一些顶点的度数有要求一些没有，让你求这样的树的度数。
我一开始想DP脑子都爆了也没想出来。。最后想到Prufer Code。。然后就明白了。。
Prufer Code是把每棵n点的树对应到长度为n-2，数在1-n之间的数列。。其中一个度数为d的点出现d-1次。。
wiki上的说明:en.wikipedia.org/wiki/Prufer_code
这就是关键。所以问题就转化成求这样的数列的数目了。。这用多重集的公式很方便，就不多说了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000;
int n;
vector<int> Prime;
typedef vector<int>::iterator it;
int D[maxn],S=0,noLimit=0;
bool isPrime(int x)
{
if(x==2) return true;
if(x/2==0) return false;
for(int i=3;i*i<=x;i+=2)
if(x%i==0) return false;
return true;
}
void getPrime()
{
for(int i=2;i<=n;i++)
if(isPrime(i)) Prime.pb(i);
}
void init()
{
cin>>n;
rep(i,n)
{
cin>>D[i];
if(D[i]>0)
S+=D[i]-1;
else
noLimit++;
}
}
struct BigInt
{
int H[400];
BigInt(){memset(H,0,sizeof(H));}
void mul(int x)
{
rep(i,Prime.size())
while(x%Prime[i]==0) x/=Prime[i],H[i]++;
}
void div(int x)
{
rep(i,Prime.size())
while(x%Prime[i]==0) x/=Prime[i],H[i]–;
}
};
ostream& operator<<(ostream&out,const BigInt&x)
{
static int Hp[100000],last;
memset(Hp,0,sizeof(Hp));Hp[last=0]=1;
rep(i,Prime.size())
{
rep(j,x.H[i])
{
int o=Prime[i],d=0;
rep(k,last+1)
{
d+=Hp[k]*o;
Hp[k]=d%10;
d/=10;
}
while(d) Hp[++last]=d%10,d/=10;
}
}
for(int i=last;i>=0;–i)out<<Hp[i];
return out;
}
void work()
{
if(S>n-2){cout<<0<<endl;return;}
if(noLimit==0&&S<n-2){cout<<0<<endl;return;}
getPrime();
BigInt ans;
for(int i=1;i<=n-2;i++)
ans.mul(i);
rep(i,n)
{
if(D[i]>0)
for(int j=1;j<=D[i]-1;j++)
ans.div(j);
}
for(int i=1;i<=n-2-S;i++)
ans.div(i);
rep(i,n-2-S) ans.mul(noLimit);
cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
init();
work();
}
PS。。o(︶︿︶)o 这个OJ不能用Java。还得自己写高精度囧。。

额。。这两天我的胃罢工了。。难过4了。。今天抱着别被淘汰就行的心理参加了这个比赛囧。。
比赛前狂灌咖啡。。感觉好多了。。
第一题是水题啊。是水题啊。
第二题真BT啊，真BT。。
一开始我很想啊，这个要分类讨论啊。。然后我脑海里就浮现出200行+的代码和密密麻麻的公式。。囧了一下。。然后想是不是把这个东西摊开来啊。然后写了一会儿。囧掉了。写不出来。。最后没办法了。。突然想到似乎可以bfs。。然后又想如何表示6个面。。纠结了半天。。只好又灌咖啡。。最后豁出去了。干脆开3维数组得了。。结果居然过了。。其实我那个程序好像有个bug总觉得哪个地方搞错了。。不过居然Pass System Test了。真是奇迹额。。
第三题去死吧。去死吧。。
我想到上次USACO的月赛。然后感觉要离散化，然后离散化的时候把角要切出来，之后开个数组递推出每个其他的方格是否是白的？现在感觉好像是这么做的，不过比赛的时候没想到。我的第一反应是绕圈儿。。
因为这个图形本质上好像就是一圈东西囧。。
然后好不容易写了个绕圈的程序。。发现不知道怎么算面积囧。。然后我就撞死了。。
掉Rating了。。

今天两个比赛之间一秒钟都没有。。一连码了5个小时。。脑子小了囧。。
题目见官网。。
www.hsin.hr/coci/
第一题第二题纯水题。。忽略它们吧。。
第三题就是去重么，注意旋转就可以了。。
第四题我写了个dfs。好像写错了。。只有10分囧。。
第五题其实比第四题简单，对于每种jump一起上，那么每个数最多1次，总共也就是nlogn的。。
第六题太BT了。。我看了就晕。。
额。。这次比上次好点。。280分。。
我这个人一做到烦的题目就晕。。

囧。。其实这玩意等价于分空间的问题，设维数为d魔法n次为dp(d,n)
则dp(d,n)=dp(d-1,n-1)+dp(d,n-1)
dp(1,i)=2*i
dp(i,0)=1
。。。我一开始是解了个方程。因为我发现结果是d次函数，并且前d+1个值都是2的幂，
所以可以解出系数然后计算囧。。写了半天。真是沙茶到家了555
HNOI2006A了5道。。剩下的就不会做了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=100+1,maxd=16;
int n,d;
long long dp[maxd][maxn]={0};
int main()
{
cin>>n>>d;
rep(i,n+1)dp[1][i]=i*2;dp[1][0]=1;
for(int i=2;i<=d;i++)
{
dp[i][0]=1;
for(int j=1;j<=n;j++)
dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
}
cout<<dp[d][n]<<endl;
}

61.187.179.132:8080/JudgeOnline/showproblem
看似水题。。其实不是很水（应该是我太菜了囧。。）
之前想了几种算法都是错的。。就不说了。最后的算法是二分最大值。并用并查集帮忙(*^__^*)
然后首先扫描一遍所有的边，能够建一号公路的就建一号公路。扫描的话如果k没达到，就是false
然后再扫描一遍所有的边，把能建的二号公路也建上去。判断一下是否联通的就OK了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=10000;
int n,k,m;
struct Data
{
int s,t,c1,c2;
void operator()(int _s,int _t,int _c1,int _c2)
{s=_s;t=_t;c1=_c1;c2=_c2;}
}E[maxn*2];
int F[maxn];
int find(int x)
{
if(F[x]==x) return x;
return F[x]=find(F[x]);
}
int Union(int i,int j){F[j]=i;}
bool check(int limit)
{
int cnt=n,r=k;
rep(i,n) F[i]=i;
for(Data*i=E;i!=E+m;i++)
{
if(i->c2<=limit)
{
int a=find(i->s),b=find(i->t);
if(a!=b) Union(a,b),–cnt,–r;
}
}
if(r>0) return false;
for(Data*i=E;i!=E+m;i++)
{
if(i->c1<=limit)
{
int a=find(i->s),b=find(i->t);
if(a!=b) Union(a,b),–cnt;
}
if(cnt==1) return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>k>>m;int s,t,c1,c2;
rep(i,m)
{
scanf("%d %d %d %d",&s,&t,&c2,&c1);
E[i](s-1,t-1,c1,c2);
}
int l=0,r=30000;
while(l+1<r)
{
int m=(l+r)/2;
if(check(m))
r=m;
else
l=m;
}
cout<<r<<endl;
}

囧。。什么水题。。
61.187.179.132:8080/JudgeOnline/showproblem
Code:
n,d=0;main(){scanf("%d",&n);while(1<<d<=n)d++;printf("%d",d);(*^__^*) 最快+最短。。我真是无聊。

61.187.179.132:8080/JudgeOnline/showproblem
数据那么大暴搜只能去死。。
我想先贪心的跳一会，当距离比较近的时候再暴搜。
我一开始想的贪心是直接按距离。。结果WA。。
然后我编数据找原因。。发现对于那些正方形两个对角点比如0 0 100 100的数据错的很厉害。。
然后我感觉似乎是因为这样贪心的话一开始就会往边上跳。。不顾后来的情况。
所以我又加了个指标就是如果距离一样，那么横纵距离差小的更有优先权。就A掉了。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
typedef pair<int,int> pi;
const pi D[]={pi(2,1),pi(1,2),pi(-1,2),pi(-2,1),pi(-2,-1),pi(-1,-2),pi(1,-2),pi(2,-1)};
const int inf=~0U>>1;
inline int abs(int x){return x<0?-x:x;}
inline pi dist(pi a,pi b)
{
int x=abs(a.first-b.first),y=abs(a.second-b.second);
return pi(x+y,abs(x-y));
}
pi operator+(const pi&a,const pi&b)
{
return pi(a.first+b.first,a.second+b.second);
}
ostream& operator<<(ostream& out,const pi&a)
{
out<<"("<<a.first<<","<<a.second<<")";
}
int main()
{
//freopen("in","r",stdin);
pi a,b;int ans=0;
cin>>a.first>>a.second>>b.first>>b.second;
while (dist(a,b).first>10)
{
pi next,Min(inf,inf);
rep(i,8)
{
pi c=a+D[i];pi ncost=dist(c,b);
if(ncost<Min)
Min=ncost,next=c;
}
a=next,ans++;
}
int x=min(a.first,b.first),y=min(a.second,b.second);
pi c=pi(-x,-y);
a=a+c+pi(5,5);b=b+c+pi(5,5);
bool vis[100][100]={0};
int d[100][100];
vis[a.first][a.second]=true;
d[a.first][a.second]=0;
queue<pi> Q;Q.push(a);
while (Q.size())
{
pi t=Q.front();Q.pop();int cost=d[t.first][t.second];
if(t==b) break;
rep(i,8)
{
pi c=t+D[i];
if(c.first>=0&&c.first<100&&c.second>=0&&c.second<100)
if(!vis[c.first][c.second])
{
vis[c.first][c.second]=true;
d[c.first][c.second]=cost+1;
Q.push(c);
}
}
}
cout<<ans+d[b.first][b.second];
}

61.187.179.132:8080/JudgeOnline/showproblem
太TMD恶心了。。一眼就看出是匹配。。关键是这个答题是要连续的！
也就是说从1到开始找增广轨找不到就不能再找了。。结果WA了3次
Code：
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int V=1200;
int E[V][2],Link[V],n,m;
bool vis[V];
bool dfs(int x)
{
if(vis[x]) return 0;
vis[x]=1;
for(int i=0,t;i<2;i++)
{
t=E[x][i];
if(Link[t]==-1||dfs(Link[t]))
return Link[t]=x,1;
}
return 0;
}
int main()
{
cin>>n>>m;
rep(i,m) cin>>E[i][0]>>E[i][1];
rep(i,n) Link[i]=-1;
int ans;
for(ans=0;ans<m;ans++){memset(vis,0,sizeof(vis)); if(!dfs(ans)) break;}
cout<<ans<<endl;
}

www.vijos.cn/Problem_Show.asp
也是[CQOI2009]中位数图
额。。设b所在位置为x，
设一个数列S中大于b的数的数量-小于b的数的数量F(S)
那么这个序列由x左边的一些和右边的一些构成，且F(Left)+F(Right)=0。。
那么就很简单了。。从x往右扫描一遍，记录每个F(S)出现了几次，放在Count数组里
再往左扫描一遍，若当前F值为now,只要把答案+上Count[-now]就可以了
0ms1A。。真是爽啊。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=1e5+10;
int main()
{
//freopen("in","r",stdin);
int n,b;int A[maxn];
int C[maxn*2]={0};
cin>>n>>b;int x;
rep(i,n) scanf("%d",A+i),x=(A[i]==b?i:x);
int now=0;
C[now+maxn]++;
for(int i=x+1;i<n;i++)
{
if(A[i]>b) now++;
else now–;
C[now+maxn]++;
}
long long ans=0;
now=0;ans+=C[now+maxn];
for(int i=x-1;i>=0;–i)
{
if(A[i]>b) now++;
else now–;
ans+=C[maxn-now];
}
cout<<ans<<endl;
}
P.S最近在做以前浙江省数学竞赛的卷子，突然灵机一动想出了一道编程题，就交到Vijos上面去了。。不知道能不能通过囧。。