A

题目描述

有长度为 \(n\) 的数组 \(\{a\}\)，若 \(a_i>0\) 则表示 \(p_i\leq a_i\)，若 \(a_i<0\) 则表示 \(p_i\geq a_i\)

请问满足上面 \(n\) 个条件的排列个数，答案对 \(10^9+7\) 取模。

\(n\leq 5000\)

解法

首先考虑 \(a_i>0\) 时有两种类似的计数方法，第一种是扫描 \(a_i\)，决策它们可以填的位置；第二种是扫描位置，决策它们可以填的 \(a_i\)，但是综合考虑 \(a_i>0\) 和 \(a_i<0\) 这两种方法都难做。

我们可以尝试同时使用这两种方法，我们从左到右扫描位置，对于 \(a_i>0\) 我们在扫描到 \(i\) 时直接安排它们的位置，对于 \(a_i<0\) 我们可以考虑把它们填到 \(i\) 中。

这样就可以 \(dp\) 了，设 \(dp[i][j]\) 表示扫描到 \(i\) 已经填入了 \(j\) 个 \(a_i<0\) 的位置的方案数。

总结

就算两类元素的计数方式不同，也可以写进同一个 \(dp\) 中。

#include <cstdio>
const int M = 5005;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[M],l[M],r[M],dp[M][M],fac[M],inv[M];
void add(int &x,int y) {x=(x+y)%MOD;}
void init()
{
	fac[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
}
int A(int n,int m)
{
	if(m<0 || n<m) return 0;
	return fac[n]*inv[n-m]%MOD;
}
signed main()
{
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	n=read();init();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(a[i]>0) l[a[i]]++;
		else r[-a[i]]++;
	}
	dp[0][0]=1;
	int cnt=0,pre=0;
	for(int i=1;i<=n;i++)
	{
		pre+=r[i];
		for(int j=0;j<i;j++)
		{
			add(dp[i][j],dp[i-1][j]);
			if(pre>j) add(dp[i][j+1],dp[i-1][j]*(pre-j));
		}
		for(int j=0;j<=i;j++)
			dp[i][j]=dp[i][j]*A(i-j-cnt,l[i])%MOD;
		cnt+=l[i];
	}
	printf("%lld\n",dp[n][pre]);
}

C

题目描述

\(01\) 字符串 \(a\) 长度为 \(n\)，表示密码原文。字符串 \(b\) 长度为 \(m\)，其中恰好有 \(k\) 个位置为给定的 \(0/1\)，其他位置均为 ?

加密过程：你可以根据字符串 \(a\) 把字符串 \(b\) 的 ? 位置任意填上 \(0/1\)，得到字符串 \(tmp\)

解密过程：只根据字符串 \(tmp\) 还原出字符串 \(a\)，注意这个过程你只知道 \(n,m,tmp\)

现在要求你实现两个函数完成加密和解密，要求最后可以还原出字符串 \(a\)

\(n+k+50\leq m,m\leq 2050\)

解法

这种加密题可以考虑随机向量的方法，我们可以固定一个随机种子在两个过程得到相同的向量。

本题我们随机 \(m\) 个长度为 \(n\) 的 \(01\) 向量，然后考虑用这些向量线性组合出 \(a\)，再用 \(tmp\) 记录向量的组合情况。

具体来说我们求出这 \(m\) 个向量的线性基（排除固定位置），并且记录线性基上的元素是由哪些位置的向量组合而成的。然后用这个线性基拼凑出字符串 \(a\)，同时可以得到由哪些位置的向量异或而得到，这个信息可以通过 \(tmp\) 从加密函数传递到解密函数，\(tmp\) 对应位置为 \(1\) 就表示解密时要异或上这个向量。

如果固定位置的有 \(1\) 怎么办？你在加密时就把 \(a\) 异或上这个固定位置的向量即可。

只要线性基满秩那么我们的算法就是正确的，由于会多出来 \(50\) 个向量，所以满秩的概率是极大的。本题我们可以全程用 \(\tt bitset\) 优化，那么时间复杂度 \(O(\frac{m^3}{w})\)

#include "password.h"
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int M = 2100;
bitset<M> v[M],c[M],p[M];
void generate(int n,int m,int sd)
{
	const int MOD = 14451;
	mt19937 e(371);
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			v[i][j]=e()&1;
}
void encoder(int n,int m,int k,const char *a,const char *b,char *ans)
{
	generate(n,m,371);
	char na[M]={};
	for(int i=0;i<n;i++) na[i]=a[i];
	for(int i=0;i<m;i++)
	{
		if(b[i]=='?')
		{
			bitset<M> nw;nw[i]=1;
			for(int j=n-1;j>=0;j--)
			{
				if(!v[i][j]) continue;
				if(!c[j][j]) {c[j]=v[i];p[j]=nw;break;}
				else v[i]=v[i]^c[j],nw=nw^p[j];
			}
		}
		else if(b[i]=='1')
		{
			for(int j=0;j<n;j++)
				na[j]=((na[j]-'0')^v[i][j])+'0';
		}
	}
	bitset<M> res,nw;
	for(int i=n-1;i>=0;i--)
	{
		if(nw[i]!=na[i]-'0')
			nw=nw^c[i],res=res^p[i];
	}
	for(int i=0;i<m;i++)
	{
		if(b[i]!='?') ans[i]=b[i];
		else ans[i]=res[i]+'0';
	}
}
void decoder(int n,int m,const char *a,char *ans)
{
	generate(n,m,371);
	bitset<M> res;
	for(int i=0;i<m;i++) if(a[i]=='1')
		res=res^v[i];
	for(int i=0;i<n;i++)
		ans[i]=res[i]+'0';
}