2020杭電多校5(補)
6270 ワード
1001 Tetrahedron
に言及
1つの直角四面体の3つの直角辺は([1,n])の範囲内でランダムで、直角頂点から対面までの距離の二乗逆数((frac{1}{h^2}))の期待値を求める.
構想
まずベクトル計算により(frac{1}{h^2}=frac{1}{a^2}+frac{1}{b^2}+frac{1}{c^2})が得られ,そこで(E(frac{1}{h^2})=3 E(frac{1}{a^2})quad,そのうちain[1,n])が発売される.
\[answer=\frac{3}{n}\sum_{i=1}^{n}\frac{1}{i^2}\(mod\quad 998244353)\]
逆元の前処理方法に注意してください.(inv[i]=mod-mod/i*inv[mod%i]).
コード#コード#
1003 Boring Game
に言及
テーブルの上にn枚の紙を重ねて、これらの紙を左から右にk回折り畳んで、全部で階層化します(2*n*(1<層、これらの層に対して1から番号をつけて、1組の折り畳み後の番号をあげて、折り畳む前にこれらの番号が上から下まで、左から右のシーケンスを聞きます.
構想
配列でシミュレーションし、折りたたむたびに折りたたまれた中点を見つけ、中点の上の逆順を下の配列に加えます.
コード#コード#
1009 Paperfolding
に言及
1枚の紙に、水平に折り、縦に折り、全部でn回((2^n)の折り方があることを意味する)行い、最後に紙を十字に切り、多くのブロックに分け、ブロック数の数学的期待を求める.
構想
水平にx回折り、縦にy回折り、折りたたんだ紙を広げてみると、切り裂いた跡は原紙を縦方向に(2^x)ナイフ、水平方向に(2^y)ナイフを切ったので、全部で((2^x+1)*(2^y+1))ブロックが切り裂かれています.
だから望むのは
\[\begin{align} ans &=\frac{1}{2^n}\\sum_{i=0}^{n}\C_n^i\(2^i+1)*(2^{n-i}+1)\\&=\frac{1}{2^n}\\sum_{i=0}^{n}\C_n^i\(2^n+2^i+2^{n-i}+1)\\&= 2^n+1+2*\frac{1}{2^n}\sum_{i=0}^{n}\C_n^i 2^i\\&= 2^n+1+2*\frac{3^n}{2^n}\end{align}\]
コード#コード#
1012 Set1
に言及
1つの初期要素が({1,...,n})の集合は、1つの要素しか残っていないまで2つの操作を順次行います.コレクションの最小要素 を除去する.ランダムに要素を除去する 数字ごとに残された期待値を聞く
構想
(i)番目の要素については、左の要素の数が右の要素の数より少なくなく、右の要素の数が2番目の操作で除去されることが残りの条件です.
そこで、それぞれの数について残されたシナリオ数は(cnt[i]=C_{r}^{l}r!\frac{( r-l)!}{(2!)^{(r-l)/2}\frac{r-l}{2}})のうち、(l)は(i)の左の数の個数であり、(r)は(i)の右の数の個数である.
答えは,各シナリオ数(cnt[i])をシナリオ数を除いて加算(sum)である.
コード#コード#
に言及
1つの直角四面体の3つの直角辺は([1,n])の範囲内でランダムで、直角頂点から対面までの距離の二乗逆数((frac{1}{h^2}))の期待値を求める.
構想
まずベクトル計算により(frac{1}{h^2}=frac{1}{a^2}+frac{1}{b^2}+frac{1}{c^2})が得られ,そこで(E(frac{1}{h^2})=3 E(frac{1}{a^2})quad,そのうちain[1,n])が発売される.
\[answer=\frac{3}{n}\sum_{i=1}^{n}\frac{1}{i^2}\(mod\quad 998244353)\]
逆元の前処理方法に注意してください.(inv[i]=mod-mod/i*inv[mod%i]).
コード#コード#
#include
#define ll long long
using namespace std;
const int maxn = 6e6 + 7;
const int mod = 998244353;
int T, n;
int ni[maxn], sum[maxn];
void init() {
ni[1] = sum[1] = 1;
for(int i = 2; i < maxn; i++) {
ni[i] = mod - 1LL * mod/i * ni[mod%i] % mod;
sum[i] = sum[i-1] + 1LL * ni[i] * ni[i] % mod;
sum[i] %= mod;
}
}
ll qpow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
init();
cin >> T;
while(T--) {
cin >> n;
cout << 1LL * sum[n] * 3 % mod * qpow(n, mod - 2) % mod << endl;
}
return 0;
}
1003 Boring Game
に言及
テーブルの上にn枚の紙を重ねて、これらの紙を左から右にk回折り畳んで、全部で階層化します(2*n*(1<層、これらの層に対して1から番号をつけて、1組の折り畳み後の番号をあげて、折り畳む前にこれらの番号が上から下まで、左から右のシーケンスを聞きます.
構想
配列でシミュレーションし、折りたたむたびに折りたたまれた中点を見つけ、中点の上の逆順を下の配列に加えます.
コード#コード#
#include
#define ll long long
using namespace std;
const int maxn = 5e5 + 7;
const int mod = 1e9 + 7;
int T, n, k;
vector v[maxn];
void slove(int l, int r) {
int mid = (l + r) / 2, now = mid + 1;
for(int i = mid; i >= l; i--) {
for(int j = v[i].size() - 1; j >= 0; j--) {
v[now].push_back(v[i][j]);
}
now++;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
cin >> T;
while(T--) {
cin >> n >> k;
int len = 2 * n * (1 << k);
for(int i = 0; i < maxn; i++) v[i].clear();
for(int i = 0; i < len; i++) {
int temp; cin >> temp;
v[i].push_back(temp);
}
int l = 0, r = len - 1;
for(int _ = 0; _ < k; _++) {
slove(l, r);
l += (r - l) / 2 + 1;
}
for(int i = l; i <= r; i++) {
reverse(v[i].begin(), v[i].end());
for(int j = 0; j < v[i].size(); j++) {
cout << v[i][j];
if(i == r && j == v[i].size() - 1) cout << endl;
else cout << ' ';
}
}
}
return 0;
}
1009 Paperfolding
に言及
1枚の紙に、水平に折り、縦に折り、全部でn回((2^n)の折り方があることを意味する)行い、最後に紙を十字に切り、多くのブロックに分け、ブロック数の数学的期待を求める.
構想
水平にx回折り、縦にy回折り、折りたたんだ紙を広げてみると、切り裂いた跡は原紙を縦方向に(2^x)ナイフ、水平方向に(2^y)ナイフを切ったので、全部で((2^x+1)*(2^y+1))ブロックが切り裂かれています.
だから望むのは
\[\begin{align} ans &=\frac{1}{2^n}\\sum_{i=0}^{n}\C_n^i\(2^i+1)*(2^{n-i}+1)\\&=\frac{1}{2^n}\\sum_{i=0}^{n}\C_n^i\(2^n+2^i+2^{n-i}+1)\\&= 2^n+1+2*\frac{1}{2^n}\sum_{i=0}^{n}\C_n^i 2^i\\&= 2^n+1+2*\frac{3^n}{2^n}\end{align}\]
コード#コード#
#include
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;
const int mod = 998244353;
ll T, n;
ll qpow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
ll inv2 = qpow(2, mod - 2);
cin >> T;
while(T--) {
cin >> n;
ll ans = 1 + qpow(2, n % (mod - 1)) + 2 * qpow(3 * inv2, n % (mod - 1));
ans %= mod;
cout << ans << endl;
}
return 0;
}
1012 Set1
に言及
1つの初期要素が({1,...,n})の集合は、1つの要素しか残っていないまで2つの操作を順次行います.
構想
(i)番目の要素については、左の要素の数が右の要素の数より少なくなく、右の要素の数が2番目の操作で除去されることが残りの条件です.
そこで、それぞれの数について残されたシナリオ数は(cnt[i]=C_{r}^{l}r!\frac{( r-l)!}{(2!)^{(r-l)/2}\frac{r-l}{2}})のうち、(l)は(i)の左の数の個数であり、(r)は(i)の右の数の個数である.
答えは,各シナリオ数(cnt[i])をシナリオ数を除いて加算(sum)である.
コード#コード#
#include
#define ll long long
using namespace std;
const int maxn = 5e6 + 7;
const int mod = 998244353;
int T, n;
int cnt[maxn], fac[maxn], inv[maxn], sum;
int qpow(int a, int b) {
int ans = 1;
while(b) {
if(b & 1) ans = (ll)ans * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return ans;
}
void init() {
fac[0] = inv[0] = 1;
for(int i = 1; i < maxn; i++) fac[i] = (ll)fac[i - 1] * i % mod;
inv[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
for(int i = maxn - 2; i >= 1; i--) inv[i] = (ll)inv[i + 1] * (i + 1) % mod;
}
ll C(ll n, ll m) {
return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
init();
cin >> T;
while(T--) {
sum = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
int l = i-1, r = n-i;
if(l >= r) {
int res = (ll)C(l, r) * fac[r] % mod;
int temp = qpow(2, (l-r)/2);
temp = qpow(temp, mod - 2);
res = (ll)res * fac[l-r] % mod * temp % mod;
res = (ll)res * inv[(l-r)/2] % mod;
cnt[i] = res;
sum = ((ll)sum + cnt[i]) % mod;
}
else cnt[i] = 0;
}
sum = qpow(sum, mod - 2);
for(int i = 1; i <= n; i++) {
cout << (ll)cnt[i] * sum % mod;
if(i != n) cout << ' ';
}
cout << endl;
}
return 0;
}