Atcoder grand 025 组合数学塔涂色贪心走路博弈

略

题意:给你N个数(3e5) 每个数可以是0,a,b,a+b(3e5) 但是总数加起来要是定值K(18e10)

问总方法数mod 998244353

解:

把a+b的看成是一个a加上一个b的这样从0-N枚举a的个数判断b的个数是否合法

如果合法的话这种情况的所有方法数就相当于在N个中选i个放a 然后再在N个中选剩下的b个放b

anser = (anser + (ncr(n, i) * ncr(n, remain / B) % mod)) % mod

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = , gakki =  +  +  +  + 1e9;

const int MAXN = 2e5 + , MAXM = 2e5 + , N = 3e5 + ;

int to[MAXM << ], nxt[MAXM << ], Head[MAXN], tot = ;

inline void addedge(int u, int v)

{

        to[++tot] = v;

        nxt[tot] = Head[u];

        Head[u] = tot;

}

ll Qpow(ll a, ll b)

{

        ll ans = , base = a;

        while (b != )

        {

                if (b &  != )

                {

                        ans = (ans * base) % mod;

                }

                base = (base * base) % mod;

                b >>= 1LL;

        }

        return ans % mod;

}

ll Inv(ll a)

{

        return Qpow(a, mod - );

}

ll fact[N], Invfact[N], anser = ;

ll ncr(ll n, ll r)

{

        if (r <  || n < )

        {

                return ;

        }

        if (n < r)

        {

                return ;

        }

        ll a = fact[n];

        a = (a * Invfact[r]) % mod;

        a = (a * Invfact[n - r]) % mod;

        return a;

}

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        ll n, A, B, K;

        cin >> n >> A >> B >> K;

        Invfact[] = Invfact[] = fact[] = fact[] = ;

        for (ll i = ; i <= 3e5 + ; i++)

        {

                fact[i] = (fact[i - ] * i) % mod;

                Invfact[i] = Inv(fact[i]);

        }

        ll remain;

        for (ll i = ; i <= n; i++)

        {

                remain = K - i * A;

                if (remain >=  && remain % B ==  && remain / B <= n)

                {

                        anser = (anser + (ncr(n, i) * ncr(n, remain / B) % mod)) % mod;

                }

        }

        cout << anser << endl;

        return ;

}

题意:给你一个数轴和N个线段有两个人A,B A每次给B一个线段要求B要走到线段的范围内 B初始在原点

A会选最优方案使得B走的距离最远而B会选最优方案使得自己走的距离最少问你最后B走的距离是多少

解:

A选的方案肯定是使得B在原点左右来回跑这样使得跑的距离最大

这样我们把L从大到小排列把R从小到大排列如果有L>R 就说明B需要走这么长的距离来满足条件

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = , gakki =  +  +  +  + 1e9;

const int MAXN = 2e5 + , MAXM = 2e5 + , N = 1e5 + ;

int to[MAXM << ], nxt[MAXM << ], Head[MAXN], tot = ;

inline void addedge(int u, int v)

{

        to[++tot] = v;

        nxt[tot] = Head[u];

        Head[u] = tot;

}

vector<int> l, r;

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n;

        cin >> n;

        l.push_back(), r.push_back();

        for (int i = ; i <= n; i++)

        {

                int L, R;

                cin >> L >> R;

                l.push_back(L);

                r.push_back(R);

        }

        ll anser = ;

        sort(l.rbegin(), l.rend());

        sort(r.begin(), r.end());

        for (int i = ; i <= n; i++)

        {

                if (l[i] > r[i])

                {

                        anser += 2LL * (l[i] - r[i]);

                }

        }

        cout << anser << endl;

        return ;

}

巴特西

Atcoder grand 025 组合数学塔涂色贪心走路博弈

最新文章

热门文章

巴特西

Atcoder grand 025 组合数学塔涂色 贪心走路博弈

最新文章

热门文章

Atcoder grand 025 组合数学塔涂色贪心走路博弈