【LGR-054】洛谷10月月赛II
成功咕掉Codeforces Round #517的后果就是，我(mbox{T4})依旧没有写出来。(mbox{GG}) 。
浏览器
(mbox{popcount})为(0)的乘上(mbox{popcount})为(1)的就是答案。
因为两个数异或以后二进制位(1)的个数的奇偶性不会变。
至于计算(mbox{popcount})，预处理到根号，(O(1))计算即可。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define ll long long
int n,cnt[65536],sz[2];ll a,b,c,d,x;
int main(){
n=gi();a=gi();b=gi();c=gi();d=gi();x=gi();
for (int i=0;i<65536;++i) cnt[i]=cnt[i>>1]^(i&1);
for (int i=1;i<=n;++i){
x=(a*x%d*x%d+b*x%d+c)%d;
++sz[cnt[x&65535]^cnt[x>>16]];
}
printf("%lld
",1ll*sz[0]*sz[1]);
return 0;
}
大师
直接枚举公差，然后(O(n))扫一遍即可。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 20005;
const int mod = 998244353;
void inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}
int n,a[N],f[N],s[N],ans;
int main(){
n=gi();ans=n;
for (int i=1;i<=n;++i) a[i]=gi();
for (int i=-20000;i<=20000;++i){
for (int j=1;j<=n;++j){
if (a[j]-i>=0&&a[j]-i<=20000) f[j]=s[a[j]-i]+1;
else f[j]=1;
inc(s[a[j]],f[j]);inc(ans,f[j]);
}
inc(ans,mod-n);
for (int j=1;j<=n;++j) s[a[j]]=0;
}
printf("%d
",ans);return 0;
}
礼物
限制条件是如果一个数是另一个数的子集，那么两个数不能被放在同一个盒子里。
对关系建一个(DAG)，每个数向自己的所有子集连边，这样拥有拓扑关系的两个数就不能放在一起。答案就是(DAG)最长链长度。
构造方案的话，建立一个源点跑出到每个点(i)的最长路(f_i)，那么(i)就放到编号为(f_i)的盒子里就行了。
暴力建边(3^k)，注意当(n=2^k)即(a_i)取遍([0,2^k))时，建出这个(DAG)只需要连(O(k2^k))条边就行了。如果不满的话，还是把这(2^k)个点都建出来，不存在的点权值设为(0)，依然按上述做法做即可。
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 2e6+5;
int n,k,S,vis[N],f[N];vector<int>ans[21];
int main(){
n=gi();k=gi();S=(1<<k)-1;
for (int i=1;i<=n;++i) vis[gi()]=1;
for (int i=S;~i;--i){
if (vis[i]) ++f[i];
for (int j=1;j<S;j<<=1)
if (i&j) f[i^j]=max(f[i^j],f[i]);
}
printf("1
%d
",f[0]);
for (int i=S;~i;--i) if (vis[i]) ans[f[i]].push_back(i);
for (int i=1;i<=f[0];++i){
int sz=ans[i].size();printf("%d ",sz);
for (int j=0;j<sz;++j) printf("%d ",ans[i][j]);
puts("");
}
return 0;
}
口袋里的纸飞机
考虑计算每个数(x)会在多少种数列中被生成出来。进一步的，因为不能确定生成的(x)的个数，所以考虑计算(x)在多少数列中不会被生成出来。
对数列中的每个数对(P)取模，这样每个([0,P))就可以有(lfloorfrac RP floor)或(lfloorfrac RP floor+1)种不同选法。
如果(x=0)，那么只要满足数列中不存在(0)就可以了。
如果(x eq0)，那么对于每个(ain[1,P))，都有一个唯一且互不相同的(bin[1,P))使得(a imes b=xmod p)。这样相当于是对于一个(x eq0)，存在若干对无交集的((a,b))，要求同一对中的两个数不能同时出现。
这个东西的方案数怎么计算呢？你发现(nle500)，也许是......生成函数？
说一种显得不那么劝退的做法。考虑设(f_{i,j})表示用了前(i)对数填了(j)个位置的方案数，转移显然就是枚举当前这对数填多少个，同时因为位置可以任意选所以还得要乘上一个组合数。这样一写出来就会发现他就是一个指数生成函数卷积的形式，即(C_i=sum_{j=0}^iinom ijA_jB_{i,j})。
所以对于每个(x)大有概(O(P))的数对，每个数对可以用一个指数生成函数表示，把这(O(P))个生成函数暴力卷起来，就可以得到一个(O(n^2P^2))的做法。
然后因为每个([0,P))只有(lfloorfrac RP floor)或(lfloorfrac RP floor+1)种不同的选法，所以本质不同的数对只有(3)种。我们考虑一下每种数对的生成函数。令(B=lfloorfrac RP floor)。
数对中两个数都只有(B)种选法，考虑计算无限制减去两个数同时出现的方案：(A(x)=e^{Bx}e^{Bx}-(e^{Bx}-1)e^{Bx}-1)=2e^{Bx}-1)。其中(e^{Bx})实际上就是((e^x)^B)。
同理有(B(x)=e^{Bx}+e^{(B+1)x}-1,C(x)=2e^{(B+1)x}-1)。
假设对于某个(x)它三种数对的个数分别是(u,v,w)，那么我们就只需要计算(A^u(x) imes B^v(x) imes C^w(x) imes e^{Bx})就行了。
为什么还有一个(e^{Bx})？因为数列中还可以有(0)呀。这一点你有没有注意到呢？
所以我们先预处理出(A(x),B(x),C(x))的(P)次幂，这样预处理的复杂度可以做到(O(n^P))，然后对于每个(x)都可以(O(n^2))地计算卷积，总复杂度还是(O(n^2P))，可以获得(80)分的好成绩。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int mod = 1000000007;
inline void inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}
inline void dec(int &x,int y){x-=y;x<0?x+=mod:x;}
int fastpow(int a,int b){
int res=1;
while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
return res;
}
int n,P,R,B,S,inv[5005],C[505][505],ans;
struct poly{
int a[505];
poly(){memset(a,0,sizeof(a));}
poly operator * (poly b){
poly c;
for (int i=0;i<=n;++i)
for (int j=0;j<=i;++j)
c.a[i]=(c.a[i]+1ll*a[j]*b.a[i-j]%mod*C[i][j])%mod;
return c;
}
}dp[3][5005],zero;
int main(){
n=gi();P=gi();R=gi();B=R/P;
inv[1]=1;
for (int i=2;i<P;++i) inv[i]=inv[P%i]*(P-P/i)%P;
for (int i=C[0][0]=1;i<=n;++i)
for (int j=C[i][0]=1;j<=i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
for (int i=0;i<3;++i){
dp[i][0].a[0]=dp[i][1].a[0]=1;
for (int j=1;j<=n;++j) dp[i][1].a[j]=(fastpow(B+(i>0),j)+fastpow(B+(i>1),j))%mod;
for (int j=2;j<=P;++j) dp[i][j]=dp[i][j-1]*dp[i][1];
}
for (int i=0;i<=n;++i) zero.a[i]=fastpow(B,i);
S=fastpow(R,n);inc(ans,S);dec(ans,fastpow(R-B,n));
for (int i=1;i<P;++i){
int u=0,v=0,w=0;
for (int j=1;j<P;++j){
int x=inv[j]*i%P;
if (x<j){
if (j<=R-B*P) ++w;
else if (x<=R-B*P) ++v;
else ++u;
}
}
poly res=dp[0][u]*dp[1][v]*dp[2][w]*zero;
inc(ans,S);dec(ans,res.a[n]);
}
printf("%d
",ans);
return 0;
}
满分做法比较玄学。
首先，要求(A(x))的若干次幂其实只要预处理到根号就行了，即预处理(A(x),A^2(x),A^3(x)...)以及(A^{sqrt p}(x),A^{2sqrt p}(x),A^{3sqrt p}(x)...)这样预处理的复杂度可以降到(O(n^2sqrt P))，且对于一个(x)仍可以做到(O(n^2))计算。
然后后本部分仍是复杂度瓶颈？发现对于每个(x)答案只与三种数对的个数(u,v,w)有关，所以加个记忆化......就能过了？
司说本质不同的数对数量是(O(sqrt P))的，那......就是吧。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int mod = 1000000007;
inline void inc(int &x,int y){x+=y;x>=mod?x-=mod:x;}
inline void dec(int &x,int y){x-=y;x<0?x+=mod:x;}
int fastpow(int a,int b){
int res=1;
while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
return res;
}
int n,P,R,B,sqr,S,inv[5005],C[505][505],ans;
struct poly{
int a[505];
poly(){memset(a,0,sizeof(a));}
poly operator * (poly b){
poly c;
for (int i=0;i<=n;++i)
for (int j=0;j<=i;++j)
c.a[i]=(c.a[i]+1ll*a[j]*b.a[i-j]%mod*C[i][j])%mod;
return c;
}
}dp[3][2][80],zero;
map<pair<pair<int,int>,int>,int>M;
int calc(int u,int v,int w){
return (dp[0][0][u%sqr]*dp[0][1][u/sqr]*dp[1][0][v%sqr]*dp[1][1][v/sqr]*dp[2][0][w%sqr]*dp[2][1][w/sqr]*zero).a[n];
}
int main(){
n=gi();P=gi();R=gi();B=R/P;while (sqr*sqr<P) ++sqr;
inv[1]=1;for (int i=2;i<P;++i) inv[i]=inv[P%i]*(P-P/i)%P;
for (int i=C[0][0]=1;i<=n;++i)
for (int j=C[i][0]=1;j<=i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
for (int i=0;i<3;++i){
dp[i][0][0].a[0]=dp[i][1][0].a[0]=dp[i][0][1].a[0]=1;
for (int j=1;j<=n;++j) dp[i][0][1].a[j]=(fastpow(B+(i>0),j)+fastpow(B+(i>1),j))%mod;
for (int j=2;j<=sqr;++j) dp[i][0][j]=dp[i][0][j-1]*dp[i][0][1];
for (int j=1;j<=sqr;++j) dp[i][1][j]=dp[i][1][j-1]*dp[i][0][sqr];
}
for (int i=0;i<=n;++i) zero.a[i]=fastpow(B,i);
S=fastpow(R,n);inc(ans,S);dec(ans,fastpow(R-B,n));
for (int i=1;i<P;++i){
int u=0,v=0,w=0;
for (int j=1;j<P;++j){
int x=inv[j]*i%P;
if (x<j){
if (j<=R-B*P) ++w;
else if (x<=R-B*P) ++v;
else ++u;
}
}
pair<pair<int,int>,int>pr=make_pair(make_pair(u,v),w);
if (M.find(pr)==M.end()) M[pr]=calc(u,v,w);
inc(ans,S);dec(ans,M[pr]);
}
printf("%d
",ans);return 0;
}