Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#define base 790972
using namespace std;

int n,k,f[51],g[51],wrong;
vector < pair<int,int> > a;

int main()
{
    int x,y;
    cin >> n >> k;
    for (int i=0;i<n;i++) scanf("%d%d",&x,&y), a.push_back(make_pair(y,x));
    sort(a.begin(),a.end());
    f[0]=1;
    for (int i=0;i<n;i++)
        for (int j=k;j;j--)
            f[j]=int((1LL*f[j-1]*a[i].second+f[j])%base);
    for (int i=0;i<n;)
    {
        int j=i;
        memset(g,0,sizeof(g));
        g[0]=1;
        while (j<n && a[j].first==a[i].first)
        {
            for (int p=k;p;p--)
                g[p]=int((1LL*g[p-1]*a[j].second+g[p])%base);
            j++;
        } 
        wrong+=g[k];
        if (wrong>=base) wrong-=base;
        i=j;
    }
    cout << (f[k]<wrong?wrong-f[k]:f[k]-wrong) << endl;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 100005;
const int K = 55;
const int MOD = 790972;
using namespace std;
int n, k;
int F[N][K], C[N][K];
ii a[N];

int cut(int l, int r) {
    C[l - 1][0] = 1;
    for(int j = 1; j <= k; j++) C[l - 1][j] = 0;
    for(int i = l; i <= r; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i - l + 1 && j <= k; j++)
            C[i][j] = (C[i - 1][j] + a[i].Y * C[i - 1][j - 1]) % MOD;
    }
    return C[r][k];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) 
        cin >> a[i].Y >> a[i].X;
    sort(a + 1, a + 1 + n);
    F[0][0] = 1; a[0].X = a[n + 1].X = -1;
    int res = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
        F[i][0] = 1;
        for(int j = 1; j <= i && j <= k; j++)
            F[i][j] = (F[i - 1][j] + a[i].Y * F[i - 1][j - 1]) % MOD;
        if (a[i].X == a[i - 1].X) cnt++; else cnt = 1;
        if (cnt >= k && a[i].X != a[i + 1].X) 
            res = (res + MOD - cut(i - cnt + 1, i)) % MOD;
    }
    res = (res + F[n][k]) % MOD;
    cout << res;
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MOD = 790972;

pair<int,int> a[100111];
int f[55][100111], n, k;

int solve(int l, int r) {
    FOR(i,l-1,r) f[0][i] = 1;
    FOR(t,1,k) {
        FOR(i,l,r)
            f[t][i] = (f[t][i-1] + f[t-1][i-1] * (ll) a[i].S) % MOD;
    }

    int res = f[k][r];
    FOR(t,0,k) FOR(i,l-1,r) f[t][i] = 0;
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    FOR(i,1,n) scanf("%d%d", &a[i].S, &a[i].F);
    sort(a+1, a+n+1);

    int res = solve(1,n);
    int i = 1, j = 1;
    while (i <= n) {
        while (j < n && a[j+1].F == a[i].F) ++j;
        if (j - i + 1 >= k) res = (res - solve(i,j) + MOD) % MOD;
        i = j + 1;
    }
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 790972
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

ll tinh(vector<int> A, int k){
    int n = SZ(A);
    ll f[n + 1], g[n + 1];
    MS(f, 0);
    rep(i, n) f[i + 1] = f[i] + A[i];
    FOR(j, 2, k){
        FOR(i, 1, n) g[i] = f[i]; g[0] = 0;
        FOR(i, 1, n) f[i] = (A[i - 1] * g[i - 1] + f[i - 1]) % mod;
    }
    return f[n]; 
}

int n, k;
vector<int> A;
pair<int, int> V[100005];

int main(){
    //OPEN();
    scanf("%d %d", &n, &k);
    rep(i, n){
        scanf("%d %d", &V[i].se, &V[i].fi);
        A.PB(V[i].se);
    }

    ll res = tinh(A, k);
    sort(V, V + n);

    A.clear();
    A.PB(V[0].se);
    FOR(i, 1, n - 1){
        if(V[i].fi == V[i - 1].fi) A.PB(V[i].se);
        else{
            res -= tinh(A, k);
            A.clear();
            A.PB(V[i].se);        
        }
    }
    res -= tinh(A, k);

    printf("%lld\n", ((res % mod) + mod) % mod);

}