ARC117B（思维，乘法原理）

题意描述

有\(n\)个数字，每次可以选择一个\(x\)，使得大于等于\(x\)的数减\(1\)，求不同序列的个数

思路

选择\(x\)的顺序对序列不会产生不同的影响，因此我们可以将序列排序。
如果两个数相同，则可以将他们看成一个数，因此我们可以将数组去重。
发现每个数字能够变化的范围为\([a_{i-1},a_{i}]\)，而变成\(a_{i-1}\)后，就可以视为一个数来看待，因此我们只需要分别计算每一位的贡献，将所有贡献乘起来即可。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
#include "sstream"
#include "cstdio"
#include "unordered_set"
#include "iomanip"

using namespace std;

#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define rep(x,l,u) for(int x=l;x=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1)
#define endl '\n'
#define dbg(x) cerr << #x " = " << (x) << endl
#define mp make_pair
#define dbgfull(x) cerr << #x << " = " << x << " (line " << __LINE__ << ")"< PII;
typedef pair PCC;
typedef pair PDD;
typedef pair PLL;
typedef pair PIII;
typedef pair PLB;

struct Scanner {

    bool hasNext = 1;
    bool hasRead = 1;

    int nextInt() {
        hasRead = 0;
        int res = 0;
        char flag = 1, ch = getchar();
        while (ch != EOF && !isdigit(ch)) {
            hasRead = 1;
            flag = (ch == '-') ? -flag : flag;
            ch = getchar();
        }
        while (ch != EOF && isdigit(ch)) {
            hasRead = 1;
            res = res * 10 + (ch - '0');
            ch = getchar();
        }
        if (ch == EOF)
            hasNext = 0;
        return res * flag;
    }

    ll nextLL() {
        hasRead = 0;
        ll res = 0;
        char flag = 1, ch = getchar();
        while (ch != EOF && !isdigit(ch)) {
            hasRead = 1;
            flag = (ch == '-') ? -flag : flag;
            ch = getchar();
        }
        while (ch != EOF && isdigit(ch)) {
            hasRead = 1;
            res = res * 10 + (ch - '0');
            ch = getchar();
        }
        if (ch == EOF)
            hasNext = 0;
        return res * flag;
    }

    char nextChar() {
        hasRead = 0;
        char ch = getchar();
        while (ch != EOF && isspace(ch)) {
            hasRead = 1;
            ch = getchar();
        }
        if (ch == EOF)
            hasNext = 0;
        return ch;
    }

    int nextString(char *str) {
        hasRead = 0;
        int len = 0;
        char ch = getchar();
        while (ch != EOF && isspace(ch)) {
            hasRead = 1;
            ch = getchar();
        }
        while (ch != EOF && !isspace(ch)) {
            hasRead = 1;
            str[++len] = ch;
            ch = getchar();
        }
        str[len + 1] = 0;
        if (ch == EOF)
            hasNext = 0;
        return len;
    }

} sc;

void rd(int &x) {
    x = sc.nextInt();
}

void rd(ll &x) {
    x = sc.nextLL();
}

void rd(char &x) {
    x = sc.nextChar();
}

void rd(char *x) {
    sc.nextString(x);
}

template
void rd(pair &x) {
    rd(x.first);
    rd(x.second);
}

template
void rd(T *x, int n) {
    for (int i = 1; i <= n; ++i)
        rd(x[i]);
}


struct Printer {

    void printInt(int x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x >= 10)
            printInt(x / 10);
        putchar('0' + x % 10);
    }

    void printLL(ll x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x >= 10)
            printLL(x / 10);
        putchar('0' + x % 10);
    }

} printer;

void pr(int x, char ch = '\n') {
    printer.printInt(x);
    putchar(ch);
}

void pr(ll x, char ch = '\n') {
    printer.printLL(x);
    putchar(ch);
}

template
void pr(pair x, char ch = '\n') {
#ifdef LOCAL
    putchar('<');
    pr(x.first, ' ');
    pr(x.second, '>');
    putchar(ch);
    return;
#endif // LOCAL
    pr(x.first, ' ');
    pr(x.second, ch);
}

template
void pr(T *x, int n) {
    for (int i = 1; i <= n; ++i)
        pr(x[i], " \n"[i == n]);
}

template
void pr(vector &x) {
    int n = x.size();
    for (int i = 1; i <= n; ++i)
        pr(x[i - 1], " \n"[i == n]);
}



const int N=1e5+5;
const int M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-4;
const double pi=acos(-1);

int n,a[N],b[N];

struct Solver {

    void InitOnce() {

    }

    void Read() {
        rd(n);
        rd(a,n);
    }


    void Solve() {
        sort(a+1,a+1+n);
        int len=unique(a+1,a+1+n)-a-1;
        rep(i,1,len+1) b[i]=a[i]-a[i-1]+1;
        ll ans=1;
        rep(i,1,len+1) ans=(ans*b[i])%mod;
        pr(ans);
    }

} solver;
int main() {
#ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    solver.InitOnce();
    while (1) {
        solver.Read();
        if (!sc.hasRead)
            break;
        solver.Solve();
        if (!sc.hasNext)
            break;
    }
    return 0;
}