C. Sasha and Array
题目大意&题目链接：
http://codeforces.com/problemset/problem/718/C
长度为n的正整数数列，有m次操作，$opt==1$时，对$[L,R]$全部加x，$opt==2$时，对$[L,R]$求$\sum_{i=L}^{R}Fibonacc(a_{i})$。
题解：
线段树+矩阵快速幂。
在每个线段树存一个转移矩阵，然后YY即可。
代码：
#include<cstdio>
#include<cstring>
#define lc t<<1
#define rc (t<<1)|1
typedef long long ll;
const int N=;
const ll mod=(ll)1e9+;
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct Martrix{
ll a[][];
Martrix(){memset(a,,sizeof(a));}
inline void e(){
memset(a,,sizeof(a));
for(int i=;i<;i++)
a[i][i]=;
}
inline void fibe(){
for(int i=;i<;i++)
for(int j=;j<;j++)
a[i][j]=;
a[][]=;
}
friend Martrix operator *(Martrix x,Martrix y){
Martrix z;
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
return z;
}
friend Martrix operator ^(Martrix a,int b){
Martrix ans;ans.e();
while(b){
if(b&) ans=ans*a;
b>>=;
a=a*a;
}return ans;
}
}fibe_1;
struct Tree{
Martrix x,lazy;
}tree[N<<];
const int root=;
inline void update(int t){
tree[t].x.a[][]=(tree[lc].x.a[][]+tree[rc].x.a[][])%mod;
tree[t].x.a[][]=(tree[lc].x.a[][]+tree[rc].x.a[][])%mod;
}
inline void downdate(int t){
tree[lc].x=tree[t].lazy*tree[lc].x;
tree[rc].x=tree[t].lazy*tree[rc].x;
tree[lc].lazy=tree[lc].lazy*tree[t].lazy;
tree[rc].lazy=tree[rc].lazy*tree[t].lazy;
tree[t].lazy.e();
}
inline void build(int l,int r,int t){
tree[t].lazy.e();
if(l==r){
int num=read()-;
tree[t].x.fibe();
tree[t].x=(tree[t].x^num)*fibe_1;
return ;
}int mid=l+r>>;
build(l,mid,t<<);build(mid+,r,(t<<)|);
update(t);
}
inline void add(int l,int r,int L,int R,int t,Martrix x){
if(l!=r)
downdate(t);
if(L<=l&&r<=R){
tree[t].x=x*tree[t].x;
tree[t].lazy=x;
return ;
}
int mid=l+r>>;
if(R>mid) add(mid+,r,L,R,rc,x);
if(L<=mid) add(l,mid,L,R,lc,x);
update(t);
}
inline ll sum(int l,int r,int L,int R,int t){
if(l!=r)
downdate(t);
if(L<=l&&r<=R){
return tree[t].x.a[][];
}
int mid=l+r>>;
ll ans=;
if(R>mid) ans+=sum(mid+,r,L,R,rc);
if(L<=mid) ans+=sum(l,mid,L,R,lc);
return ans%mod;
}
int n,m;
int main(){
n=read(),m=read();
fibe_1.a[][]=;
build(,n,);
for(int i=,opt,l,r,x;i<=m;i++){
opt=read();
l=read(),r=read();
if(opt==){
x=read();
Martrix now;now.fibe();
now=now^x;
add(,n,l,r,root,now);
}
else{
printf("%lld\n",sum(,n,l,r,root));
}
}
}
D. Andrew and Chemistry
题目大意&链接：
http://codeforces.com/problemset/problem/718/D
（辣鸡有机化学）给一个无向图，每个节点只允许有至多4条边，且至少一条边，而且这个图是个树，现在新建一个节点，并与这个节点连条边，求可以构成多少个不一样的图（恩……就是是不是同构）。n<=100000
题解：
写个靠谱的哈希……然后因为节点多，但是只会有最多4条边，设F[x][i]表示从第x个节点，走第i条边得到的hash值，如果已经得到F[x][i]就不要再dfs下去了。
（什么你问我时间复杂度）
代码：
#include<cstdio>
#include<algorithm>
#include<set>
inline int read(){
int s=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') s=s*+(ch^),ch=getchar();
return s;
}
typedef unsigned long long ull;
ull P[]={0u,76543u,233u,123457u,56741857u,1537427u};
const int N=;
ull f[N];
ull g[N][];
std::set<ull> st;
int n;
struct edges {
int v;edges *last;
}edge[N<<],*head[N];int cnt;
inline void push(int u,int v){
edge[++cnt]=(edges){v,head[u]};head[u]=edge+cnt;
}
int a[];
inline bool cmp(int x,int y){
return f[x]<f[y];
}
inline void dfs(int x,int fa){
int num=;
f[x]=1u;
int k=;
for(edges *i=head[x];i;i=i->last){
k++;
if(fa==i->v) continue;
if(!g[x][k])
dfs(i->v,x),g[x][k]=f[i->v];
else
f[i->v]=g[x][k];
}
for(edges *i=head[x];i;i=i->last)
if(fa==i->v) continue;
else a[++num]=i->v;
std::sort(a+,a++num,cmp);
for(int i=;i<=num;i++)
f[x]=f[x]*P[]+f[a[i]]*P[i];
}
int red[N];
int main(){
n=read();
for(int i=;i<n;i++){
int u=read(),v=read();
push(u,v);push(v,u);
red[u]++,red[v]++;
}
//printf("s");
for(int i=;i<=n;i++){//printf("i=%d\n",i);
if(red[i]<){
dfs(i,i);
// printf("i=%d\n",i);
st.insert(f[i]);
}
}
printf("%d\n",st.size());
}