欢乐赛#69 T6 题解

整个欢乐赛#69 就这一题有点难度。

想要证明的话需要一些数论知识。

求证：$(a\bmod m+b\bmod m)\bmod m=(a+b)\bmod m$（$a,b,m$ 为整数）。
令 $a=k_1m+a\bmod m,b=k_2m+b\bmod m$（$k_1,k_2$ 为整数），
则 $(a+b)\bmod m=(k_1m+a\bmod m+k_2m+b\bmod m)\bmod m=(a\bmod m+b\bmod m)\bmod m$。
注意此处 $m\mid(k_1m,k_2m)$。

求证：$(a\bmod m)\times(b\bmod m)\bmod m=a\times b\bmod m$（$a,b,m$ 为整数）。
令 $a=k_1m+a\bmod m,b=k_2m+b\bmod m$（$k_1,k_2$ 为整数），
则 $a\times b\bmod m=(k_1m+a\bmod m)\times(k_2m+b\bmod m)\bmod m=[k_1m\times k_2m+k_1m\times(b\bmod m)+(a\bmod m)\times k_2m+(a\bmod m)\times(b\bmod m)]\bmod m=(a\bmod m)\times(b\bmod m)\bmod m$。
注意此处 $m\mid[k_1m\times k_2m,k_1m\times(b\bmod m),(a\bmod m)\times k_2m]$。

根据以上的两个证明，可知边做边取模并不影响计算的结果，所以就有了 40 pts 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,x,y,z;
signed main(){
	cin>>n>>x;
    while (n--){
        cin>>y>>z;
        x=max(x+y,x*z);
        x%=mod;
    }
    cout<<x;
	return 0;
}

注意到上面加粗的文字，这种做法并不会影响到计算的结果，但会影响到你的选择。

口胡 hack：
上一轮 $x$ 变为 $10^9+7$，取模后为 $0$。
此时 $y_i=1,z_i=2$，你的代码会选择 $x+y_i$ 操作，使其变为 $1$。
但实际上 $x+y_i$ 操作会使 $x$ 变为 $10^9+8$，而 $x\times z_i$ 操作会使 $x$ 变为 $2\times10^9+14$，应选择后者。

但这并不意味着你不能边做边取模。

注意到 $y_i,z_i$ 远小于模数，那么当至少完成一次取模时，若 $z_i\ge2$，那么一定选择 $x\times z_i$ 操作，否则一定选择 $x+y_i$ 操作。

好的，100 pts 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,x,y,z;
bool f;
signed main(){
	cin>>n>>x;
    while (n--){
        cin>>y>>z;
        if (f){
            if (z>1){
                x*=z;
            }
            else {
                x+=y;
            }
            x%=mod;
            continue;
        }
        x=max(x+y,x*z);
        if (x>mod){
            f=1;
        }
        x%=mod;
    }
    cout<<x;
	return 0;
}

---

以上全文共 1781 字符，肝了 40+ min，创作不易，点个赞扒。