博弈论+概率dp
对于第一问：f[i][j]表示前i个数，当前黑板上的数为j的概率
当前有三种情况
1． 当前数不是j的倍数—>黑板上的数字改变。
2． 当前数是j的倍数且当前数在前i个数中(已经选过)
3． 当前数是j的倍数且没有选过
转移:f[i+1][j]=((j的倍数个数-i)*f[i][j]+f[i][gcd(j,k)])的平均值 j的倍数个数-i是没选过的j的倍数
对于第二问，考虑博弈论中sg函数。可知sg[i][1]二维含义同f数组)必定为0(最后黑板上剩下1必败) sg[n][i]=0(选完了必败) 同样枚举上述三种情况，取后续状态mex值即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define eps 1e-8 6 #define N 1000 7 using namespace std; 8 inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 9 int sg[N + 5][N + 5], g[N + 5][N + 5], f[N + 5], n, a[N + 5]; 10 double dp[N + 5][N + 5], ans = 0; 11 bool getsg(int x, int y) { 12 if (x == 1) return 1; 13 if (sg[x][y] != -1) return sg[x][y]; 14 bool flag = 1; 15 if (f[x] > y) flag &= getsg(x, y + 1); 16 for (int i = 1; i <= n; i++) 17 if (g[x][i] != x) 18 flag &= getsg(g[x][i], y + 1); 19 sg[x][y] = !flag; 20 return sg[x][y]; 21 } 22 int main() { 23 freopen("cards.in", "r", stdin); 24 freopen("cards.out", "w", stdout); 25 scanf("%d", &n); 26 int mx = 0; 27 for (int i = 1; i <= n; i++) { scanf("%d", a + i); mx = max(mx, a[i]); g[0][i] = a[i]; } 28 for (int i = 1; i <= mx; i++) 29 for (int j = 1; j <= n; j++) 30 f[i] += (a[j] % i == 0), g[i][j] = gcd(i, a[j]); 31 dp[0][0] = 1; 32 for (int i = 1; i <= n; i++) 33 for (int j = 0; j <= mx; j++) 34 if (dp[i - 1][j] > eps) { 35 dp[i][j] += dp[i - 1][j] * (f[j] - i + 1) / (n - i + 1); 36 for (int k = 1; k <= n; k++) 37 if (g[j][k] != j) { 38 if (g[j][k] != 1) 39 dp[i][g[j][k]] += dp[i - 1][j] / (n - i + 1); 40 else 41 ans += (i + 1 & 1) * dp[i - 1][j] / (n - i + 1); 42 } 43 } 44 if (n & 1) 45 for (int j = 0; j <= mx; j++) ans += dp[n][j]; 46 printf("%.9lf ", ans); 47 memset(sg, -1, sizeof(sg)); 48 if (getsg(0, 0)) puts("1.000000000"); else puts("0.000000000"); 49 return 0; 50 }
树形dp+LCA
对于60~80分，可以n^2暴力，断掉每条边时，O(N)求每个部分的直径，然后相乘。
正解：倒序加边，考虑两棵树合并的时候新直径一定是原来两个直径四个断点任意两个的路径。所以可以首先求LCA倍增处理两点间路径，然后求最大。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <algorithm> 5 #define N 111111 6 #define MOD 1000000007 7 #define LL long long 8 using namespace std; 9 10 int a[N], dep[N], sum[N], par[N][18], h[N], del[N]; 11 int endpoint[N][2], ans[N], f[N], length[N]; 12 int tote, n, product; 13 14 struct edge{ 15 int s, t, n; 16 }e[N * 2]; 17 18 void adde(int u, int v) { 19 e[++tote].t = v; 20 e[tote].s = u; 21 e[tote].n = h[u]; 22 h[u] = tote; 23 return ; 24 } 25 26 void dfs(int u, int fa) { 27 par[u][0] = fa; 28 dep[u] = dep[fa] + 1; 29 sum[u] = sum[fa] + a[u]; 30 for (int i = 1; i < 18; i++) par[u][i] = par[par[u][i - 1]][i - 1]; 31 for (int i = h[u]; i; i = e[i].n) { 32 int v = e[i].t; 33 if (v != fa) dfs(v, u); 34 } 35 return ; 36 } 37 38 int lca(int u, int v) { 39 if (dep[u] < dep[v]) swap(u, v); 40 for (int t = dep[u] - dep[v], i = 0; t > 0; t >>= 1, i++) 41 if (t & 1) u = par[u][i]; 42 int t = 17; 43 while (u != v) { 44 while (t && par[u][t] == par[v][t]) t--; 45 u = par[u][t]; v = par[v][t]; 46 } 47 return u; 48 } 49 50 int getf(int u) { 51 if (u == f[u]) return u; 52 f[u] = getf(f[u]); 53 return f[u]; 54 } 55 56 int pw(int a, int b) { 57 int ans = 1, t = a; 58 for (int i = b; i; i >>= 1) { 59 if (i & 1) ans = (LL) ans * t % MOD; 60 t = (LL) t * t % MOD; 61 } 62 return ans; 63 } 64 65 int getlength(int u, int v) { 66 int w = lca(u, v); 67 return sum[u] + sum[v] - 2 * sum[w] + a[w]; 68 } 69 70 int getint() 71 { 72 char ch; 73 do 74 { 75 ch=getchar(); 76 }while (ch!='-'&&(ch<'0'||ch>'9')); 77 int ans=0,f=0; 78 if (ch=='-') f=1; else ans=ch-'0'; 79 while (isdigit(ch=getchar())) ans=ans*10+ch-'0'; 80 if (f) ans*=-1; 81 return ans; 82 } 83 84 int main() { 85 freopen("forest.in", "r", stdin); 86 freopen("forest.out", "w", stdout); 87 n = getint(); 88 product = 1; 89 for (int i = 1; i <= n; i++) { 90 a[i] = getint(); 91 f[i] = i; 92 product = (LL) product * a[i] % MOD; 93 endpoint[i][0] = endpoint[i][1] = i; 94 length[i] = a[i]; 95 } 96 97 for (int i = 1; i < n; i++) { 98 int u = getint(), v = getint(); 99 adde(u, v); adde(v, u); 100 } 101 102 dfs(1, 0); 103 104 int t = n; 105 ans[t] = product; 106 107 for (int i = 1; i < n; i++) del[i] = getint(); 108 109 for (int i = n - 1; i; i --) { 110 int id = del[i], u = e[id * 2 - 1].s, v = e[id * 2 - 1].t; 111 u = getf(u); v = getf(v); 112 if (length[u] < length[v]) swap(u, v); 113 int tmax = length[u], end[2]; 114 for (int j = 0; j < 2; j++) end[j] = endpoint[u][j]; 115 for (int j = 0; j < 2; j++) 116 for (int k = 0; k < 2; k++) { 117 int l = getlength(endpoint[u][j], endpoint[v][k]); 118 if (l > tmax) { 119 tmax = l; 120 end[0] = endpoint[u][j]; 121 end[1] = endpoint[v][k]; 122 } 123 } 124 product = (LL) product * pw(length[u], MOD - 2) % MOD; 125 product = (LL) product * pw(length[v], MOD - 2) % MOD; 126 f[v] = u; 127 length[u] = tmax; 128 for (int j = 0; j < 2; j++) endpoint[u][j] = end[j]; 129 product = (LL) product * length[u] % MOD; 130 ans[--t] = product; 131 } 132 for (int i = 1; i <= n; i++) printf("%d ", ans[i]); 133 return 0; 134 }
组合数学
考虑两列的情况。若两列颜色分别为A,B,则A独有的颜色就是A—A∩B ，B同理。
若是多列那还是设两边两列为A,B，中间多列为C，那根据题目结论可以知道C一定是A∩B的子集。枚举A中独有颜色个数，B中独有颜色个数与A中相同。若有i中独有，j中共有C(K，i)*C(k-i+1，j)*C(k-i-j，j)
因为每次选择都必须是恰好那些颜色，不能少，所以用总方案数减去不是恰好的就可以了。
1 # include<iostream> 2 # include<cstdio> 3 # include<cstring> 4 # include<cstdlib> 5 using namespace std; 6 const int pp=1000000007; 7 int c[2008][2008],f[2008],p[2008],ni[2008]; 8 int n,m,k,nn; 9 inline int power(int x,int n) 10 { 11 int ans=1,tmp=x; 12 while (n) 13 { 14 if (n&1) ans=(long long)ans*tmp%pp; 15 tmp=(long long)tmp*tmp%pp;n>>=1; 16 } 17 return ans; 18 } 19 void Count_c() 20 { 21 for (int i=0;i<=nn;i++) c[i][0]=1; 22 for (int i=1;i<=nn;i++) 23 for (int j=1;j<=i;j++) 24 { 25 c[i][j]=c[i-1][j-1]+c[i-1][j]; 26 if (c[i][j]>=pp) c[i][j]-=pp; 27 } 28 } 29 void Count_p() 30 { 31 int mm=(m-2)*n; 32 for (int i=0;i<=nn;i++) 33 p[i]=power(i,mm); 34 } 35 void Count_f() 36 { 37 f[0]=0;f[1]=1; 38 for (int i=2;i<=nn;i++) 39 { 40 f[i]=power(i,n); 41 for (int j=1;j<i;j++) 42 { 43 f[i]-=(long long)f[j]*c[i][j]%pp; 44 if (f[i]<=-pp) f[i]+=pp; 45 } 46 if (f[i]<0) f[i]+=pp; 47 } 48 } 49 void Count_ni() 50 { 51 ni[1]=1; 52 for (int i=2;i<=nn;i++) 53 ni[i]=power(i,pp-2); 54 } 55 int main() 56 { 57 freopen("photo.in","r",stdin); 58 freopen("photo.out","w",stdout); 59 scanf("%d%d%d",&n,&m,&k); 60 nn=min(n,k); 61 if (m==1) 62 printf("%d ",power(k,n)); 63 else 64 { 65 Count_c(); 66 Count_p(); 67 Count_f(); 68 Count_ni(); 69 long long tmp=1,tmp1=1,sum=0,sum1; 70 for (int s=1;s<=nn;s++) 71 { 72 tmp=tmp*ni[s]%pp; 73 tmp=tmp*(k-s+1)%pp; 74 tmp1=1;sum1=0; 75 for (int j=0;j<=s;j++) 76 { 77 sum1+=tmp1*c[s][s-j]%pp*p[s-j]%pp; 78 if (sum1>=pp) sum1-=pp; 79 tmp1=tmp1*ni[j+1]%pp; 80 if (k-s<j+1) break; 81 tmp1=tmp1*(k-s-j)%pp; 82 } 83 sum+=tmp*f[s]%pp*f[s]%pp*sum1%pp; 84 if (sum>=pp) sum-=pp; 85 } 86 printf("%d ",sum); 87 } 88 fclose(stdin); 89 fclose(stdout); 90 return 0; 91 }