出题人题解 | #小y的盒子#

原题解链接：https://ac.nowcoder.com/discuss/181037

此题为送温暖题目。。

把所有的数字转换为三进制，对于每个卡片都是形如$00000100000000010000$的形式

所以$SS$为$222222222222$的形式，共有$nn$位

然后考虑当第$ii$位上为$11$的时候，表示这一位上需要选$11$个$3^{i}3^i$ 的卡片，同样，为$22$时需要$22$个，为$00$时只需一个。

当需要$11$个时，有两种选择，其他的都只有一种选择。

又因为$SS$的形式是$222222222222$

我们从$11$枚举到$SS$，只需考虑哪些位置上面是$22$即可。

如果当前有$ii$个位置为$11$那么共有$C_n^{i}C\_n^i$ 种情况，且贡献为$2^{i}2^i$ ，然后其他位置可以为$00$，也可以为$22$。所以贡献为$2^{n-i}2^\{n-i\}$ 。所以当前的贡献就是$C_n^i\times 2^i\times 2^{n-i}=C_n^i\times 2^{n}C\_n^i\; \backslash times\; 2^i\; \backslash times\; 2^\{n-i\}\; =\; C\_n^i\; \backslash times\; 2^n$

所以最终答案为${\sum }_{i=0}^n{C}_n^i\times 2^n\backslash sum\backslash limits\_\{i=0\}^nC\_n^i\; \backslash times\; 2^n$

将$2^{n}2^n$ 提出来。那就是$2^n\times {\sum }_{i=0}^n{C}_n^{i}2^n\; \backslash times\; \backslash sum\backslash limits\_\{i=0\}^nC\_n^i$ 。

用二项式定理合并那个$\sum \backslash sum$，其实就是$2^{n}2^n$ ，所以最终答案为$4^{n}4^n$ 。

注意到当$i=0i=0$时是不符合题目要求的，所以要减去他的贡献$11$。

所以真正的最后答案是$4^n-14^n-1$

#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <cassert>
typedef long long ll;
char s[100100];
ll Mul(ll a, ll b, ll m){
	ll rnt = 0;
	a %= m;
	while(b){
		if(b & 1) rnt = (rnt + a) % m;
		a = (a << 1) % m;
		b >>= 1;
	}
	return rnt;
}
ll Pow(ll a, ll n, ll m){
    if(n == 1) return a;
	else{
		ll rnt = Pow(a, n / 2, m);
		rnt = Mul(rnt, rnt, m);
		if(n & 1) rnt = Mul(a, rnt, m);
		return rnt;
	}
	return 0;
}
int main(){
	int T; scanf("%d", &T);
	while(T--){
		ll m;
		scanf("%s%lld", s, &m);
		ll phi = m, t = m;
		for(ll i = 2; i <= t / i; ++i)
			if(t % i == 0){
				phi = phi / i * (i - 1);
				while(t % i == 0) t /= i;
			}
		if(t > 1)
			phi = phi / t * (t - 1);
		ll res = 0; bool flag = false;
		for(int i = 0; s[i]; ++i){
			res = res * 10 + s[i] - '0';
			if(res >= phi) res %= phi, flag = true;
		}
		ll ans = (Pow(4 % m, res + flag * phi, m) - 1 + m) % m;
		printf("%lld\n", ans);
	}
	return 0;
}