首页 > 其他分享 >P10185的题解

P10185的题解

时间:2024-03-27 12:35:40浏览次数:29  
标签:md int 题解 200010 ss P10185 x%

(一)

考虑对每一种颜色单独求解。

对于一次第 \(k\) 种的“循环”,美丽度会加上

\[\sum_{i=1}^{a_k}C_{n}^{i}\times v_k^{i}=(v_k+1)^{a_k}-1 \]

相信大家都学过二项式定理。

“循环”次数取决于其他珠子是否出现,即 \(2^{\sum_{i=1}^{a_i}-a_k}\)。

再将两式相乘就愉快 AC 了。

(二)

警钟敲烂:注意输入格式。

我调了 \(1\) 天。

(三)

AC 代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200010],v[200010],ans,pw[200010];
const int md=1e9+7;
int pow(int x,int y){
	int ss=1;
	while(y){
		if(y&1)ss=ss*x%md;
		x=x*x%md;
		y>>=1;
	}
	return ss;
}
signed main(){
	scanf("%lld",&n);
	int s=0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i];
	for(int i=1;i<=n;i++)scanf("%lld",&v[i]);
//	pw[0]=1;
//	for(int i=1;i<=s;i++)pw[i]=pw[i-1]*i%md;
//	for(int i=0;i<=a[1];i++)
//		for(int j=0;j<=a[2];j++){
//			if(i==0&&j==0)continue;
//			else if(j==0)ans=(ans+pow(v[1],i)*C(a[1],i)%md)%md;
//			else if(i==0)ans=(ans+pow(v[2],j)*C(a[2],j)%md)%md;
//			else ans=(ans+((pow(v[1],i)+pow(v[2],j))%md*C(a[1],i)%md*C(a[2],j)%md))%md;
//		}
//	printf("%lld\n",ans);
//	return 0;
	for(int i=1;i<=n;i++){
		ans=(ans+pow(2ll,s-a[i])*((pow(v[i]+1ll,a[i])-1ll+md)%md)%md)%md;
	}
	printf("%lld\n",ans);
	return 0;
}

标签:md,int,题解,200010,ss,P10185,x%
From: https://www.cnblogs.com/Jh763878/p/18098704

相关文章

  • CF1904C的题解
    (一)不太好想。(我看了题解才会)当\(k>2\)时,可以选两次相同的\(i\)和\(j\)。再将生成的数做差。当\(k=1\)时,直接\(Θ(n^2)\)枚举。当\(k=2\)时,先枚举第一次的\(i\)和\(j\),再用lower_bound()实现查找第二次选择的数。时间复杂度\(Θ(n^2\log_2{n})\)。注......
  • CF1929C的题解
    (一)每次下注,要么赚\(y\times(k-1)\),要么亏\(y\)。由于不知道什么时候会输,每次都下能赚回前面所有的金额好了。第一次下\(1\),共下\(x+1\)次。(二)AC代码。#include<bits/stdc++.h>usingnamespacestd;intt,k,x,a;intmain(){ scanf("%d",&t); while(t--){ scan......
  • CF1213D1的题解
    (一)直接暴力!!!对于每一个数,枚举它能生成的数。然后对于每一个可能的答案,开长度为\(k\)的优先队列维护,同时统计操作次数和。时间复杂度为\(Θ(\log^2_2n)\)。惊讶地发现顺便把双倍经验给切了。(卡过)(二)AC代码。#include<bits/stdc++.h>usingnamespacestd;intcnt,n,k,su......
  • CF1922C的题解
    (一)从\(i\)到\(j\)有两种走法,一种是用\(a_j-a_i\)的代价,一种是用\(1\)的代价,前提是\(j\)是\(i\)最近的。显然如果符合条件选第二种。先考虑从左向右走。(和从右向左相同)考虑走到了节点\(i\),如果\(a_{i+1}-a_{i}>a_{i}-a_{i-1}\),那么花费\(1\)的代价向右走,否则花......
  • AT_arc169_a的题解
    (一)由于每次把子节点的权值加到父节点中,深度越深影响越大。将\(1\)号节点视作父节点,不难发现,同一深度的节点对其贡献度相等,都为\(1\timesnow\val\)。因为\(10^{100}\)极大,所以统计每层权值和,从深往浅扫。(二)AC代码。#include<bits/stdc++.h>#defineintlonglongus......
  • CF1922B的题解
    (一)因为\(2^{n}+2^{n}=2^{n+1}\)。设取的三个数为\(2^i\),\(2^j\),\(2^k\),\(i\lej\lek\)。因为\(2^i+2^j>2^k\),所以\(j=k\)。(反证法易证)此时\(i\)任意取。注意不要重复取。将答案分为两类计算,\(i=j=k\)和\(i<j=k\)。(二)AC代码。#include<bits/stdc++.h>#define......
  • 20240327每日一题题解
    20240327每日一题题解Problem一些整数可能拥有以下的性质:性质1:是偶数;性质2:大于\(4\)且不大于\(12\)。小A喜欢这两个性质同时成立的整数;Uim喜欢这至少符合其中一种性质的整数;小B喜欢刚好有符合其中一个性质的整数;正妹喜欢不符合这两个性质的整数。现在给出一个......
  • 第三届信大超越杯团体赛题解
    第三届信大超越杯团体赛题解A红红找蓝蓝​​​​题解:宽搜bfs,定义状态{x,y,d,Dir}表示:到(x,y)点拐了d次弯,上一次的方向为Dir与最短路不同的是,我们从一个点出发要把一个方向上的所有点加入队列,因为这个方向上所有点的拐弯数都只是+1,为了维护先搜到的点拐弯数越少,就要把一个方向......
  • 【蓝桥杯选拔赛真题48】C++九进制回文数 第十四届蓝桥杯青少年创意编程大赛 算法思维
    目录C++九进制回文数一、题目要求1、编程实现2、输入输出二、算法分析三、程序编写四、程序说明五、运行结果六、考点分析七、推荐资料C++九进制回文数第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题一、题目要求1、编程实现提示信息:回文数:反向排列与原......
  • [题解]P5858 Golden Sword
    P5858「SWTR-3」GoldenSword第一道自己想出递推公式并且成功\(AC\)的\(dp\)绿题。题意简述有\(n\)种原料,每个原料有一个耐久度\(a[i]\),必须按照\(1,2,…,n\)的顺序放入炼金锅。但是炼金锅的容量是有限的,只有\(w\),所以在每次放入原料之前,都可以选择取出\(0\sims\)个原料再放......