备孕百度之星-9月20日

签到题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
const ll mod = 998244353;
struct FastIO//输入挂
{
    static const int S=200;
    int wpos;
    char wbuf[S];
    FastIO():wpos(0){}
    inline int xchar()
    {
        static char buf[S];
        static int len=0,pos=0;
        if(pos==len) pos=0,len=fread(buf,1,S,stdin);
        if(pos==len) exit(0);
        return buf[pos++];
    }
    inline int read()
    {
        int s=1,c=xchar(),x=0;
        while(c<=32) c=xchar();
        if(c=='-') s=-1,c=xchar();
        for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';
        return x*s;
    }
    ~FastIO()
    {
        if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;
    }
}io;


inline ll read(){
    ll x=0;char ch;bool f=true;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
ll qp(ll a){
	ll x = 2;
	ll res = 1;
	while(a != 0){
		if(a % 2 == 1) res = (res * x) % mod;
		x = (x * x) % mod;
		a /= 2;
	}
	return res;
}
int main(){
	int T;
	T = read();
	while(T-- > 0){
		int a1, b1, k;
		a1 = read();
		b1 = read();
		k = read();
		ll m = k / 2;
		ll q = qp(m);
		ll a = a1 * q % mod;
		ll b = b1 * q % mod;
		if(k % 2 == 1){
			ll n_a = (a + b) % mod;
			b = (a - b) % mod; 	
			a = n_a; 
			if(b1 > 0) {
				b = (b + mod) % mod;
			}else{
				b = (b - mod) % mod; 
			}
		}
		cout << a << " " << b << endl;
	} 
}

Hamilton路径（acwing 93）

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
int dis[25][25];

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> dis[i][j];
	int dp[1<<n][n];
	for(int i = 0; i < (1<<n); i++)
		memset(dp[i], 0x3f, sizeof(dp[i]));
	dp[1][0] = 0;
	for(int i = 1; i < (1 << n); i++){
		for(int j = 0; j < n; j++){
			if(i >> j & 1)
				for(int k = 0; k < n; k++){//i ^ 1 << j防止从一个点跳到自己 
					if((i ^ 1 << j) >> k & 1) dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + dis[k][j]);//k是中间点 
				}
		}
	}
	cout << dp[(1<<n) - 1][n-1];
}
 

汉诺塔（acwing96）

#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
 
using namespace std;

int n;
int order[21];
bool ch[21];

void calc(int k)
{
	if(k == n + 1){
		for(int i = 1; i <= n; i++) cout << order[i] << " ";
		cout << endl;
		return ;
	}
	for(int i = 1; i <= n; i++){
		if(ch[i]) continue;
		ch[i] = true;
		order[k] = i;
		calc(k+1);
		ch[i] = false;
	}
}
int solve(){
	int d[n+1];
	memset(d, 0x3f, sizeof(d));
	d[1] = 1;
	for(int i = 2; i <= n; i++) d[i] = 2 * d[i-1] + 1;
	int f[n+1];
	memset(f, 0x3f, sizeof(f));
	f[1] = 1;
	for(int i = 2; i <= n; i++){
		for(int j = 1; j < i; j++){
			f[i] = min(f[i], 2 * f[j] + d[i-j]);
		}
	} 
	for(int i = 1; i <= 12; i++)
	cout << f[i] << endl;
}
int main()
{	
	n = 13;
	solve();
	
}

分形之城（awcing98）

这种题一定要静下心思考，多写多画

#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
 
using namespace std;

typedef long long ll;

pair<ll, ll> calc(ll n, ll m){
	if(n == 0) return make_pair(0, 0);
	ll cnt = 1LL << (2*n - 2);//子城房子个数
	ll len = 1LL << (n-1);
	pair<ll, ll> pos = calc(n-1, m % cnt);
	ll z = m / cnt;
	ll x = pos.first, y = pos.second;
	if(z == 0) return make_pair(y, x);
	if(z == 1) return make_pair(x, y + len);
	if(z == 2) return make_pair(x + len, y + len);
	if(z == 3) return make_pair( 2 * len - 1 - y, len - 1 - x); 
}

int main()
{	
	int T;
	cin >> T;
	ll n, a, b;
	while(T-- > 0){
		cin >> n >> a >> b;
		pair<ll, ll> x = calc(n, a-1);
		pair<ll, ll> y = calc(n, b-1);
		double z = sqrt( (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second) ) * 10;
		printf("%0.lf\n", z);//lf不保留小数，1f保留一位 
	}
}

欧拉降幂（力扣372）

快速幂

class Solution {
public:
    int mod = 1337;
    int pow(int a, int b){
        int res = 1;
        while(b != 0){
            if(b % 2 == 1) res = (res * a) % mod;
            a = a * a % mod;
            b /= 2;
        }
        return res;
    }
    int superPow(int a, vector<int>& b) {
        a %= mod;
        int res = 1;
        for(int i = 0; i < b.size(); i++){
            res = pow(res, 10) % mod;
            res = res * pow(a, b[i]) % mod;
        }
        return res;
    }
};

欧拉降幂

class Solution {
public:
    //欧拉函数
    int Phi(int n){
        int result = n;
        for( int i = 2; i * i <= n; ++i )
            if( n % i == 0 ){
                do	n /= i;
                while( n % i == 0 );
                result -= result / i;
            }
        if( n > 1 ) result -= result / n;
        return result;
    }
    int MOD = 1337;
    int M_PHI = Phi(MOD);
    //a ^ b降幂
    int superPow(int a, vector<int>& b) {
        a %= MOD;
		int bphi{};
		for( auto i : b )
			bphi = ( bphi * 10 + i ) % M_PHI;
		if( std::gcd( a, MOD ) != 1 && ge( b, M_PHI ) )
			bphi += M_PHI;
		return qp( a, bphi );
    }
    
    // 判断数组形式的十进制数（个位在最后）是否大于等于给定的值
	bool ge( const vector< int > &v, int val )	const noexcept
	{
		int dec{}, p10 = 1;
		for( int i = v.size() - 1; i >= 0; --i, p10 *= 10 )
			if( dec += v[ i ] * p10; dec >= val )
				return true;
		return false;
	}
    //快速幂
	int qp( int base, int exp )	{
		base %= MOD;
		int ans = 1;
		while( exp ){
			if(exp & 1)ans = ans * base % MOD;
			base = base * base % MOD;
			exp >>= 1;
		}
		return ans;
	}
};

快速幂求逆元

d 的逆元相当于 pow(d,mod-2) 。咱就是说，不知其然，也不知其所以然

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


LL qmi(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}