学步园

5186:求各个数位上的和并%k，k为k进制。要交c++

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
typedef long long LL;

int n , Q;
int res[205];
char str[205];
void work() {
    int mx = 0;
    memset(res , 0 , sizeof(res));
    for (int i = 0 ; i < n ; ++ i) {
        scanf("%s" , str);
        int len = strlen(str);
        reverse(str , str + len);
        for (int j = 0 ; j < len ; ++ j)
            if (isdigit(str[j]))
                res[j] += str[j] - '0';
            else
                res[j] += str[j] - 'a' + 10;
        mx = max(len , mx);
    }
    for (int i = 0 ; i < mx ; ++ i)
        res[i] %= Q;        
    while (mx > 1 && res[mx - 1] == 0)
        -- mx;
    for (int i = mx - 1 ; i >= 0 ; -- i) {
        if (res[i] < 10)
            printf("%d" , res[i]);
        else
            printf("%c" , res[i] - 10 + 'a');
    }
    puts("");
}

int main() {
    while (~scanf("%d%d",&n,&Q))
        work();
    return 0;
}

5187：n个从1到n的数重新排成一个序列，允许序列出现一个峰（最高峰或最低峰）

可知，整个序列中只有最两边的位置一定是存在一个n或者是1的，否则若1和n这两个数都在序列中间的话，整个序列势必会出现两个峰而不满足条件。那么接下来我们开始讨论：1:1放在最左，然后考虑n所在的位置（假设都是从左往右），在第二位时所有可能是C( 0,n-2),第三位为C(1,n-2)...一直到最有，共有X = c(0,n-2)+c(1,n-2).....c(n-2,n-2) = 2^(n-1)-1种可能，然后把1放在最右同理，再将1换成n，再算一次，所以一共是有X × 2 × 2 = 2 ^ n - 4，但是中间算的过程中多减去两次(1...n)
(n...1)的情况，所以加回来，那么最终答案是ans = 2 ^ n - 2,。很明显用快速幂，但是n高达10^18,在裸快速幂计算过程中肯定会爆LL，因此将中间再次二进制拆分下，时间变成lgn*lgn，就能接受了

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;

ll n, x;

ll multi( ll a, ll b )
{
	ll res = 0;
	while( b )
	{
		if( b & 1 )
		{
			res += a;
			res %= x;
		}
		a += a, a %= x, b >>= 1;
	}
	return res;
}

ll power( ll a, ll b )
{
	ll res = 1;
	while( b )
	{
		if( b & 1 )
		{
			res = multi( res, a );
		}
		a = multi( a, a ), b >>= 1;
	}
	return res;
}

int main()
{
	while( cin >> n >> x )
	{
		if( n == 1 )
		{
			cout << 1 % x << endl;
			continue;
		}
		else
		{
			ll ans = power( 2, n ) - 2;
			while( ans < 0 )
				ans += x;
			cout << ans << endl;
		}
	}
	return 0;
}