题解归档 - cf2226A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2226A
• 本地来源：problems/cf2226A/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/A
• 原始标题：cf2226A - Disturbing Distribution

思路

cf2226A - Disturbing Distribution

pattern: partition into nondecreasing subsequences with positive products.

claim: values greater than 1 are never cheaper to multiply together, because xy >= x+y for x,y>=2. Thus each >1 value can be paid separately. A value 1 costs nothing if it is placed before some later >1 in that operation; all trailing ones after the last >1 need one separate operation of cost 1. If all values are 1, one operation costs 1.

check: samples [1,2,1,2,3] -> 7, [3,2,1] -> 6, all ones -> 1.

代码

来源：problems/cf2226A/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=676767677;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n,last=-1;
        cin>>n;
        ll ans=0;
        vector<int>a(n+1);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>1){
                ans+=a[i];
                last=i;
            }
        }
        if(last==-1){
            cout<<1<<"\n";
            continue;
        }
        if(last<n) ans++;
        cout<<(ans%MOD)<<"\n";
    }
    return 0;
}