官方题解：http://wyfcyx.is-programmer.com/posts/95490.html
A
目前只会30分的暴力……DP好像很神的样子0.0（听说可以多次随机强行算？
//Round2 A
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/
int n,m;
double a[][]; void work1(){
double ans=1.0;
F(i,,m) ans*=(1.0-a[][i]);
printf("%.9f\n",1.0-ans);
}
void work2(){
double ans=0.0;
F(i,,m) ans*=(1.0-a[][i]);
}
int mp[][],my[N];
bool vis[N];
long double ans=0.0,gailv=1.0; bool go(int x){
F(i,,m)
if (mp[x][i] && !vis[i]){
vis[i]=;
if (!my[i]||go(my[i])){
my[i]=x;
return ;
}
}
return ;
}
void check(){
// F(i,1,n){ F(j,1,m) printf("%d ",mp[i][j]); puts("");}
int tmp=;
memset(my,,sizeof my);
F(i,,n){
memset(vis,,sizeof vis);
if (go(i)) tmp++;
}
double gl=gailv;
// printf("%d %.9f\n\n",tmp,gl);
ans+=tmp*gailv;
}
void dfs(int x,int y){
// printf("dfs %d %d\n",x,y);
if (x==n+){check();return;}
D(i,,){
mp[x][y]=i;
gailv*=i*a[x][y]+(-i)*(1.0-a[x][y]);
if (y==m) dfs(x+,);
else dfs(x,y+);
mp[x][y]=;
gailv/=i*a[x][y]+(-i)*(1.0-a[x][y]);
}
}
void work3(){
dfs(,);
double as=ans;
printf("%.9f\n",as);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n) F(j,,m) scanf("%lf",&a[i][j]);
if (n==) work1();
// else if (n==2) work2();
else
work3();
return ;
}
（30分）
C
原来是用FFT来做的好题！
第一步用KMP比较简单，容易想到。
这题的特点是每个字符都是0或1，所以考虑第二步的时候，可以用FFT来进行快速运算0.0太神了！利用卷积的特点，将一个串反转过来，然后相同的，会对答案贡献1，不同的贡献0，卷积一下就是两个串对应位置都是1的位数！太神奇了。。。（都是0的位数求法：整个异或一下，0变1，1变0）
//Round2 C
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/
const double pi=acos(-);
struct comp{
double r,i;
comp(double r=0.0,double i=0.0):r(r),i(i){}
comp operator * (const comp &b)const{return comp(r*b.r-i*b.i,r*b.i+i*b.r);}
comp operator + (const comp &b)const{return comp(r+b.r,i+b.i);}
comp operator - (const comp &b)const{return comp(r-b.r,i-b.i);}
}A[N],B[N]; int n,m,nxt[N],v[N],cnt,c[N],nn;
char a[N][],b[N][],a2[N],b2[N];
void FFT(comp *a,int n,int type){
for(int i=,j=;i<n;++i){
if (i<j) swap(a[i],a[j]);
for(int k=n>>;(j^=k)<k;k>>=);
}
for(int m=;m<n;m<<=){
double u=pi/m*type; comp wm(cos(u),sin(u));
for(int i=;i<n;i+=(m<<)){
comp w(,);
rep(j,m){
comp &A=a[i+j+m],&B=a[i+j],t=w*A;
A=B-t; B=B+t; w=w*wm;
}
}
}
if (type==-) rep(i,n) a[i].r/=n;
}
void KMP(){
nxt[]=nxt[]=;
int j=;
F(i,,m){
while(j!= && strcmp(b[i],b[j])!=) j=nxt[j];
nxt[i+]=strcmp(b[i],b[j])== ? ++j : ;
}
j=;
F(i,,n){
while(j!= && strcmp(a[i],b[j])!=) j=nxt[j];
if (strcmp(a[i],b[j])==) j++;
if (j==m+) v[++cnt]=i-m+;
}
}
void work(int x){
rep(i,nn) A[i]=B[i]=comp(,);
rep(i,n) if (a2[i+]-''==x) A[i].r=;
rep(i,m) if (b2[i+]-''==x) B[m-(i+)].r=;
FFT(A,nn,); FFT(B,nn,);
rep(i,nn) A[i]=A[i]*B[i];
FFT(A,nn,-);
rep(i,n) c[i+]+=(int)(A[i+m-].r+0.5);
} int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
n=getint(); m=getint();
for(nn=;nn<n+m-;nn<<=);
F(i,,n){
scanf("%s",a[i]);
a2[i]=a[i][];
a[i][]='';
}
F(i,,m){
scanf("%s",b[i]);
b2[i]=b[i][];
b[i][]='';
}
KMP();
if (cnt) puts("Yes");
else {puts("No");return ;}
work();
work();
int ans1=1e9,ans2=;
F(i,,cnt) if (m-c[v[i]]<ans1){
ans1=m-c[v[i]]; ans2=v[i];
}
printf("%d %d\n",ans1,ans2);
return ;
}