题解：CF997B Roman Digits

· · 题解

这到题一眼丁真，不是靠脑子数学硬算，就是打表找规律。

前者@litble 大神已经详细讲过了（膜拜大神），我就依她的题解进一步的复述一遍（因为第 一次没有看懂，芽儿太菜了）：

题目简意就是求在{ 1,5,10,50 } 中取 n 个组成不同数的方案数，我们将每个数减一，就变成在 { 0,4,9,49 }中取 n 个，由于有0的出现，故更加便于处理。

我们可以发现 9\times4=4\times9+5\times0，故 9 个 4 和 4 个 9+5 个 0 为两种同样的情况，于是出现了重 复，那么单纯的排列组合相加是不行的（需要减一），所以如果方案数单调，取4的个数应不超过 8 个。

同理：由 1\times4+5\times9=1\times49+5\times0 ，取 4 的时候，取 9 的个数就不能超过 4 个。

由 49\times9=9\times49+44\times0 ，没有取 4 的时候，取 9 的个数就不能超过 48 个。

但是由 9\times9=2\times4+1\times49+6\times0 ，发现在取 48 个 9 之前，没有取 4 的情况已经出现重复，只不过用 4 代替了一部分 49，所以取 9 的个数不能超过 8 个。

由上可知，我们找到了用 0 和 49 代替 4 和 9 的例子，于是我们可以枚举取 4 和取 9 的个数 i 和 j，剩下的数全选 0 和 49，方案数是 n−i−j+1。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans(0);
signed main(){
    cin >> n;
    for (int i=0;i<=8 && i<=n;i++){
        if(!i){
            for (int j=0;j<=8 && j+i<=n;j++)
                ans+=n-i-j+1;
        }
        else 
            for (int j=0;j<=4 && j+i<=n;j++)
                ans+=n-i-j+1;
    }
    cout << ans;
    return 0;
}

其次是打表，打表代码如下（其实就是简单的循环，但是包超时的）

void solve(int x){
    bool vis[N];
    int ans(0);
    for (int i=0;i<=x;i++){
        for (int j=0;i+j<=x;j++){
            for (int k=0;i+j+k<=x;k++){
                int l = x-i-j-k;
                int p = i+5*j+10*k+50*l;
                if (!vis[p]) {
                    vis[p] = 1;
                    ans++;
                }
            }
        }
    }
    cout << ans << '\n';
}

这是前 100 个数据：

4 10 20 35 56 83 116 155 198 244 292 341 390 439 488 537 586 635 684 733 782 831 880 929 978 1027 1076 1125 1174 1223 1272 1321 1370 1419 1468 1517 1566 1615 1664 1713 1762 1811 1860 1909 1958 2007 2056 2105 2154 2203 2252 2301 2350 2399 2448 2497 2546 2595 2644 2693 2742 2791 2840 2889 2938 2987 3036 3085 3134 3183 3232 3281 3330 3379 3428 3477 3526 3575 3624 3673 3722 3771 3820 3869 3918 3967 4016 4065 4114 4163 4212 4261 4310 4359 4408 4457 4506 4555 4604 4653

发现在第 12 个数据以后，每个数是前一个数加上 49（根据前面数学推导不难发现，第 12 个数据其实就是 4 取 8 个， 9 取 4 个的情况，所以后面的规律也不难理解）

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int db[20]={0,4,6,10,15,21,27,33,39,43,46,48,49};
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=12;++i) db[i]=db[i-1]+db[i];
    if(n<=12) printf("%d",db[n]);
    else printf("%lld",1ll*db[12]+1ll*(n-12)*49);
    return 0;
}