本人小测分：100+30+0+50=180(￣ー￣)
由于本人比较菜，所以本人将自己写的题解和我老师写的题解放在一起帮助各位学习
第1题 字伏串
思路:
此题乃用容斥原理解,我们发现从正面想很复杂所以 (吾有一计),吾们可以反向思考,用方案总数-不满足情况的方案即可。
但是我们发现不满足情况的方案比较~ 难，可难不倒聪明的你，因为只有a或只有b的计算方法中有没有a也没有b的情况,(减掉就行了呗)额~
代码:
#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
long long ksm(long long a,long long b)
{long long r=1;while(b){if(b&1){r=r*a%998244353;}a=a*a%998244353;b>>=1;}return r%998244353;
}
int main(){scanf("%d",&T);while(T--){scanf("%lld",&n);long long aa=ksm(26,n),bb=ksm(24,n),cc=ksm(25,n)*2%998244353;printf("%lld\n",(aa-cc+bb+998244353)%998244353);}return 0;
}
第2题 数字屏障
思路:
代码:
#include<bits/stdc++.h>
using namespace std;
long long l,r,k,a[1000005],b[1000005],c[1000005],size,y=0;
bool v[1000005];
void work(long long x)
{for(long long i=(l+x-1)/x*x;i<=r;i+=x){int t=0;while(c[i-l]%x==0){c[i-l]/=x;t++;}b[i-l]=b[i-l]*(t*k+1)%998244353;}
}
int main(){for(int i=2;i<1000005;i++){if(v[i]==0)a[size++]=i;for (int j=0;j<size&&i*a[j]<1000005;j++){v[i*a[j]]=1;if(i%a[j]==0)break;}}scanf("%lld%lld%lld",&l,&r,&k);int n=r-l+1;for (int i=0;i<n;i++){b[i]=1;c[i]=l+i;}for(int i=0;i<size;i++){if(a[i]*a[i]>r)break;work(a[i]);}for(int i=0;i<1000005;i++){if(c[i]>1)b[i]=b[i]*(k+1)%998244353;y=(y+b[i])%998244353;}printf("%lld",y);return 0;
}
第3题 好学的panda
思路:
我们可以知道数组只能建m条的双向边(不然会炸),所以我们只能在Dijkstra中枚举1~n的点。但是这样时间复杂度会很高，于是聪明的你想到了只枚举u+1和u-1的点,因为|i-j|=|(i+1)-i|+|(i+2)-(i+1)|+...+|(j-1)-(j-2)|+|j-(j-1)|。
代码:
#include<bits/stdc++.h>
using namespace std;
long long n,m,d[500005];
bool vv[500005];
struct s{long long v,w;
};
vector<s>a[500005];
void dj()
{priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >q;q.push({0,1});for(int i=1;i<=n;i++){d[i]=LLONG_MAX;}d[1]=0;while(!q.empty()){int u=q.top().second,dd=q.top().first;q.pop();if(dd>d[u])continue;for(int v=u-1;v<=u+1;v++){if(v==u)continue;if(v>=1&&v<=n){long long w=abs(u-v);if(d[v]>d[u]+w){d[v]=d[u]+w;q.push({d[v],v});}}}for(int i=0;i<a[u].size();i++){int v=a[u][i].v,w=a[u][i].w;if(d[v]>d[u]+w){d[v]=d[u]+w;q.push({d[v],v});}}}
}
int main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){long long u,v,w;scanf("%lld%lld%lld",&u,&v,&w);a[u].push_back({v,w});a[v].push_back({u,w});}dj();for(int i=2;i<=n;i++){printf("%lld ",d[i]);}return 0;
}
第4题 传送门
思路：
代码：
#include<bits/stdc++.h>
using namespace std;
long long T,n,a[200005],b[40][200005];
long long dp[200005];
int main(){scanf("%lld",&T);while(T--){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}memset(dp,0,sizeof(dp));memset(b,0,sizeof(b));dp[1]=1;for(int i=0;i<30;i++){b[i][1]=(dp[1]*((a[1]>>i)&1))%998244353;}for(int i=2;i<=n;i++){for(int j=0;j<30;j++){dp[i]=(dp[i]+((a[i]>>j)&1)*b[j][i-1]%998244353)%998244353;}for(int j=0;j<30;j++){b[j][i]=(b[j][i-1]+((a[i]>>j)&1)*dp[i]%998244353)%998244353;}}printf("%lld\n",dp[n]);}return 0;
}