差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:牛客多校第七场 [2020/08/06 11:50]
great_designer
+++ 2020-2021:teams:namespace:牛客多校第七场 [2020/08/08 11:26] (当前版本)
great_designer
@@ 行 141: / 行 141: @@
 </hidden>
-=====J=====
+=====A=====
 以下是补题。
-[[小型代码分析系统的实现方式]]
+这个题数据量较小，甚至可以打表。
+<hidden>
+<code C>
+#include<stdio.h>
+#include<string.h>
+#include<math.h>
+int f[9][2*250][2*250], n, r;
+int Ans[20][50];
+int main()
+{
+    int T;
+    scanf("%d",&T);
+    memset(Ans,255,sizeof(Ans));
+    while (T--)
+    {
+        scanf("%d%d", &n, &r);
+        if (Ans[n][r]!=-1)
+        {
+            printf("%d\n",Ans[n][r]);
+            continue;
+        }
+        int i;
+        for(i=0; i<=n; ++i)
+        {
+        	int j;
+        	for(j=250-n*r; j<=250+n*r; ++j)
+        	{
+        		int k;
+        		for(k=250-n*r; k<=250+n*r; ++k)
+        		{
+        			f[i][j][k]=-1;
+				}
+			}
+    	}
+        f[0][250][250]=0;
+        for(i=-r; i<=r; ++i)
+        {
+        	int j;
+        	for(j=-r; j<=r; ++j)
+        	{
+        		if(i*i+j*j<=r*r)
+        		{
+        			f[1][250+i][250+j] = 0;
+				}
+			}
+		}
+        for(i=2; i<=n; ++i)
+        {
+        	int j;
+            for(j=-r; j<=r; ++j)
+            {
+                int k = trunc(sqrt(r*r-j*j));
+                int s1;
+                for(s1=250-(i-1)*r; s1<=250+(i-1)*r; ++s1)
+                {
+                	int s2;
+                	for(s2=250-(i-1)*r; s2<=250+(i-1)*r; ++s2)
+                    {
+                        int z = f[i-1][s1][s2]; int t1 = s1 - 250; int t2 = s2 - 250;
+                        if (z==-1) continue;
+                        f[i][s1+j][s2+k] =f[i][s1+j][s2+k]>(z+(t1*t1+t2*t2+z)/(i-1)-2*(j*t1+k*t2)+(i-1)*(j*j+k*k))?f[i][s1+j][s2+k]:(z+(t1*t1+t2*t2+z)/(i-1)-2*(j*t1+k*t2)+(i-1)*(j*j+k*k));
+                        f[i][s1+j][s2-k] =f[i][s1+j][s2-k]>(z+(t1*t1+t2*t2+z)/(i-1)-2*(j*t1-k*t2)+(i-1)*(j*j+k*k))?f[i][s1+j][s2-k]:(z+(t1*t1+t2*t2+z)/(i-1)-2*(j*t1-k*t2)+(i-1)*(j*j+k*k));
+                    }
+				}
+            }
+        }
+        int ans = 0;
+        for(i=250-n*r; i<=250+n*r; ++i)
+        {
+        	int j;
+        	for(j=250-n*r; j<=250+n*r; ++j)
+        	{
+        		ans =ans>f[n][i][j]?ans:f[n][i][j];
+			}
+		}
+        printf("%d\n", ans);
+        Ans[n][r]=ans;
+    }
+    return 0;
+}
+</code>
+</hidden>
+=====I=====
+<hidden>
+<code C>
+#include<stdio.h>
+int T;
+long long mod;
+long long norings[5007], GraphCnt[5007], EdgeCnt[5007], f[5007], g[5007];
+long long SS[5007][5007];
+int power(int x, int times)
+{
+    return SS[x][times];
+}
+long long C[5007][5007];
+int main()
+{
+    scanf("%d%d", &T, &mod);
+	int i;
+    for(i = 1; i < 5007; i++)
+	{
+        SS[i][0] = 1;
+        int j;
+        for(j = 1; j < 5007; j++)
+            SS[i][j] = (long long)SS[i][j - 1] * i % mod;
+    }
+    for(i = 0; i < 5007; i++)
+	{
+        C[i][0] = C[i][i] = 1;
+        int j;
+        for(j = 1; j < i; j++)
+		{
+            C[i][j] = C[i - 1][j - 1] + C[i - 1][j] ;
+            if (C[i][j] >= mod) C[i][j]-=mod;
+        }
+    }
+    norings[1] = norings[2] = 1;
+    for(i = 3; i < 5007; i++)
+	{
+        norings[i] = power(i, i - 2);
+    }
+    for(i = 1; i < 5007; i++)
+	{
+        GraphCnt[i] = norings[i];
+    }
+    for(i = 2; i < 5007; i++)
+	{
+        EdgeCnt[i] = 0;
+        int j;
+        for(j = 1; j <= i - 1; j++)
+		{
+            EdgeCnt[i] = (EdgeCnt[i] + C[i - 2][j - 1] * power(i - 1, i - j - 1) % mod * i % mod * (j * j) % mod) % mod;
+        }
+    }
+    f[0] = 1;
+    for(i = 1; i < 5007; i++)
+	{
+		int j;
+        for(j = 1; j <= i; j++)
+		{
+            f[i] = (f[i] + GraphCnt[j] * f[i - j] % mod * C[i - 1][j - 1]) % mod;
+            g[i] = (g[i] + C[i - 1][j - 1] * (EdgeCnt[j] * f[i - j] % mod + GraphCnt[j] * g[i - j] % mod)) % mod;
+        }
+    }
+    while (T--)
+	{
+        int n;
+        scanf("%d",&n);
+        printf("%lld\n",g[n]);
+    }
+    return 0;
+}
+</code>
+</hidden>
+=====J=====
+见[[小型代码分析系统的实现方式]]。

CVBB ACM Team

用户工具

站点工具

差别

页面工具