C題：
蠻有意思的，給你m個位置，現在要從這m個位置往位置的兩邊擴展，問你把所有的數都擴展到總共有多少種方法。
在兩個位置中間的那些數的可能的排列數應該是2^（k-1），因為每次都有兩種選擇，要麼左端點，要麼右端點。
然後從所有的間隔中各取出一種排列，a1 a2 a3 b1 b2 b3 c1 c2 c3，現在就是求這個序列的總排列數，要求同類的先後順序不能變，很容易發現這個其實就是類似於多重集合的排列，ans=n!/(p1!*p2!*p3!) ，然後分子再乘上一個2^(k-1)就好了
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long lld;
const int inf = ~0u>>2;
const int mod = 1000000007 ;
const int maxn = 1010;
int pos[maxn];
lld Pow(lld a,lld b) {
lld ans = 1;
while(b) {
if(b&1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans ;
}
lld fac[maxn],two[maxn];
vector<int> rec;
void solve(int n) {
fac[0] = 1; two[0] = 1;
for(int i = 1; i <= 1000; i++) fac[i] = fac[i-1] * i % mod;
for(int i = 1; i <= 1000; i++) two[i] = two[i-1] * 2 % mod;
int sum = 0;
for(int i = 0; i < rec.size(); i++) sum += rec[i];
// printf("sum=%d\n",sum);
lld ans = fac[sum];
for(int i = 0; i < rec.size(); i++) {
ans = ans * Pow(fac[rec[i]],mod-2) % mod;
}
for(int i = 1; i < rec.size()-1;i++) {
if(rec[i]>0) ans = ans * two[rec[i]-1] % mod;
// printf("ans=%d\n",rec[i]);
}
printf("%I64d\n",ans);
}
int main() {
int n , m;
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i++) {
scanf("%d",&pos[i]);
}
sort(pos,pos+m);
rec.push_back(pos[0]-1);
for(int i = 1; i < m ; i++) {
rec.push_back(pos[i]-pos[i-1]-1);
}
rec.push_back(n-pos[m-1]);
solve(n);
return 0;
}
D題：
上次做過一個網格反彈的題，，，，被陷進去了。。。。
網格中的反彈有個性質就是45度反射的時候經過的格子的奇偶性都是一樣的，所以無論怎麼反彈，都不會經過兩個相鄰的方格。
給你一個n*m的矩形網格，問你從某個位置，某個方向出發經過多少個格子才能將網格染成棋盤的樣子，也就是每兩個相鄰的格子的顏色都不同。
每個矩形有兩種棋盤，不管哪種，如果成功染成某一種，肯定會經過邊界的網格n+m-2次，也就是說，如果反彈過程中經過了n+m-2個不同的邊界網格，肯定就對應著一種棋盤的方案，如果兩次到達同一個位置同一個方向，肯定已經進入循環了。
E題：
給你一棵樹，5000個點，每條邊有邊權，可以刪掉一條邊再將這條邊換個位置，要保證改變後仍然是樹的形狀，現在問你所有點對的距離之和最小是多少。
5000個點，馬上想到n^2..然後就是暴力枚舉去掉每條邊 ，剩下的就是兩棵樹，然後重新連接一條邊，稍微想一下，這條邊肯定就是將兩棵樹的重心連起來，所以，接下來的事情就簡單了。。。
比賽的時候看錯了題，以為邊可以修改很多次。。。然後各種YY，不夠仔細啊。。。
--------------------------------------------------------------------------------
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = ~0u>>2;
const int mod = 1000000007 ;
const int maxn = 5010;
int son[maxn] ;
long long dp[maxn];
int n ;
int mp[maxn][maxn];
vector<int> edge[maxn];
int node;
struct Edge{
int s,t,w;
Edge(){}
Edge(int a,int b,int c)
{
s = a;
t = b;
w = c;
}
}in[maxn];
int dep[maxn];
void dfs(int u,int f) {
son[u] = 1;
dep[u] = dep[f] + 1;
int sz = edge[u].size();
for(int i = 0; i < sz; i++) {
int v = edge[u][i];
if(v==f) continue;
dfs(v,u);
son[u] += son[v];
}
}
int cen;
int S[maxn];
void DFS(int u,int f) {
S[u] = 1;
int sz = edge[u].size();
for(int i = 0; i < sz; i++) {
int v = edge[u][i];
if(v == f || v == node) continue;
DFS(v,u);
S[u] += S[v];
}
}
long long sum;
void dfs1(int u,int f,int rt) {
dp[u] = 0;
int sz = edge[u].size();
for(int i = 0; i < sz; i++) {
int v = edge[u][i];
if(v == f || v == node) continue;
dfs1(v,u,rt);
sum += (long long ) S[v] * (S[rt]-S[v]) * mp[u][v];
dp[u] += dp[v] + (long long)S[v] * mp[u][v];
}
}
long long Mi;
void dfs2(int u,int f,int rt) {
if(u==rt) {
Mi = min(dp[u],Mi);
} else {
long long tmp = dp[f] - dp[u] - (long long)S[u] * mp[f][u];
dp[u] += (long long)mp[f][u] * (S[rt] - S[u]) + tmp;
Mi = min(dp[u],Mi);
}
int sz = edge[u].size();
for(int i = 0; i < sz; i++) {
int v = edge[u][i];
if(v == f || v == node) continue;
dfs2(v,u,rt) ;
}
}
int main() {
scanf("%d",&n);
int a,b,c;
int tot = 0;
for(int i=1;i<n;i++) {
scanf("%d%d%d",&a,&b,&c);
edge[a].push_back(b);
edge[b].push_back(a);
mp[a][b] = mp[b][a] = c;
in[tot++] = Edge(a,b,c);
}
dfs(1,0);
long long INF = (long long)1000000000*(long long)1000000000;
long long ans = INF;
for(int i=0;i<tot;i++) {
int u = in[i].s , v = in[i].t;
if(dep[u] > dep[v]) swap(u,v);
node = v;
Mi = INF; sum = 0;
DFS(1,0);
dfs1(1,0,1);
dfs2(1,0,1);
long long tmp = (long long)(son[1]-son[node])*(son[node])*in[i].w;
tmp += Mi * (son[node]) ;
tmp += sum;
Mi = INF; sum = 0;
DFS(node,u);
dfs1(node,u,node);
dfs2(node,u,node);
tmp += Mi * (son[1]-son[node]);
tmp += sum;
if(tmp < ans) ans = tmp;
}
printf("%I64d\n",ans);
return 0;
}
