2022icpc网络赛 A题B题

A Yet Another Remainder

费马小定理

\(10^{p-1} \% p==1\)

考虑第\(p-1\)行

字符串为\(a_1a_2a_3a_4a_5a_6\)

假设当前模数p为3

那考虑第2行

然后第一个数是 \(a_1+a_3+a_5\) 第二个数是 \(a_2+a_4+a_6\)

假设一个数 等于x (这个数是为所求的那个大数的一部分)

x=\(a_1*10^5+a_3*10^3+a_5*10\)

\(x\%p=a_1*10+a3*10+a_5*10\)

\(x\%p=10*(a_1+a_3+a_5)\)

恰好是p-1行的第一个数

然后就可以推出后面的数了。

#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
using namespace std;
const int N=1e5+5;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m;
int b[200][200];
int a[N];
ll qpow(ll a,ll b,ll p){
    ll res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
void solve(){
    int n;cin>>n;
    for(int i=1;i<=min(100,n);i++){
        for(int j=1;j<=i;j++){
            cin>>b[i][j];
        }
    }
    if(n<=100){
        for(int i=1;i<=n;i++){
            a[i]=b[n][i];
        }
        int q;cin>>q;
        while(q--){
            int p;cin>>p;
            ll x=0;
            for(int i=1;i<=n;i++){
                x=(x*10+a[i])%p;
            }
            cout<<x<<endl;
        }
    }
    else {
        int q;cin>>q;
        while(q--){
            int p;cin>>p;
            ll ans=0;

            for(int i=1;i<p;i++){
                ans=(ans+qpow(10,n-i,p)*b[p-1][i]%p)%p;
            }
            cout<<ans<<endl;
        }
    }
    
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){solve();}
}

B Non-decreasing Array

$dp[i][j] $ 表示前i个删完后只剩j个数的最大值

#include<bits/stdc++.h>
#define ll long long 
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e5+5;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m;
int b[200][200];
int a[N];
ll dp[200][200];
// dp[i][j]  前i个删完只剩j个的最大值
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,-inf,sizeof(dp));

    dp[1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int k=1;k<i;k++){
                if(dp[k][j-1]>=0)
                dp[i][j]=max(dp[i][j],dp[k][j-1]+(a[i]-a[k])*(a[i]-a[k]));
            }
        }
    }
        ll ans=0;

    for(int i=1;i<=n;i++){
        ans=max(ans,dp[n][max(0ll,n-i*2+1)]);
        ans=max(ans,dp[n][max(0ll,n-i*2)]);
        cout<<ans<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}