北京网站建设升上去,企石网站建设,网站风格评价,焦作网站建设公司排名正题
题目连接:https://www.luogu.com.cn/problem/P7887?contestId52021 题目大意
给出三个长度为nnn的序列xi,yi,zix_i,y_i,z_ixi,yi,zi#xff0c;求一个序列aaa满足0≤ai10970\leq a_i10^970≤ai1097且 xi(∑j1iaj)yi(∑jinaj)≡zi(mod1097)x_i\lef…正题
题目连接:https://www.luogu.com.cn/problem/P7887?contestId52021 题目大意
给出三个长度为nnn的序列xi,yi,zix_i,y_i,z_ixi,yi,zi求一个序列aaa满足0≤ai10970\leq a_i10^970≤ai1097且 xi(∑j1iaj)yi(∑jinaj)≡zi(mod1097)x_i\left(\sum_{j1}^ia_j\right)y_i\left(\sum_{ji}^na_j\right)\equiv z_i(mod\ 10^97)xi(j1∑iaj)yi(ji∑naj)≡zi(mod 1097)
如果只有一组解就输出这组解
1≤∑n≤2×105,1≤xi,yi1097,0≤zi10971\leq \sum n\leq 2\times 10^5,1\leq x_i,y_i10^97,0\leq z_i10^971≤∑n≤2×105,1≤xi,yi1097,0≤zi1097 解题思路
看到这个同余就感觉这题是个啥方程的做法类的 设si∑j1iajs_i\sum_{j1}^ia_jsi∑j1iaj那么有 xisiyi(sn−si−1)zix_is_iy_i(s_n-s_{i-1})z_ixisiyi(sn−si−1)zi 这样我们就有了si,si−1,sns_i,s_{i-1},s_nsi,si−1,sn之间的关系式而对于s1s_1s1我们可以直接得到它和sns_nsn的关系式 x1s1y1snz1⇒s1z1−y1snx1x_1s_1y_1s_nz_1\Rightarrow s_1\frac{z_1-y_1s_n}{x_1}x1s1y1snz1⇒s1x1z1−y1sn
这样我们可以设siAiBisns_iA_iB_is_nsiAiBisn然后用上面的式子化为 siziyisi−1−yisnxis_i\frac{z_iy_is_{i-1}-y_is_n}{x_i}sixiziyisi−1−yisn
推出后面的A,BA,BA,B最后有 snAnBnsn⇒snAn1−Bns_nA_nB_ns_n\Rightarrow s_n\frac{A_n}{1-B_n}snAnBnsn⇒sn1−BnAn
当然Bn1B_n1Bn1时需要判断AnA_nAn是否为000来得到解数。 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510,P1e97;
ll T,n,x[N],y[N],z[N],a[N],b[N],s[N];
ll power(ll x,ll b){ll ans1;x%P;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
};
signed main()
{scanf(%lld,T);while(T--){scanf(%lld,n);for(ll i1;in;i)scanf(%lld%lld%lld,x[i],y[i],z[i]);ll invpower(x[1],P-2);a[1]z[1]*inv%P;b[1](P-y[1])*inv%P;for(ll i2;in;i){invpower(x[i],P-2);a[i](a[i-1]*y[i]%Pz[i])*inv%P;b[i](b[i-1]*y[i]%P-y[i]P)%P*inv%P;}if(b[n]1){printf(%lld\n,a[n]?0:P);continue;}s[n]a[n]*power((1-b[n]P)%P,P-2)%P;for(ll i1;in;i)s[i](a[i]b[i]*s[n]%P)%P;puts(1);for(ll i1;in;i)printf(%lld ,(s[i]-s[i-1]P)%P);putchar(\n);} return 0;
}
