QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#177711#6417. Classical Summation Problempikachu_coderWA 7ms11048kbC++142.5kb2023-09-13 11:00:442023-09-13 11:00:45

Judging History

你现在查看的是最新测评结果

  • [2023-09-13 11:00:45]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:11048kb
  • [2023-09-13 11:00:44]
  • 提交

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'