Codeforces 1228 #Codeforces

1228C.py

mod = int(1e9 + 7)
maxn = int(1e5 + 100)
primes = []
is_prime = [True] * maxn
def init():
    is_prime[0] = is_prime[1] = False
    for i in range(2, maxn):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if p * i >= maxn:
                break
            is_prime[i * p] = False
            if i % p == 0:
                break

def qpow(base, t):
    ret = 1
    while t > 0:
        if t & 1:
            ret = ret * base % mod
        base = base * base % mod
        t >>= 1
    return ret

def solve():
    x, n = map(int, input().split())
    p = []
    for prime in primes:
        if x <= 1:
            break
        if x % prime == 0:
            p.append(prime)
            while x % prime == 0:
                x = x // prime
    if x > 1:
        p.append(x)
    
    ans = 1
    for prime in p:
        index = 0
        k = prime
        while k <= n:
            index += n // k
            k = k * prime
        ans = ans * qpow(prime, index) % mod
            
    print(ans)

if __name__ == "__main__":
    init()
    solve()

# 20190929 1605
# 363165664

1228D.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll inf=0x3f3f3f3f3f3f3f3f;

const int maxn = 1e5 + 100;

set<int> G[maxn];
int color[maxn];

void solve(){
    int n, m, u, v, dfn = 1;
    memset(color, -1, sizeof color);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        G[u].insert(v);
        G[v].insert(u);
    }

    for(int i=0; i<3; i++){
        int point;
        for(point=1; point<=n; point++) if(color[point] == -1) break;
        if(point == n + 1){
            cout << -1 << endl;
            return;
        }

        for(int j=point; j<=n; j++){
            if(G[point].find(j) == G[point].end()) color[j] = i;
        }
    }

    vector<int> partial[3];
    for(int i=1; i<=n; i++){
        if(color[i] == -1){
            cout << -1 << endl;
            return;
        }
        partial[color[i]].push_back(i);
    }

    int edge_cnt = 0;
    for(int i=0; i<3; i++) for(int j=i+1; j<3; j++){
            for(int u:partial[i]) for(int v:partial[j]){
                    if(G[u].count(v) <= 0){
                        cout << -1 << endl;
                        return;
                    }
                    edge_cnt ++;
                }
        }
    
    if(edge_cnt != m){
        cout << -1 << endl;
        return;
    } 
    for(int i=1; i<=n; i++) cout << color[i] + 1 << ' ';
    cout << endl;
}

signed main(){
    Android;
    solve();
}

1228E.py

def main():
    n, k = map(int, input().split())

    MOD = 10**9 + 7
    Comb = [None] * (n + 1)
    dp = [[None] * (n + 1) for i in range(n+1)]

    for i in range(1, n + 1):
        Comb[i] = [1] + [(Comb[i-1][j-1] + Comb[i-1][j]) % MOD for j in range(1, i)] + [1]

    def powgen(base):
        cur = 1
        while True:
            yield cur
            cur = cur * base % MOD

    gen, gen_1 = powgen(k), powgen(k - 1)
    kpower = [next(gen) for i in range(n + 1)]
    k1power = [next(gen_1) for i in range(n + 1)]

    dp[1][0] = (kpower[n] - k1power[n] + MOD) % MOD
    for i in range(1, n+1): dp[1][i] = kpower[n-i]

    for r in range(2, n + 1): # row remaining
        for c in range(n+1): # c means col incompleted
            dp[r][c] = (dp[r-1][c] * k1power[c] * (kpower[n-c]-k1power[n-c]) + \
                kpower[n-c] * sum([dp[r-1][c-i] * Comb[c][i] * k1power[c-i] for i in range(1, c+1)])) % MOD
            
    # input 250 1000000000
    return dp[n][n]

print(main())