次芝麻
题解
大力打表,发现快速幂,
例如初始$5$ $6$,那么第一次就是$5*2\%11=10$,$6*2\%11=1$.
代码
#include<bits/stdc++.h> using namespace std; #define ll long long ll n,m,k,d; ll g(ll x,ll k,ll s=1){ for(;k;k>>=1,x=x*x%d) if(k&1) s=s*x%d; return s; } int main(){ scanf("%lld%lld%lld",&n,&m,&k); d=n+m; printf("%lld ",min((n*g(2,k))%d,(m*g(2,k))%d)); }
喝喝喝
题解
把$a[i]\%a[j]=k$转化为$a[i]-k=y*a[i]$,
开桶维护$a[i]-k$
每次枚举$y$,看桶里是否有对应值,找到当前$i$左侧的最右能形成坏对的$v$,然后坏对个数就是$v$,,最后容斥就完了
考试时打的$n^2$,剪一个小枝能$70$分,然而我没减
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 4444444 ll a[A],ve[A],tong[A]; ll n,K,ans=0,maxx=0,jc=0; int main(){ scanf("%lld%lld",&n,&K); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),maxx=max(maxx,a[i]); ll num=0; for(ll i=1;i<=n;i++){ ve[i]=max(ve[i],ve[i-1]); if(a[i]<K) continue ; ll maxid=0; for(ll b=0;b*a[i]<=maxx;b++) if(tong[b*a[i]]) maxid=max(maxid,tong[b*a[i]]); tong[a[i]-K]=i; if(a[i]==K) continue ; if(maxid!=i) ve[i]=max(maxid,ve[i]); } for(ll i=1;i<=n;i++) if(ve[i]) ans+=(ve[i]); printf("%lld ",n*(n+1)/2-ans+jc); }
长寿花
题解
部分分状压$dp$,然而很难打,打了状压就陷进去了,具体$m$不用考虑
#include<iostream> #include<cstring> #include<cstdio> #include<bitset> #define LL long long using namespace std; int n,m,p; int a[1000010]; LL g[1010][1<<11],t[1<<11]; LL f[1010][1<<11]; LL poww(LL a,int b) { LL ans=1; while(b) { if(b&1)ans=ans*a%p; a=a*a%p;b=b>>1; } return ans; } inline int read(); signed main() { n=read(),m=read(),p=read(); for(int i=1;i<=n;i++)a[i]=read(); if(m<=10) { for(int i=1;i<=n;i++) for(int k=0;k<(1<<m);k++) { int tem=k,num=0;while(tem){num+=tem&1;tem=tem>>1;} g[i][k]=num*poww(num-1,a[i]-1)%p; } for(int i=1;i<=n;i++) { for(int k=0;k<(1<<m);k++) for(int l=0;l<(1<<m);l++) if(l!=k&&(l|k)==k)g[i][k]=((g[i][k]-g[i][l])%p+p)%p; } LL sum=0; for(int k=0;k<(1<<m);k++)f[1][k]=g[1][k],sum=(sum+f[1][k])%p; for(int i=2;i<=n;i++) { for(int k=0;k<(1<<m);k++) f[i][k]=((sum-f[i-1][k])%p+p)%p*g[i][k]%p; sum=0; for(int k=0;k<(1<<m);k++) sum=(sum+f[i][k])%p; } /* for(int i=1;i<=n;i++) for(int k=0;k<(1<<m);k++) { bitset<3>t(k); cout<<i<<" "<<t<<" "<<g[i][k]<<endl; }*/ printf("%lld ",sum%p); return 0; } } inline int read() { int s=0,f=1;char a=getchar(); while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();} while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();} return s*f; }
正解
设$f[i][j]$为到第$i$层,当前颜色$j$种
$f[i][j]=sumlimits_{k=1}^{k<=a[i-1]} f[i-1][k](之前的方案数贡献)*(当前层方案数)-(和上一层重合的)$
当前层可看作$j$个集合,相同集合元素互不相邻
$g[i][j]$表示$i$个元素放$j$个集合
考虑递推
当前值可以是之前一个集合
$g[i][j]=g[i-1][j]*(j-1)$解释一下
不能和之前相同集合相邻
$g[i][j]=g[i-1][j-1]*j$
也可以是一个新的集合,你之前知道$j-1$个集合,但你不知道当前新增是哪一个
去重,颜色集合相同则颜色数相同
$f[i][j]=sumlimits_{k=1}^{k<=a[i-1]} f[i-1][k]*g[a[i]][j]*C[a[i]][j]-f[i-1][j]*g[a[i]][j]$
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 5555 #define maxn 3333333 ll a[maxn],bj[maxn],prime[maxn],t[maxn]; long long g[A][A],f[2][maxn],C[maxn]; long long sum; ll n,m,K,ans=0,maxx=0,jc=0,mod; void debuger_g(); void jia(ll x){ // printf("+x=%lld bj=%lld ",x,bj[x]); while(x>1){ t[bj[x]]++; x=x/bj[x]; } } void jian(ll x){ // printf("-x=%lld bj=%lld ",x,bj[x]); while(x>1){ t[bj[x]]--; x=x/bj[x]; } } void get_prime(ll o){ ll gby=o; for(ll i=2;i<=gby;i++){ if(!bj[i]){ prime[++prime[0]]=i; bj[i]=i; } for(ll j=1;j<=prime[0]&&prime[j]*i<=gby;j++){ bj[i*prime[j]]=prime[j]; if((i%prime[j])==0) break ; } } } ll get_(){ ll ans=1; for(ll i=1;i<=prime[0];i++){ for(ll j=1;j<=t[prime[i]];j++) ans=1ll*ans*prime[i]%mod; // printf("ans=%lld t[%lld]=%lld prime=%lld ",ans,i,t[prime[i]],prime[i]); } return ans; } void get_C(){ ll gby=min(m,5000ll); for(ll i=1;i<=gby;i++){ jia(m-i+1); jian(i);C[i]=get_(); // printf("C[%lld]=%lld ",i+1,C[i+1]); } } int main(){ scanf("%lld%lld%lld",&n,&m,&mod); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),maxx=max(maxx,a[i]); g[1][1]=1;g[2][2]=2; for(ll i=3;i<=5000;i++) for(ll j=2;j<=i&&j<=m;j++) g[i][j]=((j-1)*g[i-1][j]%mod+g[i-1][j-1]*j%mod)%mod; get_prime(m); get_C(); for(ll j=1;j<=a[1];j++){//处理出来i==1的情况 f[1][j]=C[j]*g[a[1]][j]%mod; sum=(sum+f[1][j])%mod; } for(ll i=2;i<=n;i++){ for(ll j=0;j<=maxx;j++) f[i&1][j]=0; for(ll j=1;j<=a[i];j++){ f[i&1][j]=(C[j]%mod*g[a[i]][j]%mod*sum%mod-(f[(i-1)&1][j]*g[a[i]][j]%mod)%mod+mod)%mod; } sum=0; for(ll j=1;j<=a[i];j++) sum=(sum+f[i&1][j])%mod; } printf("%lld ",sum); }