MnZn刚学oi
查看原帖
MnZn刚学oi
53769
北文楼主2023/5/2 16:10

我这题做法就是每次合并两个镜子,我计算出1号到i-1号合并出来的镜子的a和b,然后取合并i号。但是为什么合并的顺序会对答案影响呢?
AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
ll n, a1, b1, a2, b2;
ll ksm(ll a, ll z, ll p) {
	ll ret=1;
	while(z) {
		if(z&1) ret=ret*a%p;
		a=a*a%p;
		z>>=1;
	}
	return ret;
}
int main() {
	int inv100=ksm(100, mod-2, mod);
	scanf("%lld", &n);
	scanf("%lld %lld", &a1, &b1);
	a1=1ll*a1*inv100%mod;
	b1=1ll*b1*inv100%mod;
	for(int i=2; i<=n; i++) {
		scanf("%lld %lld", &a2, &b2);
		a2=1ll*a2*inv100%mod;
		b2=1ll*b2*inv100%mod;
		ll inv=ksm((1ll-1ll*b1*b2%mod+mod)%mod, mod-2, mod);
		b1=(b2+a2*a2%mod*b1%mod*inv)%mod;
		a1=a1*a2%mod*inv%mod;
	} 
	printf("%lld", 1ll*a1%mod);
	return 0;
}

不通过的代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
ll n, a1, b1, a2, b2;
ll ksm(ll a, ll z, ll p) {
	ll ret=1;
	while(z) {
		if(z&1) ret=ret*a%p;
		a=a*a%p;
		z>>=1;
	}
	return ret;
}
int main() {
	int inv100=ksm(100, mod-2, mod);
	scanf("%lld", &n);
	scanf("%lld %lld", &a1, &b1);
	a1=1ll*a1*inv100%mod;
	b1=1ll*b1*inv100%mod;
	for(int i=2; i<=n; i++) {
		scanf("%lld %lld", &a2, &b2);
		
		a2=1ll*a2*inv100%mod;
		b2=1ll*b2*inv100%mod;
		swap(a1, a2);
		swap(b1, b2);
		ll inv=ksm((1ll-1ll*b1*b2%mod+mod)%mod, mod-2, mod);
		b1=(b2+a2*a2%mod*b1%mod*inv)%mod;
		a1=a1*a2%mod*inv%mod;
	} 
	printf("%lld", 1ll*a1%mod);
	return 0;
}
2023/5/2 16:10
加载中...