ARC 113

傳送門

A. A×B×C

https://atcoder.jp/contests/arc113/tasks/arc113_a

題意

給定一個正整數K，求出正整數排列(A,B,C)，使A×B×C ≤ K，的組合個數，

思路

暴力，列舉A、B，求C的個數，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
int k;

int main(){
    IOS;
    cin >> k;
    ll res = 0;
    for(int c = 1;c <= k;c++){
        int ab = 0;
        ab = k / c;
        for(int a = 1;a <= ab;a++){
            res += ab / a;
        }
    }
    cout << res << endl;
    system("pause");
    return 0;
}

B.A ^ B ^C

https://atcoder.jp/contests/arc113/tasks/arc113_b

題意

給定三個數A,B,C,求出 a b c a^{b^c} abc的個位上的數，

思路

①由于我們只需求解個位上數，所以A的個位以上的數對結果無影響，所以我們對A取余，
②找規律，我們發現0-9中每個數的n次方的個位上的數是具有規律性的，結果如下：
③利用快速冪計算 b c b^c bc對a所在周期取余的結果
④在記錄a的n次冪的個位的陣列中輸出結果，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
int abc[10][5];

ll pm(ll b,ll c,ll mod){
    ll res = 1;
    while(c){
        if(c & 1){
            (res *= b)%= mod;
        }
        c >>= 1;
        (b*=b)%= mod;
    }
    return res;
}


int main(){
    IOS;
    int a,b,c;
    abc[2][0] = 6;abc[2][1] = 2;abc[2][2] = 4;abc[2][3] = 8;
    abc[3][0] = 1;abc[3][1] = 3;abc[3][2] = 9;abc[3][3] = 7;
    abc[4][0] = 6;abc[4][1] = 4;
    abc[7][0] = 1;abc[7][1] = 7;abc[7][2] = 9;abc[7][3] = 3;
    abc[8][0] = 6;abc[8][1] = 8;abc[8][2] = 4;abc[8][3] = 2;
    abc[9][0] = 1;abc[9][1] = 9;
    cin >> a >> b >> c;
    a = a%10;
    if(a == 0 || a == 1 || a == 5 || a == 6){
        cout << a << endl;
    }else{
        if(a == 4 || a == 9){
            ll bc = pm(b,c,2);
            cout << abc[a][bc] << endl;
        }else {
            ll bc = pm(b,c,4);
            cout << abc[a][bc] << endl;
        }
    }
    system("pause");
    return 0;
}

C. String Invasion

https://atcoder.jp/contests/arc113/tasks/arc113_c

題意

給定字串s，若 s i = s i + 1 ≠ s i + 2 s_i = s_{i+1} ≠ s_{i+2} si?=si+1??=si+2?，則將 s i + 2 s_{i+2} si+2?替換為 s i s_i si?，求最多替換的次數，

思路

①從后往前遍歷字串，記錄在兩個相同且相鄰的字符出現之前，各字符的出現次數，
②當出現兩個相同且相鄰的字符時，讓結果加上這兩個字符后面的字串的長度，再減去這兩個字符在后面的字串中的出現次數（相同的字符不用修改），
③因為后面的字串已經被改動，所以要更新記錄各字符的出現次數的陣列，
④回圈進行上述程序，直到字串全都遍歷完，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
string s;
int cnt[30];

int main(){
    IOS;
    cin >> s;
    ll res = 0;
    int len = s.length();
    for(int i = len-2;i >= 0;i--){
        if(s[i] == s[i+1]){
            int after = len -(i+2);
            res += after - cnt[s[i]-'a'];
            memset(cnt,0,sizeof(cnt));
            cnt[s[i]-'a'] = after;
        }
        cnt[s[i+1]-'a']++;
    }
    cout << res << endl;
    system("pause");
    return 0;
}

D.Sky Reflector

https://atcoder.jp/contests/arc113/tasks/arc113_d

題意

給定N,M,K， A i A_i Ai?是第 i i i行的最小值， B j B_j Bj?是第 j j j列的最大值，網格中每個數的大小不超過K，求（A,B）的所有可能性（答案對998244353取模）

思路

①對于n=1 和 m=1的情況特判，
②其他情況，假設A取 a 1 , a 2 , . . . a , n a_1,a_2,...a,_n a1?,a2?,...a,n?，則設 a m a x a_{max} amax?為這n個數中的最大值，對于B，若 b 1 , b 2 , . . . . , b m b_1,b_2,....,b_m b1?,b2?,....,bm?都 ≥ a m a x ≥a_{max} ≥amax?則滿足題意，
③通過行列的排列順序不同，生成陣列B，故對i進行列舉，可得公式
　　　　　　 ∑ i = 1 k ( i n ? ( i ? 1 ) n ) ? ( k ? i + 1 ) m \sum_{i=1}^k(i^n-(i-1)^n)*(k-i+1)^m ∑i=1k?(in?(i?1)n)?(k?i+1)m
最后再對結果進行取余，
④需要用到快速冪，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mod = 998244353;
int n,m,k;

ll po(ll a,ll n){
    ll res = 1;
    while(n){
        if(n & 1){
            res = res * a % mod; 
        }
        a = a * a %mod;
        n >>= 1;
    }
    res %= mod;
    return res;
}

int main(){
    IOS;
    cin >> n >> m >> k;
    if(n == 1){
        cout << po(k,m) << endl;
    }else if(m == 1){
        cout << po(k,n) << endl;
    }else{
        ll res = 0;
        for(int i=1;i<=k;i++)
            res=(res+(ll)(po(i,n)-po(i-1,n)+mod)%mod*po(k-i+1,m)%mod)%mod;
        cout << res << endl;
    }
    system("pause");
    return 0;
}