NOIP模拟测试34「次芝麻·呵呵呵·长寿花」
rtrt
3月 14, 2025
归档于 2019-09-03 17:53
次芝麻
题解
大力打表,发现快速幂,
例如初始$5$ $6$,那么第一次就是$52%11=10$,$62%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\n",min((n*g(2,k))%d,(m*g(2,k))%d));
}
View Code
喝喝喝
题解
把$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*(n+1)/2-ans+jc);
}
View Code
长寿花
题解
部分分状压$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\n",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;
}
Al_Ca的代码
正解
设$f[i][j]$为到第$i$层 ,当前颜色$j$种
$f[i][j]=\sum\limits_{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]=\sum\limits_{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\n",x,bj[x]);
while(x>1){
t[bj[x]]++;
x=x/bj[x];
}
}
void jian(ll x){
// printf("-x=%lld bj=%lld\n",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\n",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\n",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\n",sum);
}
View Code