差别

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

--- 2020-2021:teams:namespace:牛客多校第二场 [2020/07/16 11:46]
great_designer
+++ 2020-2021:teams:namespace:牛客多校第二场 [2020/07/17 12:24] (当前版本)
great_designer [E]
@@ 行 409: / 行 409: @@
 </hidden>
-======B======
+=====B=====
 储存斜率用了两种做法。开longlong那个TLE掉了，double那个WA了，实在无语……
@@ 行 637: / 行 637: @@
 积分算法原来也不难，模拟就好了。反正要求精度不高……
+=====E=====
+集合中可重复取数，求异或的最大值，集合大小很大。
+有一个与FFT、NTT非常相似的东西叫FWT，比前两者简单，用于解决数组异或（不进位加法）卷积的问题。
+FWT和它的逆，将数组异或（不进位加法）的卷积变为了乘法。
+<hidden>
+<code C>
+#include<stdio.h>
+int n,nans[1<<18],one[1<<18],ans[200005];
+void FWT(int *src,int t)
+{
+	int sz;
+    for(sz = 2;sz <= 1<<18;sz<<=1)
+	{
+        int step = sz >> 1;
+        int i;
+        for(i = 0;i< 1<<18;i+=sz)
+		{
+			int j;
+            for(j = i;j < i+step;j++)
+			{
+                int a = src[j];
+				int b = src[j+step];
+                src[j] = a+b;
+                src[j+step] = a-b;
+                if(t==-1)
+                {
+                	src[j]>>=1;
+                	src[j+step]>>=1;
+				}
+            }
+        }
+    }
+}
+int main()
+{
+    scanf("%d",&n);
+    int x;
+    int i;
+    for(i = 1;i<= n;i++)
+	{
+        scanf("%d",&x);
+        one[x]=1;
+        nans[x]=1;
+        if (x > ans[1])
+		{
+			ans[1] = x;
+		}
+    }
+    FWT(one,1);
+    for(i = 2;i<= 20;i++)
+	{
+        FWT(nans,1);
+        int j;
+        for(j = 0;j < 1<<18;j++)
+        {
+        	nans[j] = nans[j]*one[j];
+		}
+        FWT(nans,-1);
+        for(j = 0;j < 1<<18;j++)
+        {
+        	if (nans[j])
+        	{
+        		nans[j] = 1;
+			}
+		}
+        for(j=(1<<18)-1;j>=0;j--)
+        {
+        	if (nans[j])
+			{
+                ans[i] = j;
+                break;
+            }
+		}
+    }
+    for(i = 21;i<= n;i++)
+    {
+    	ans[i] = ans[i-2];
+	}
+    for(i = 1;i<= n;i++)
+    {
+    	printf("%d ",ans[i]);
+	}
+}
+</code>
+</hidden>
+=====J=====
+对给定置换A开k次方，k是个大素数。
+由群论知，对大素数k，k次方运算是一一映射，所以实质是个求数论倒数的运算。
+由于模不是素数，用费马欧拉定理不方便，只能改用一次不定方程的扩展来求逆。
+<hidden>
+<code C++>
+#include<stdio.h>
+#include<vector>
+using namespace std;
+long long extgcd(long long a,long long b,long long& u,long long& v)
+{
+    long long d;
+    if(b==0)
+	{
+        d = a;
+        u=1,v=0;
+    }
+	else
+	{
+        d = extgcd(b,a%b,v,u);
+        v -= a/b*u;
+    }
+	return d;
+}
+int n,k,vis[100005];
+int P[100005],ans[100005],a[100005],tmp[100005],ttt[100005];
+int main()
+{
+    scanf("%d%d",&n,&k);
+    int i;
+    for(i=1;i<=n;i++)
+	{
+		scanf("%d",&a[i]);
+	}
+    for(i=1;i<=n;i++)
+    {
+	    if(!vis[i])
+		{
+	        vis[i] = 1;
+	        vector<int> pos;
+	        int u = a[i],len = 1;pos.push_back(i);
+	        while(u!=i)
+			{
+	            len++;
+	            vis[u] = 1;pos.push_back(u);
+	            u = a[u];
+	        }
+	        long long x,y;
+	        extgcd(k,len,x,y);
+	        x = (x%len+len)%len;
+	        int j;
+	        for(j=1;j<=len;j++)
+			{
+	            ans[pos[j-1]] = pos[(j-1+x)%len];
+	        }
+	    }
+	}
+    for(i=1;i<=n;i++)
+	{
+		printf("%d ",ans[i]);
+	}
+    return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具