牛客IOI周赛17-普及组

A.夹娃娃

#include <iostream>
#include<bits/stdc++.h>
#include<algorithm>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e5 + 7;
const ll maxn =1e5+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a; b >>= 1; a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll w[maxn],sum[maxn];
int main(){
    int n,k,l,r;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
        sum[i]+=sum[i-1]+w[i];
    }
    for(int i=1;i<=k;i++){
        scanf("%d%d",&l,&r);
        printf("%lld\n",sum[r]-sum[l-1]);
    }
}

B.莫得难题

解题思路：
1.从1 2 3 5 9 五个数字里面任意选出几个数字进行组合。
2.显然我们可以看出，一个数字得情况有1 2 3 5 9，共5^1个。
两个数字得情况有11 12 13 15 19 21 22...99.共5^2个。
三个数字的情况有5^3个，四个数字的情况有5^4个，五个数字情况有5^5个。
3.这里我们可以看成是一个五进制表示法，不过五进制里面的0 1 2 3 4换成了1 2 3 5 9。
所以我们可以用一个mp[]数组来保存以替代 0 1 2 3 4.
4.剩下的就简单了，题目要求所有的组合里面第C(n,m)个数，这个代公式就行，注意范围取mod。

0 1 2 3 4
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34
40 41 42 43 44
100 101 102 103 104
..

替换成

1 2 3 5 9
11 12 13 15 19
21 22 23 25 29
31 32 33 35 39
51 52 53 55 59
91 92 93 95 99
111 112 113 115 119
...

剩下的就按照普通的五进制算就行了,代码如下

#include <iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<cstdio>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll mod = 1e9+7;
const ll maxn =1e5+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a; b >>= 1; a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
char mp[5]={'1','2','3','5','9'};

int main(){
    ll fac[105];
    int t,n,m;
    scanf("%d",&t);
    fac[0]=1;
    for(int i=1;i<105;i++) fac[i]=fac[i-1]*i%mod;
    while(t--){
        cin>>n>>m;
        ll a = fac[n]*qpow(fac[m]*fac[n-m]%mod,mod-2,mod)%mod;
        string ans="";
        while(a>0){
            a--;
            ans+=mp[a%5];
            a/=5;
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<endl;
    }
}