| 316 | team0691 北京林业大学 |
3 | 09:56:39 |
1001 Tetrahedron
由体积相同可以化成：
然后枚举求期望，线性求逆元即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const int M = 6e6+7;
/*
int head[M],cnt=1;
void init(){cnt=1,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
const ll mod=998244353;
ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;
}
ll inv[M],inv2[M],sm[M];
void get_inverse()
{int i,p=mod;inv[1]=1;for(i=2;i<=6000000;++i)inv[i]=(p-p/i)*inv[p%i]%p;for(i=1;i<=6000000;++i)inv2[i]=inv[i]*inv[i]%mod,sm[i]=(sm[i-1]+inv2[i])%mod;
}
int main()
{get_inverse();int T;cin>>T;while(T--){int n;scanf("%d",&n);ll EX=0;EX=sm[n]*inv[n]%mod;ll ans=EX*3%mod;// cout<<"--- "<<EX<<" "<<24*qpow(5,mod-2)%mod*3%mod<<endl;;printf("%lld\n",ans);}return 0;
}
1003 Boring Game
观察可以发现，每次折叠有规律：
加入最初只有一张纸：
我们先把纸给标号：
12345678
一次折叠后：
4321
5678
二次折叠：
65
34
21
78
三次折叠：
7
2
3
6
5
4
1
8
刚好对应了最后从上往下的标号1-n。
这时候只需要再映射回去即可。。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int M=5e5+7;
int pw[27];
int b[M];
int pr[M];
int main()
{int T;cin>>T;int tp=1;for(int i=0;i<=20;i++)pw[i]=tp,tp*=2;while(T--){int N,k,x;scanf("%d%d",&N,&k);int nm=2*N*pw[k],n=N*2,m=nm/n,tp=0;vector<int>p[nm];for(int i=1;i<=2*N;i++){p[i].pb(0);for(int j=1;j<=pw[k];j++)scanf("%d",&x),p[i].pb(tp+1),b[++tp]=x;}for(int t=1;t<=k;t++){int n=N*pw[t],m=nm/n;vector<vector<int>>ans(n*2+1,vector<int>(m/2+1));for(int i=1;i<=n;i++)for(int j=1;j<=m/2;j++)ans[i][j]=p[n-i+1][m/2-j+1];for(int i=n+1;i<=2*n;i++)for(int j=1;j<=m/2;j++)ans[i][j]=p[i-n][j+m/2];// cout<<"iojko"<<endl;//for(int i=1;i<=N*2;i++)p[i].clear();for(int i=1;i<=n*2;i++)p[i].resize(m/2+1,0);for(int i=1;i<=n*2;i++)for(int j=1;j<=m/2;j++)p[i][j]=ans[i][j];}for(int i=1;i<=nm;i++)pr[p[i][1]]=b[i];for(int i=1;i<nm;i++)printf("%d ",pr[i]);printf("%d\n",pr[nm]);}return 0;
}
1009
分析可知：
我们考虑最后的折痕在最初的纸张上：（未折叠时有1条横线一条数线）
每次横向折叠会多2^i (i为横向折叠的次数)条横线，每次竖向折叠会多2^j (j为竖向折叠的次数)条竖线。
最终块数显然为：(2^i+1)*(2^j+1)
期望为：
用二项式定理和求和公式
化简为：
#include <iostream>
using namespace std;
#define mod 998244353
#define ll long longll Pow(ll a,ll b){ll res=1;while(b){if(b%2)res=res*a%mod;b>>=1;a=a*a%mod;}return res;
}int main(){int t;cin>>t;while(t--) {ll n;scanf("%lld", &n);ll res = 0;res = (res+2*Pow(3,n)%mod+Pow(2,n)*(Pow(2,n)+1)%mod)%mod;res=res*Pow(Pow(2,n),mod-2)%mod;cout << res << '\n';}}