次芝麻

題解

大力打表,發現快速冪,

例如初始$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\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

?

轉載于:https://www.cnblogs.com/znsbc-13/p/11454329.html

總結

以上是生活随笔為你收集整理的NOIP模拟测试34「次芝麻·呵呵呵·长寿花」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。