QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177711 | #6417. Classical Summation Problem | pikachu_coder | WA | 7ms | 11048kb | C++14 | 2.5kb | 2023-09-13 11:00:44 | 2023-09-13 11:00:45 |
Judging History
answer
/*
3 2
Ev = sum(value of outcome i/possibility of outcome i) for all i
Ev of city number i = sum((value of city i*p(i))/2^k) where p(i) is the probability of choosing city i as the median, all p(i) sum to one!
Because the probability distributions summing to 1 are symmetrical, the result is the center.
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define pii pair<int, int>
#define pil pair<int, ll>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
//ordered_set<int> st; ordered set
//gp_hash_table<int, int> table; faster hash table
const ll mod = 998244353LL;
const int maxn = 1000001;
vl facts(maxn, 1LL);
ll pow(ll a, ll b){ //a^b
if(b == 0) return 1LL;
ll half = pow(a, b/2);
if(b%2 == 0) return (half*half)%mod;
return (((half*half)%mod)*a)%mod;
}
ll dvd(ll a, ll b){
return (a*pow(b, mod-2LL))%mod;
}
ll choose(int a, int b){ //a choose b, a!/(b!*(a-b)!), const factor of ~30 so use wisely
if(b > a) return 0LL;
ll num = facts[a];
ll den = (facts[b] * facts[a-b])%mod;
return dvd(num, den);
}
ll n; ll k; //n cities, k friends
//all friends meet at the median
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
for(int a = 1; a < maxn; a++) facts[a] = (facts[a-1]*(ll)a)%mod;
cin >> n >> k;
if(k%2 == 0){ //given that there is an even number of friends, the floor between the two edge friends becomes the median -->
//subtract expected shift left distance - ((n+1)*n^k - e(d))/2
//how much does road i...i+1 contribute to the answer?
ll sm = 0LL; ll k2 = k/2LL;
for(int i = 1; i < n; i++){
//k/2 to the left, k/2 to the right, 3rd city left 4th city right
ll e = (choose(k, k2) * (ll)pow(i, k2))%mod;
e = (e * pow(n-i, k2))%mod;
sm = (sm + e)%mod;
}
ll rt = ((n+1LL)*pow(n, k))%mod;
cout << dvd((rt-sm+mod)%mod, 2LL);
}
else{ //given median at whole number position i, floor(k/2) friends meet at either end OR live at position i along with the middle friend --> all arrangements are unique to the i (a single arrangement cannot represent two different medians)
cout << (dvd(n+1LL, 2LL) * pow(n, k))%mod << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 10688kb
input:
3 2
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 6ms
memory: 10860kb
input:
5 3
output:
375
result:
ok 1 number(s): "375"
Test #3:
score: 0
Accepted
time: 2ms
memory: 10904kb
input:
2 2
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 6ms
memory: 10588kb
input:
10 9
output:
508778235
result:
ok 1 number(s): "508778235"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11048kb
input:
69 3
output:
11497815
result:
ok 1 number(s): "11497815"
Test #6:
score: 0
Accepted
time: 5ms
memory: 10968kb
input:
994 515
output:
33689623
result:
ok 1 number(s): "33689623"
Test #7:
score: -100
Wrong Answer
time: 7ms
memory: 10864kb
input:
4476 6182
output:
626338903
result:
wrong answer 1st numbers differ - expected: '114894183', found: '626338903'