题解：P1001 A+B Problem

· · 题解

题目

给定两个整数 a,b，求 a 与 b 的和。

思路

本题有多种解法，充分发挥一题多解的思维可以更好地提升 OI 能力。

思路 1

我们首先定义两个变量 a,b：int a,b;。在 C++ 中，int 为整形变量，可存放 -2^{31} \sim 2^{31}-1 之间的整数。

接着使用 cin>>a>>b; 语句读入 a 与 b 的值。输入数据中 a,b 之间用一个空格隔开，所以 cin 就会将第一个数赋值给 a，第二个数赋值给 b。

然后使用 cout<<a+b; 语句输出 a 与 b 的和。cout 的功能是输出变量、字符串、常数等值。如果你想在输出后加上一个换行，那么可以使用 endl，比如 cout<<a<<endl<<b;，这句话的意思就是将 a,b 分别在两行中输出。

注意，cin 和 cout 功能都在 iostream 头文件中，如果想使用就必须将头文件导入。使用 #include<iostream> 语句即可将 iostream 导入。在更深入学习信息学编程之后将会用到更多的功能（比如 queue 等），如果想使用就必须将每个功能的头文件分别导入。如果不想记忆的话，可以使用 #include<bits/stdc++.h> 将所有头文件导入。同时，cin 和 cout 等也必须使用 using namespace std; 将命名空间引入。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}

思路 2

看到题目中的 a,b 并求它们的和，可以联想到区间求和问题，用树状数组维护一个长度为 2 的序列 c，首先对 c_1 增加 a，然后对 c_2 增加 b，接着使用 query 函数将 c_1 \sim c_2 的和求出即为答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=5;
int a[N],c[N],n,Q;
inline int lowbit(int x)
{
    return x&-x;
}
inline void modify(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;
}
inline int query(int x)
{
    int s=0;
    for(int i=x;i;i-=lowbit(i)) s+=c[i];
    return s;
}
int main()
{
    n=2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        modify(i,a[i]);
    }
    cout<<query(2);
    return 0;
}

思路 3

考虑使用最短路算法。首先考虑一个三个结点三个边的有向图，如下所示（其中 1 到 3 的边权为一个很大的数，比 a+b 的值大）：

最短路径就是 1 \to 2 \to 3，所以求 a+b 的值就等同于求 1 到 3 的最短路径。因为只有三个结点，所以考虑 Floyd 算法。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll inf=1.2e18;
constexpr ll N=7;
ll g[N][N];
int main()
{
    memset(g,0x3f,sizeof g);
    int n=3;
    cin>>g[1][2];
    cin>>g[2][3];
    g[1][3]=inf;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    cout<<g[1][3];
    return 0;
}

思路 4

二项式定理：对于任意自然数 n 以及实数 a,b，均有：

(a + b)^n = \sum_{k=0}^n C_n^k \cdot a^{n-k} b^k

题目可转化为求 (a+b) \bmod p 的值，其中 p=1218000211019 为质数。所以我们可以考虑使用二项式定理求解该题目。

其中 C_n^k 为组合数，计算公式如下（x ^{\prime} 表示 x 在模 p 意义下的逆元，根据费马小定理可以计算出 x ^{\prime}=x^{p-2}）：

\begin{aligned} C_n^k \bmod p &= \dfrac{n!}{k!(n-k)!} \bmod p \\ &= n! \cdot k!^{\prime} \cdot (n-k)!^{\prime} \bmod p \end{aligned}

首先初始化一下阶乘和阶乘的逆元（f[i] 表示 i 的阶乘，invf[i] 表示 i! 的逆元，ksm(a,b) 的功能是计算 a^b \bmod p 的值）：

f[0]=invf[0]=1;
for(int i=1;i<10;i++) f[i]=f[i-1]*i%mod;
for(int i=1;i<10;i++) invf[i]=invf[i-1]*ksm(i,mod-2)%mod;

然后套二项式定理公式：

ll ans=0;
for(int k=0;k<=1;k++) ans=(ans+C(n,k)*ksm(a,n-k)*ksm(b,k))%mod;

最后输出 ans 即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=10;
constexpr ll mod=1218000211019;
ll a,b,f[N],invf[N];
inline ll ksm(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1) s=s*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return s;
}
inline ll C(ll a,ll b)
{
    if(a<b) return 0;
    return f[a]*invf[b]%mod*invf[a-b]%mod;
}
int main()
{
    cin>>a>>b;
    int n=1;
    f[0]=invf[0]=1;
    for(int i=1;i<10;i++) f[i]=f[i-1]*i%mod;
    for(int i=1;i<10;i++) invf[i]=invf[i-1]*ksm(i,mod-2)%mod;
    ll ans=0;
    for(int k=0;k<=1;k++) ans=(ans+C(n,k)*ksm(a,n-k)*ksm(b,k))%mod;
    cout<<ans;
    return 0;
}