1009 Paperfolding
把一张矩形纸折n次，每次折可以从上往下折，或从下往上折,或从左往右折，或从右往左折
这样一共有4^n种折法，折好后再把纸横切一刀，竖切一刀，再把纸展开，问展开后期望是多少张纸
看起来好难的一题，比赛刚开始的时候，我还没读完题时，旁边的人都开始折纸了，我想：这题真的要动手折纸吗？然而我开始分析的时候，就忍不住开始折纸了2333
分析出来后就不难了
分析：
- 从上往下折等价于从下往上折，从左往右折等价于从右往左折，自己拿张纸折几下，靠直觉得出这个结论
- 自己折折纸，可以发现从左往右折a次，从上往下折b次,最后展开是((1<<a)+1)*((1<<b)+1)张纸(我找的规律，没去证明，就感觉是这样)
计算：
一共2^n种折法，分母就是2^n,
从左往右一共折a次，从上往下一共折n-a次的情况是C(n,a)种(我还不会打数学符号啊啊啊),贡献为C(n,a)*((1<<a)+1)*((1<<(n-a))+1)
检验一下,a的范围是0到n,C(n,0)+C(n,1)+C(n,2)+...+C(n,n)= 2^n种
分子就是把C(n,a)*((1<<a)+1)*((1<<(n-a))+1)累加起来（a从0到n）
C(n,a)*((1<<a)+1)*((1<<(n-a))+1) = C(n,a) * [ (1<<n) + (1<<a) + (1<<(n-a)) + 1] = [C(n,a)*(1<<n)] + [C(n,a)*(1<<a)] + [C(n,a)*(1<<(n-a))] + [C(n,a)]
[C(n,a)*(1<<n)] 累加起来等于 4^n,除以分母后等于 2^n
[C(n,a)*(1<<a)]累加起来等于(2+1)^n = 3^n,除以分母后等于 3^n * inv(2^n)
[C(n,a)*(1<<(n-a))]累加起来，根据对称性，它等于[C(n,a)*(1<<a)]
[C(n,a)]累加起来等于2^n ，除以分母后等于1
#include<iostream>
#include<algorithm>
using namespace std;
const long long MOD = 998244353;
long long qpow(long long n, long long p) {
long long ret = 1;
for (; p; p >>= 1, n = n * n % MOD)
if (p & 1)
ret = ret * n % MOD;
return ret;
}
long long inv(long long a) {
return qpow(a, MOD - 2);
}
int main()
{
int T;
long long n;
cin>>T;
while(T--){
scanf("%lld",&n);
long long res, tt, ni;
res = qpow(2,n);
tt = 2*qpow(3,n);
ni = inv(res);
tt = tt * ni % MOD;
res += tt + 1;
res %= MOD;
printf("%lld\n",res);
}
return 0;
}
1001 Tetrahedron
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 6e6 + 7;
const int MOD = 998244353;
// const int INF = ;
// const int DIRX[] = {};
// const int DIRY[] = {};
int ept[MAXN];
inline int getpow(int a, int b)
{
int ret = 1;
for (; b; b >>= 1, a = a * a % MOD)
if (b & 1)
ret = ret * a % MOD;
return ret;
}
void pre()
{
int tmp = 0;
for (int i = 1; i <= 6e6; ++i)
{
tmp += getpow(i * i % MOD, MOD - 2);
tmp %= MOD;
ept[i] = tmp;
}
}
int T;
int n;
int ans;
int32_t main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
pre();
cin >> T;
while (T--)
{
cin >> n;
ans = (3 * ept[n] % MOD) * getpow(n, MOD - 2) % MOD;
cout << ans << endl;
}
return 0;
}
1003 Boring Game
很恶心的一题,折叠3次的情况我根本画不出，这题耗了很长时间，差不多3小时的时候，大家都A不出题，这时突然有个队大叫A了！A了!然后我马上看下榜单，并没有什么变化，学长问他们哪题A了，他们说样例A了...xswl
关键是模拟构造order数组，折2次及以上是有构造规律的，折1次的情况是特判
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int zheng[203][2050];
int fan[203][2050];
int order[2050],neworder[2050];
int main()
{
int T,n,k,cnt;
cin>>T;
while(T--){
cin>>n>>k;
cnt = 0;
for(int i = (1<<k);i;i--){
order[i] = 0;
cnt++;
if(i % 2) {//正
for(int j = 1;j <= n;j++){
scanf("%d%d",&zheng[j][cnt],&fan[j][cnt]);
}
}
else{//反
for(int j = n;j ;j--){
scanf("%d%d",&fan[j][cnt],&zheng[j][cnt]);
}
}
}
int len = 2;
order[1] = 1 ;order[2] = 2;//折2次的情况把折1次的情况包括进去了，初始化就直接初始成折2次的情况
for(int e = 2;e <= k;e++){//从折2次开始构造
for(int i = 1;i<=len;i++){
int x = order[len-i+1];
if(x%2) neworder[i] = x * 2;
else neworder[i] = x * 2 - 1;
}
for(int i = len+1;i<=len*2;i++){
int x = order[i-len];
if(x%2) neworder[i] = x * 2 - 1;
else neworder[i] = x * 2;
}
len *= 2;
for(int i = 1;i <= len;i++){
order[i] = neworder[i];
//cout<<order[i]<<" ";
}
//cout<<endl;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j <= (1<<k) ;j++){
printf("%d ",zheng[i][order[j]]);
}
//printf("\n");
for(int j = 1;j < (1<<k) ;j++){
printf("%d ",fan[i][order[j]]);
}
printf("%d",fan[i][order[(1<<k)]]);
if(i!=n) printf(" ");
//printf("\n");
}
printf("\n");
}
return 0;
}
PE了2发，惊了，末尾多输出空格会PE
1012 Set1
一个集合为1,2,3,4,...,n ,n是奇数，每次操作是集合中会删掉一个最小的数，然后随机选一个数删除，重复进行这集合个操作直到集合中只剩下最后一个数
求1,2,3....分别为最后一个数的概率
分母 = 总的操作方案数 = (n-1)*(n-3)*(n-5)*...*2 = ((n-1)/2)! * 2^((n-1)/2)
1,2,3,...(n-1)/2是不可能成为最后一个数的
第 i 个数，在其后 n - i 个数必须要删完，也就是分子 = （n-i)! * 某个东西
比赛的时候就是这个某个东西算不来
关键的一点就是，在删这n - i个数中的某个数a时，在前 i - 1个数中删掉了剩余的最小的数b，这n - i 个a对应n - i个b,而这n - i 个 b 可以是前 i - 1个数里选出的 n - i 个数的任意组合，情况有C(i - 1,n - i)种,这 n - i 个 b确定后,前 i - 1 个数里剩下的数就可以任意删了
假设剩下的数有 re 个,任意删的方案数 = (n-1)*(n-3)*(n-5)*...*1 = (n-1)! / [(n-2)*(n-4)*...*2] = (n-1)! / { [(n-2)/2]! * 2^[(n-2)/2] }
某个东西 = C(i - 1,n - i) * (n - 1)! / { [(n-2)/2]! * 2^[(n-2)/2] }
主要就是没想到后n - i 个数对应前 i - 1个数中 n - i个数
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 5e6+7;
const long long MOD = 998244353;
long long fact[MAXN];
long long inv[MAXN];
void pre(){
fact[0] = 1;
for(int i = 1;i <= 5e6;i++)
fact[i] = fact[i-1] * i % MOD;
inv[1] = 1;
for (int i = 2; i <= 5e6; i++)
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
inv[0] = 1;
for (int i = 1; i <= 5e6; i++)
inv[i] = inv[i] * inv[i - 1] % MOD;
}
long long qpow(long long n, long long p) {
long long ret = 1;
for (; p; p >>= 1, n = n * n % MOD)
if (p & 1)
ret = ret * n % MOD;
return ret;
}
long long mod_inv(long long a){
return qpow(a,MOD-2);
}
long long C(int n,int m){
return fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
int T, n;
pre();
cin>>T;
long long MODINV2 = mod_inv(2);
while(T--){
cin>>n;
if(n == 1) {
printf("1\n");
continue;
}
long long fm, invfm;
fm = qpow(2,n/2)*fact[n/2]%MOD;
invfm = mod_inv(fm);
int pos = n / 2 + 1;
int re = 0;
long long tt = 1;
for(int i = 1;i < pos;i++) printf("0 ");
for(;pos <= n;pos++){
long long res = fact[n-pos];
res = res * C(pos-1,n-pos) % MOD;
long long ret ;
if(!re) ret = 1;
else{
ret = fact[re-1] * inv[(re-2)/2] % MOD * tt % MOD;
tt = tt * MODINV2 % MOD;
}
res = res * ret % MOD * invfm % MOD;
re += 2;
if(pos < n)printf("%lld ",res);
else printf("%lld\n",res);
}
}
return 0;
}