今天下午考试被FFT和数论题目翔了一脸QAQ
做的是Newscafe杯的题目
第一题 异化多肽
显然构造多项式f
答案是f+f^2+f^3……
化简一下得1/(1-f)
之后多项式求逆即可
考试的时候推了好久的多项式求逆的式子(感觉自己什么都忘光了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define G 5
using namespace std;
typedef long long LL;
const int maxn=300010;
const int mod=1005060097;
int n,m,k,N,L;
int A[maxn],B[maxn];
int rev[maxn];
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
int pow_mod(int v,int p){
int tmp=1;
while(p){
if(p&1)tmp=1LL*tmp*v%mod;
v=1LL*v*v%mod;p>>=1;
}return tmp;
}
void FFT(int *A,int n,int flag){
for(L=0;(1<<L)<n;++L);
for(int i=0;i<n;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(L-1));
for(int i=0;i<n;++i)if(i<rev[i])swap(A[i],A[rev[i]]);
for(int k=2;k<=n;k<<=1){
int mk=(k>>1);
int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k);
for(int i=0;i<n;i+=k){
int w=1;
for(int j=0;j<mk;++j){
int x=A[i+j],y=1LL*A[i+j+mk]*w%mod;
A[i+j]=x+y;if(A[i+j]>=mod)A[i+j]-=mod;
A[i+j+mk]=x-y;if(A[i+j+mk]<0)A[i+j+mk]+=mod;
w=1LL*w*wn%mod;
}
}
}
if(flag==-1){
int inv=pow_mod(n,mod-2);
for(int i=0;i<n;++i)A[i]=1LL*A[i]*inv%mod;
}return;
}
void Get_inv(int n){
if(n==1){
B[0]=pow_mod(A[0],mod-2);
return;
}
int now=(n>>1);
Get_inv(now);
static int tmp[maxn];
for(int i=0;i<now;++i)tmp[i]=A[i];
FFT(tmp,n,1);FFT(B,n,1);
for(int i=0;i<n;++i)B[i]=1LL*B[i]*(2-1LL*tmp[i]*B[i]%mod+mod)%mod;
FFT(B,n,-1);
memset(B+now,0,sizeof(int)*now);
}
int main(){
freopen("polypeptide.in","r",stdin);
freopen("polypeptide.out","w",stdout);
read(n);read(m);
for(int i=1;i<=m;++i){
read(k);
if(k<=n)A[k]++;
}A[0]--;if(A[0]<0)A[0]+=mod;
for(N=1;N<=n;N<<=1);N<<=1;
Get_inv(N);
int ans=-B[n];
ans=(ans%mod+mod)%mod;
printf("%d
",ans);
return 0;
}
第二题正解是用圆周卷积优化计算过程，也要写FFT
但是考试的时候没有看出来，于是就手写了一发bitset
结果压位大法好，暴力出奇迹
开O2的情况A掉了全部的数据QAQ
然而至今不能看懂题解
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define fastcall __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline))
using namespace std;
typedef long long LL;
const int maxn=100010;
int m,n,blo,k,lim,QAQ,TAT;
int ans=0x7fffffff;
char s[maxn];
LL A[maxn],B[maxn],S;
int L[maxn],R[maxn];
int Ans[maxn];
int Num[2000010];
int Q[maxn];
fastcall IL int Get_Num(LL v){
int sum=Num[v&lim];v>>=20;
sum+=Num[v&lim];v>>=20;
sum+=Num[v&lim];return sum;
}
fastcall IL void check(int S){
int sum=Get_Num(S);
int A=(S>>(m+1)&1),B=(S>>m&1);B^=1;
int tmp=(S&QAQ);
int now=(2*B-1)*tmp%n;
if(now<0)now+=n;
if(A==0)sum+=Ans[now];
else sum+=(n-Ans[now]);
if(sum<ans)ans=sum;
}
int main(){
freopen("virus.in","r",stdin);
freopen("virus.out","w",stdout);
scanf("%d%d",&m,&n);blo=60;
k=(n%blo==0?n/blo:n/blo+1);lim=(1<<20)-1;QAQ=(1<<m)-1;
for(int i=0;i<(1<<20);++i)Num[i]=Num[i>>1]+(i&1);
scanf("%s",s+1);
for(int i=1;i<=k;++i)L[i]=(i-1)*blo+1,R[i]=min(n,i*blo);
for(int i=1;i<=k;++i){
for(int j=L[i];j<=R[i];++j)A[i]=A[i]<<1|(s[j]-'0');
}
scanf("%s",s+1);
for(int i=1;i<=k;++i){
for(int j=L[i];j<=R[i];++j)B[i]=B[i]<<1|(s[j]-'0');
}
for(int i=0;i<n;++i){
int now=0;
for(int j=1;j<=k;++j)now+=Get_Num(A[j]^B[j]);
Ans[i]=now;now=(A[k]&1);
for(int j=1;j<=k;++j){
int tmp=(A[j]&1);
int len=R[j]-L[j];
A[j]>>=1;
if(now)A[j]|=(1LL<<len);
now=tmp;
}
}
int up=(1<<(m+2));
for(int i=0;i<up;++i)check(i);
printf("%d
",ans);
return 0;
}
第三题是个数论题
推导的式子很长
最后推导的结论是R(i)+i是积性的
然后就很好搞了QAQ
至于式子嘛，明天再补上(挖坑ing)(其实是因为并不会用编辑器写公式)
吐槽一下std，花式整数溢出啊，导致造的数据都是错的
考试的时候没有看出那个性质，于是只能写O(n^2)的暴力
正准备分块打表的时候吕老师问我做完了没有，我想了想反正分块打表也没有什么意思
就直接拿到数据测了QAQ
如果分块打表的话这道题目是50分QAQ直接暴力是20分
(然而正确的数据其实只有5个)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=1000010;
const int mod=1005060097;
typedef long long LL;
LL n,ans,inv;
int mu[maxn];
int p[maxn],cnt=0;
bool vis[maxn];
LL pow_mod(LL v,int p){
LL tmp=1;
while(p){
if(p&1)tmp=tmp*v%mod;
v=v*v%mod;p>>=1;
}return tmp;
}
void Get_Prime(){
mu[1]=1;
for(int i=2;i<=1000000;++i){
if(!vis[i]){
p[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt;++j){
if(1LL*i*p[j]>1000000)break;
int ip=i*p[j];
vis[ip]=true;
if(i%p[j]==0)break;
mu[ip]=-mu[i];
}
}return;
}
LL Get_mod(LL n){return n%mod;}
LL Get_ans(LL n){
LL la,sum=0;
for(LL i=1;i<=n;i=la+1){
LL now=n/i;
la=n/now;
sum=sum+Get_mod(la+i)*Get_mod(la-i+1)%mod*inv%mod*Get_mod(n/i)%mod;
if(sum>=mod)sum-=mod;
}return sum;
}
int main(){
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
scanf("%lld",&n);
Get_Prime();inv=pow_mod(2LL,mod-2);
int lim=(int)(sqrt(n));
for(int i=1;i<=lim;++i){
ans=ans+1LL*mu[i]*i*Get_ans(n/i/i)%mod;
if(ans<0)ans+=mod;
if(ans>=mod)ans-=mod;
}
ans=ans-Get_mod(n)*Get_mod(n+1)%mod*inv%mod;
if(ans<0)ans+=mod;
if(ans>=mod)ans-=mod;
printf("%lld
",ans);
return 0;
}
明天就要去thusc报道了
希望自己能有个好成绩吧
感觉自己还是学的太少，写的太少，想的太少
以后不能继续颓下去了QAQ
UPD:感觉自己还是太naive了
第二题想了想发现是一道很简单的题目QAQ FFT的优化也很容易理解
第三题的式子就一直坑着吧，实在是不会用编辑器写公式QAQ
算了，贴一发题解吧
然后有了式子就随便搞了QAQ
UPD：第二题在去T大的火车上突然想出来了
我们考虑时间复杂度的瓶颈在于计算右移后两个串异或后1的个数
不妨考虑计算两个串对应位上都是1的个数
不难发现将第一个串反序之后对两个串做FFT
可以计算对应为都是1的个数，而当我们把第一个串倍长之后
一遍FFT就可以计算右移0-(n-1)位的所有答案
之后我们把两个串都取反再做一次，可以统计对应位都是0的个数
最后枚举选择方案O(1)统计答案即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define G 3
using namespace std;
const int mod=998244353;
const int maxn=300010;
int m,n,L,N,QAQ,ans=0x7fffffff;
char a[maxn],b[maxn];
int A[maxn],B[maxn],C[maxn];
int Ans[maxn],rev[maxn];
int Num[20000010];
int pow_mod(int v,int p){
int tmp=1;
while(p){
if(p&1)tmp=1LL*tmp*v%mod;
v=1LL*v*v%mod;p>>=1;
}return tmp;
}
void FFT(int *A,int n,int flag){
for(int i=0;i<n;++i)C[i]=A[rev[i]];
for(int i=0;i<n;++i)A[i]=C[i];
for(int k=2;k<=n;k<<=1){
int mk=(k>>1);
int wn=pow_mod(G,flag==1?(mod-1)/k:(mod-1)-(mod-1)/k);
for(int i=0;i<n;i+=k){
int w=1;
for(int j=0;j<mk;++j){
int x=A[i+j],y=1LL*A[i+j+mk]*w%mod;
A[i+j]=x+y;if(A[i+j]>=mod)A[i+j]-=mod;
A[i+j+mk]=x-y;if(A[i+j+mk]<0)A[i+j+mk]+=mod;
w=1LL*w*wn%mod;
}
}
}
if(flag==-1){
int inv=pow_mod(n,mod-2);
for(int i=0;i<n;++i)A[i]=1LL*A[i]*inv%mod;
}return;
}
void Get_flip(){
int lim=(n>>1);
for(int i=1;i<=lim;++i)swap(a[i],a[n-i+1]);
}
void Get_rev(){
for(int i=1;i<=n;++i){
if(a[i]=='1')a[i]='0';
else a[i]='1';
}
for(int i=1;i<=n;++i){
if(b[i]=='1')b[i]='0';
else b[i]='1';
}return;
}
void Get_FFT(){
memset(A,0,sizeof(A));memset(B,0,sizeof(B));
for(int i=1;i<=n;++i)A[i]=a[i]-'0';
for(int i=n+1;i<=(n<<1);++i)A[i]=A[i-n];
for(int i=1;i<=n;++i)B[i]=b[i]-'0';
FFT(A,N,1);FFT(B,N,1);
for(int i=0;i<N;++i)A[i]=1LL*A[i]*B[i]%mod;
FFT(A,N,-1);
for(int i=n+1;i<=(n<<1);++i)Ans[i-n-1]+=A[i];
}
void check(int S){
int sum=Num[S];
int A=(S>>(m+1)&1),B=(S>>m&1);B^=1;
int tmp=(S&QAQ);
int now=(2*B-1)*tmp%n;
if(now<0)now+=n;
if(A==0)sum+=(n-Ans[now]);
else sum+=Ans[now];
if(sum<ans)ans=sum;
}
int main(){
freopen("virusb.in","r",stdin);
freopen("virusb.out","w",stdout);
scanf("%d%d",&m,&n);QAQ=(1<<m)-1;
scanf("%s",a+1);scanf("%s",b+1);
for(N=1,L=0;N<=(n<<1);N<<=1,L++);
for(int i=0;i<N;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(L-1));
Get_flip();Get_FFT();
//for(int i=0;i<n;++i)printf("%d ",Ans[i]);
//printf("
");
Get_rev();Get_FFT();
//for(int i=0;i<n;++i)printf("%d ",Ans[i]);
//printf("
");
int up=(1<<(m+2));
for(int i=0;i<up;++i)Num[i]=Num[i>>1]+(i&1);
for(int i=0;i<up;++i)check(i);
printf("%d
",ans);
return 0;
}