1009.Paperfolding
题意
纸张对折，允许上下左右四个方向，给出n次操作，问n次折叠后从中心横竖裁剪后可得到多少张纸
思路
手动折纸发现左右是等价操作，上下也是
推出((2^i + 1) imes (2^{n-i} + 1))
(i)次上下，(n - i)次左右
数学期望为
$ E(x) = frac{1}{2n}sum_{i=0}n C_ni(2i + 1)(2^{n-i} + 1) =1 + 2^n + C_ni(2i+2{n-i})frac{1}{2n}=1 + 2^n+2 imes 3n/2n$因为((1 + 2)^n = C_n^i2^i)
代码
/*************************************************************************
> FileName:
> Author: Lance
> Mail: lancelot_hcs@qq.com
> Date: 9102.1.8
> Description:
************************************************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const double pi = acos(-1.0);
const double eps = 1e-6;
const int mod = 998244353;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1000005;
//sacnf("%lf") printf("%f")
ll read()
{
ll x = 0,f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
ll t, n;
ll qpow(ll x, ll n, ll p) {
ll res = 1;
while (n) {
if (n & 1) {
res = res * x % p;
}
x = x * x % p;
n >>= 1;
}
return res;
}
ll tem[maxn];
ll rev(ll a) {
return qpow(a, mod - 2, mod);
}
void solve()
{
t = read();
while (t--) {
n = read();
ll tem = 2 * qpow(3, n, mod) % mod;
tem = tem * rev(qpow(2, n, mod)) % mod;
tem = (tem + 1 + qpow(2, n, mod)) % mod;
printf("%lld
", tem);
}
}
int main()
{
// freopen("F:/Overflow/in.txt","r",stdin);
// ios::sync_with_stdio(false);
solve();
return 0;
}
1003.Boring Game
题意
纸张折叠无聊的游戏
思路
根据题解:(比赛时没有看出这么简单的规律)[x 1left[ egin{matrix} 1 \2 \3 \4 \5 \6 \7 \8 \9 \10 \11 \12 \13 \14 \15 \16end{matrix} ight] o left[egin{matrix} 8&9\7&10\6&11\5&12\4&13\3&14\2&15\1&16 end{matrix} ight] o left[egin{matrix} 12&5&4&13\11&6&3&14\10&7&2&15\9&8&1&16 end{matrix} ight] ]发现规律，每次操作都是，上半部分翻转，置于左侧，下半部分上移，对齐上半部分
根据此规律模拟即可
代码
/*************************************************************************
> FileName:
> Author: Lance
> Mail: lancelot_hcs@qq.com
> Date: 9102.1.8
> Description:
************************************************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const double pi = acos(-1.0);
const double eps = 1e-6;
const int mod = 1e9 + 7;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1000005;
//sacnf("%lf") printf("%f")
ll read()
{
ll x = 0,f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
vector<int> G[1220];
int t, n, k;
ll qpow(ll n, ll x) {
ll res = 1;
while (x) {
if (x & 1) {
res = (res * n) % mod;
}
n = (n * n) % mod;
x >>= 1;
}
return res;
}
int a[maxn];
int tem[maxn];
void look(int k) {
for (int i = 1; i <= k; i++) {
for (auto it : G[i]) {
cout << it << ' ';
}
puts("");
}
}
void solve()
{
t = read();
while (t--) {
n = read(), k = read();
ll all = 2 * n * qpow(2, k);
ll row = qpow(2, k);
for (int i = 0; i <= row; i++) G[i].clear();
for (int i = 1; i <= all; i++) {
a[i] = read();
G[1].push_back(a[i]);
}
for (int i = 1; i <= k; i++) {
int tem = 1 << (i - 1); // 操作行数
int con = all / (tem * 2); // 当前中点
for (int j = 1; j <= tem; j++) {
int to = 2 * tem - j + 1;
reverse(G[j].begin(), G[j].begin() + G[j].size() / 2); // 反转
G[to].assign(G[j].begin(), G[j].begin() + G[j].size() / 2); // 拷贝
for (int k = 0; k < con; k++) G[j][k] = G[j][k + con];
for (int k = 1; k <= con; k++) G[j].pop_back();
// look(tem * 2);
}
}
for (int i = 0; i < n * 2; i++)
for (int j = row; j >= 1; j--) {
if (j != row || i != 0) printf(" ");
cout << G[j][i];
}
puts("");
}
}
/*
10
2 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1
1 2 3 4
1 2
1 2 3 4 5 6 7 8
*/
int main()
{
// freopen("F:/Overflow/in.txt","r",stdin);
// ios::sync_with_stdio(false);
solve();
return 0;
}
1012.Set1
题意
思路
代码
1007.Tree
题意
思路
代码