Noip 模拟
目录
/(/to /text{比赛 link} /leftarrow/)
/(/to /text{题面+题解 link} /leftarrow/)
报数
线性筛+前缀和
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int cnt,p[N],qwq[N];
bitset <N> vis;
inline void get_prime(int x){
vis[1]=1;
for(int i=2;i<=x;++i){
if(!vis[i])
p[++cnt]=i;
for(int j=1;j<=cnt&&1ll*p[j]*i<=x;++j){
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
inline bool check(int x){
int res=0;
do{
res+=x%10;
x/=10;
}while(x);
return !vis[res];
}
signed main(){
get_prime(1e7);
for(int i=1;i<=1e7;++i){
qwq[i]=qwq[i-1];
if((!vis[i])&check(i))
++qwq[i];
}
int T,L,R,a,b,c,ans=0;
scanf("%d%d%d%d%d%d",&T,&L,&R,&a,&b,&c);
while(T--){
ans^=(qwq[R]-qwq[L-1]);
int x=((L^b)+a)%c+1,y=((R^b)+a)%c+1;
L=min(x,y),R=max(x,y);
}
printf("%d/n",ans);
}
随机
我们设 /(f_{i,j}/) 表示第 /(i/) 个单点查询的询问前面有 /(j/) 次别的修改操作的期望所得值
任意选 /(l,r/) 的总方案数是 /(n^2/) 的，而其中能够覆盖点 /(p_i/) 的总方案数是 /(2/cdot p_i /cdot (n-p_i+1)-1/) 的 (小于等于 /(p_i/) 的个数乘大于等于 /(p_i/) 的个数，正反都可以)
那后面的推式子就省略吧，比较复杂
然后再考虑划分的方案，这里采用的隔板法
对于第 /(i/) 个操作在第 /(j/) 个空隙的方案数等于
/[/binom{j-1}{i-1}/cdot /binom{q-k-j-1}{k-i-1}
/]
相当于左边 /(j-1/) 个空插 /(i-1/) 个板子，右边 /(q-k-j-1/) 个空插 /(k-i-1/) 个板子
这是原本的题解：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e3+5;
const int mod=998244353;
int n,q,k,V,ans,m;
int inv2,invm,invV;
int frac[N],p[N],invf[N],f[N][N];
inline int qpow(int x,int idx){
if(!idx) return 1;
int t=qpow(x,idx>>1);
return (idx&1)?t*t%mod*x%mod:t*t%mod;
}
inline int C(int x,int y){
//if(x==y||!y) return 1;
if(x<y||x<0||y<0) return 0;
return frac[x]*invf[y]%mod*invf[x-y]%mod;
}
inline int INV(int x){return qpow(x,mod-2);}
signed main(){
scanf("%lld%lld%lld%lld",&n,&q,&k,&V);
for(int i=1;i<=k;++i)
scanf("%lld",&p[i]);
frac[0]=invf[0]=1;
for(int i=1;i<=4000;++i){
frac[i]=frac[i-1]*i%mod;
invf[i]=INV(frac[i]);
}
inv2=INV(2),m=2ll*n*n%mod,invm=INV(m);
invV=(V+1)*inv2%mod;
for(int i=1;i<=k;++i){
int A=(2ll*p[i]*(n-p[i]+1)%mod-1+mod)%mod,B=(m-A+mod)%mod,invB=INV(B),res=1,pA=A*invm%mod,pB=B*invm%mod;
for(int j=1;j<=q-k;++j,res=res*pB%mod)
f[i][j]=(f[i][j-1]+pA*res%mod*(1+(j-1)*A%mod*invB%mod)%mod*invV%mod)%mod;
for(int j=1,mul=pB;j<=q-k;++j,mul=mul*pB%mod)
f[i][j]=(f[i][j]+mul*j%mod*A%mod*invB%mod*invV%mod)%mod;
}
for(int i=1;i<k;++i)
for(int j=1;j<=q-k;++j)
ans=(ans+C(j-1,i-1)*C(q-k-j-1,k-i-1)%mod*f[i][j]%mod)%mod;
printf("%lld/n",((ans*INV(C(q-k-1,k-1))%mod)+f[k][q-k])%mod);
}
单调栈
#include<bits/stdc++.h>
using namespace std;
const int N=305;
const int M=1e5+5;
const int mod=1e9+7;
struct node{
int x,w;
};
int n,m;
int g[N][N],f[N][M],b[N],fa[N];
vector <node> E[N],G[N];
inline void add(int x,int y,int z){
E[x].push_back({y,z});
g[x][y]=1;
}
inline void dfs(int x){
for(int i=1;i<=m;++i)
f[x][i]=1;
for(node i:G[x]){
int y=i.x,v=i.w;
//cout<<y<<endl;
dfs(y);
int res=0;
for(int j=1;j<=m;++j){
res=(res+f[y][j-v])%mod;
f[x][j]=1ll*f[x][j]*res%mod;
}
}
}
signed main(){
scanf("%d%d",&n,&m);
memset(g,-63,sizeof(g));
//cout<<g[0][0]<<endl;
for(int i=1;i<=n;++i){
scanf("%d",&b[i]);
g[i][i]=0;
if(b[i]==-1) continue;
if(b[i]) add(b[i],i,1);
for(int j=b[i]+1;j<i;++j)
add(i,j,0);
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(i==k||i==j||j==k) continue;
g[i][j]=max(g[i][j],g[i][k]+g[k][j]);
}
for(int i=1;i<=n;++i)
for(node x:E[i]){
//cout<<i<<" "<<x.x<<" "<<g[i][x.x]<<endl;
if(g[i][x.x]==1){
//cout<<i<<" "<<x.x<<" "<<x.w<<endl;
G[i].push_back({x.x,x.w});
fa[x.x]=i;
}
}
int ans=1;
for(int i=1;i<=n;++i){
if(fa[i]) continue;
dfs(i);
int sum=0;
for(int j=1;j<=m;++j)
sum=(sum+f[i][j])%mod;
ans=1ll*ans*sum%mod;
}
cout<<ans<<endl;
}
后缀数组
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/288779.html