Noip模拟13 2021.7.13：再刚题，就剁手&&生日祭
2024-09-29 23:17:30
T1 工业题
这波行列看反就非常尴尬。。。。。口糊出所有正解想到的唯独行列看反全盘炸列（因为和T1斗智斗勇两个半小时。。。）
这题就是肯定是个O(n+m)的，那就往哪里想，a，b和前面的系数分开求，前面系数显然是小学学过的走步数方法问题，排列组合搞掉就行，a，b分别是向下走和向右走的步数。然后会打快速幂，会打费马小定理，会组合数学就可以过掉。这里关于系数有两种不同求法。
第一个是打表出的规律，第二个是按照(i,j)(n,m)的位置求得。
1 #include<bits/stdc++.h>
2 #define int long long
3 #define write(X) printf("%lld\n",X)
4 #define Min(A,B) ((A)<(B)?(A):(B))
5 #define Max(A,B) ((A)>(B)?(A):(B))
6 using namespace std;
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13 const int NN=5000005,p=998244353;
14 int n,m,a,b,s[NN],t[NN],diss[NN],dist[NN],pws[NN],pwt[NN];
15 int h[NN];
16 inline void mul(){ h[0]=1;for(int i=1;i<=5000000;i++) h[i]=h[i-1]*i%p;}
17 inline int qmo(int a,int b){
18 int ans=1,c=p; a%=c;
19 while(b){
20 if(b&1) ans=(ans*a)%c;
21 b>>=1; a=(a*a)%c;
22 } return ans;
23 }
24 inline int phi(int a){
25 int ans=1,b=p-2,c=p; a%=c;
26 while(b){
27 if(b&1) ans=(ans*a)%c;
28 b>>=1; a=(a*a)%c;
29 } return ans;
30 }
31 inline int C(int n,int m){
32 if(m==0) return 1;
33 return h[n]*phi(h[m])%p*phi(h[n-m])%p;
34 }
35 namespace WSN{
36 inline int main(){
37 n=read();m=read();a=read()%p;b=read()%p; mul();
38 int wsn=0;
39 for(int i=1;i<=n;i++) s[i]=read()%p;
40 for(int i=1;i<=m;i++) t[i]=read()%p;
41 for(int i=1;i<=n;i++){
42 int c=C(i+m-2,m-1);
43 diss[n-i+1]=s[n-i+1]*c%p;
44 }
45 for(int i=1;i<=m;i++){
46 int c=C(n+i-2,i-1);
47 dist[m-i+1]=t[m-i+1]*c%p;
48 }
49 for(int i=1;i<=n;i++){
50 pws[i]=qmo(a,m)*qmo(b,n-i)%p;
51 wsn=(wsn+diss[i]*pws[i]%p)%p;
52 }
53 for(int i=1;i<=m;i++){
54 pwt[i]=qmo(b,n)*qmo(a,m-i)%p;
55 wsn=(wsn+dist[i]*pwt[i]%p)%p;
56 }
57 write(wsn);
58 return 0;
59 }
60 }
61 signed main(){return WSN::main();}
小马的方法
1 #include<bits/stdc++.h>
2 #define int long long
3 #define write(X) printf("%lld\n",X)
4 #define Min(A,B) ((A)<(B)?(A):(B))
5 #define Max(A,B) ((A)>(B)?(A):(B))
6 using namespace std;
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13 const int NN=5000005,p=998244353;
14 int n,m,a,b,s[NN],t[NN],diss[NN],dist[NN],pws[NN],pwt[NN],h[NN];
15 inline int inv(int a){
16 int ans=1,b=p-2,c=p; a%=c;
17 while(b){
18 if(b&1) ans=(ans*a)%c;
19 b>>=1; a=(a*a)%c;
20 } return ans;
21 }
22 inline void mul(){ h[0]=h[1]=1;for(int i=2;i<=5000000;i++) h[i]=h[i-1]*i%p;}
23 inline int C(int n,int m){
24 if(m==0) return 1;
25 if(n==m) return 1;
26 return h[n]*inv(h[m])%p*inv(h[n-m])%p;
27 }
28 inline int qmo(int a,int b){
29 int ans=1,c=p; a%=c;
30 while(b){
31 if(b&1) ans=(ans*a)%c;
32 b>>=1; a=(a*a)%c;
33 } return ans;
34 }
35 namespace WSN{
36 inline int main(){
37 n=read();m=read();a=read()%p;b=read()%p;
38 mul(); int wsn=0;
39 for(int i=1;i<=n;i++){
40 int x=read()%p;
41 wsn=(wsn+C(n+m-i-1,m-1)*x%p*qmo(a,m)%p*qmo(b,n-i)%p)%p;
42 }
43 for(int i=1;i<=m;i++){
44 int y=read()%p;
45 wsn=(wsn+C(n+m-i-1,n-1)*y%p*qmo(b,n)%p*qmo(a,m-i)%p)%p;
46 }
47 write(wsn);
48 return 0;
49 }
50 }
51 signed main(){return WSN::main();}
正常方法
T2 卡常题
看到题解这句话就知道又是超纲题。。。。并不太懂。。。
听完讲就比较会了，将Y看成边，X看成点，这样的话先找到环上的一条边，然后删掉，分别用这条边的（u，v）为根跑一遍没有上司的舞会
然后呢，这波是STL的大胜利！！！
1 #include<bits/stdc++.h>
2 #define write(X) printf("%d\n",X)
3 #define Min(A,B) ((A)<(B)?(A):(B))
4 #define Max(A,B) ((A)>(B)?(A):(B))
5 using namespace std;
6 inline int read(){
7 int x=0,f=1; char ch=getchar();
8 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
9 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
10 return x*f;
11 }
12 const int NN=1e6+1e3;
13 int n,a,b,rt1,rt2;
14 bool vis[NN];
15 struct SNOW{int from,to,next;}; SNOW e[NN<<1]; int head[NN],rp;
16 map<int,int> mp[NN];
17 vector<int> vc[NN];
18 int dp[NN][2][2],w[NN];
19 inline void add(int x,int y){
20 e[++rp]=(SNOW){x,y,head[x]}; head[x]=rp;
21 e[rp+n]=(SNOW){y,x,head[y]}; head[y]=rp+n;
22 }
23 inline void dfs1(int x){
24 vis[x]=true;
25 for(int i=head[x];i;i=e[i].next) if(!vis[e[i].to]){
26 vc[x].push_back(e[i].to);
27 vc[e[i].to].push_back(x);
28 mp[x][e[i].to]=1;
29 mp[e[i].to][x]=1;
30 dfs1(e[i].to);
31 }
32 }
33 inline void dps(int x,int op){
34 dp[x][1][op]+=w[x]; vis[x]=1;
35 for(int i=0;i<vc[x].size();i++) if(!vis[vc[x][i]]){
36 int to=vc[x][i];
37 dps(to,op);
38 dp[x][0][op]+=dp[to][1][op];
39 dp[x][1][op]+=Min(dp[to][0][op],dp[to][1][op]);
40 }
41 }
42 namespace WSN{
43 inline int main(){
44 n=read(); a=read(); b=read();
45 for(int i=1;i<=n;i++){
46 int x=read(),y=read();
47 add(x,y); w[x]+=a; w[y]+=b;
48 }
49 dfs1(1);
50 for(int i=1;i<=n;i++){
51 int f=e[i].from,t=e[i].to;
52 if(mp[f].find(t)==mp[f].end()) rt1=f,rt2=t;
53 }
54 for(int i=1;i<=n;i++) vis[i]=0;
55 dps(rt1,0);
56 for(int i=1;i<=n;i++) vis[i]=0;
57 dps(rt2,1);
58 int ans=Min(dp[rt2][1][1],dp[rt1][1][0]);
59 write(ans);
60 return 0;
61 }
62 }
63 signed main(){return WSN::main();}
比较吊的STL打法（最劣解）
就非常带劲。。。。
T3 玄学题
第一眼看确实比较玄学。。。。这指数上套一个sigma就比较离谱，不过，既然看到了-1的指数，那我们就有必要讨论其奇偶性。
发现一个数的约数个数为奇数的情况当且仅当这个数是完全平方数。那么，我们只要找到这个值，便可以求出指数奇偶性，然后累加即可。
1 #include<bits/stdc++.h>
2 #define int long long
3 #define write(X) printf("%lld\n",X)
4 #define Min(A,B) ((A)<(B)?(A):(B))
5 #define Max(A,B) ((A)>(B)?(A):(B))
6 using namespace std;
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13
14 const int NN=1e7+1e5;
15 int n,m,pw[NN],cnt,p[NN],ans;
16 bool vis[NN];
17
18 namespace WSN{
19 inline int main(){
20 n=read(); m=read();
21 for(int i=2;i*i<=n;i++){
22 pw[++cnt]=i*i;
23 vis[i*i]=1;
24 }
25 for(int i=1;i<=cnt;i++)
26 for(int j=1;j*pw[i]<=n;j++)
27 if(vis[j]) continue;
28 else p[j*pw[i]]=j;
29 for(int i=1;i<=n;i++){
30 if(!p[i]) p[i]=i;
31 int numji=sqrt(m/p[i]);
32 ans+=numji%2==0? 1:-1;
33 }
34 write(ans);
35 return 0;
36 }
37 }
38 signed main(){return WSN::main();}
END
这次考试发现特殊性质可以帮助推出正解，并且数据范围可以知道此题的循环大体长什么样子。然后就是————
不要再刚题了！！！！！！！！！！！！！！！！！
最后给自己来一句：生日快乐～
最新文章
- 引用类型-Array类型
- redis命令全集（自用）
- maven的配置环境及Myeclipse部署Maven项目
- Scala之OOP
- 【python】Head First Python（五）
- zigbee学习之路(九):串口(发送)
- phonegap文件，目录操作以及网络上传，下载文件（含demo）
- VC中打开对话框选择文件和文件夹
- android桌面快捷方式跳转到指定activity
- ERROR 23 (HY000) at line 29963: Out of resources when opening file
- ANDROID_MARS学习笔记_S01原始版_018_SERVICE之Parcel
- 【HDOJ】1394 Minimum Inversion Number
- 使用ItextSharp产PDF完整操作
- CodeForces 21C Stripe 2 构造题
- Facebook开源的基于SQL的操作系统检测和监控框架:osquery
- D3D中一些接口的变化和VS配置关联的方法
- Django REST Framework 最佳实践
- 2D射影几何和变换
- pycharm安装package时报错
- CCCC L2-013. 红色警报 连通分量