GigCombinatorics

NC223555. GigCombinatorics

描述

Your friend Tóti is an aspiring musician. He has written $n$ songs, each of which has a hype rating of either $1$ , $2$ , or $3$ .A higher hype rating means the song has more energy. Tóti is planning his first live performance and needs your help. He wants to know how many setlists he can make. A setlist consist of at least three songs, the first song must have hype rating $1$ , the last song must have hype rating $3$ , and all other songs must have hype rating $2$ . Tóti also wants to play the songs in the same order he wrote them.

Given the hype rating of each of Tóti’s songs in the order he wrote them, how many setlists can he make?

输入描述

The first line of input consists of an integer  (),  the number of songs Tóti has written. The second line consists of  integers ,each in , giving the hype ratings of the .

输出描述

Output the number of setlists Tóti can make. Since this number can be large, print it modulo .

示例1

输入:

9
1 1 1 2 2 2 3 3 3

输出:

示例2

输入:

8
1 2 1 2 3 1 2 3

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 179ms, 内存消耗: 452K, 提交时间: 2021-09-10 22:48:58

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, s, p1=0, p2=0, p3=0,mod = 1e9+7;
	cin >> n;
	while(n--){
		cin >>s;
		if(s == 1)p1++;
		else if(s == 2)p2 = (p2 * 2 + p1) % mod;
		else p3 = (p3 + p2) % mod;
	}
	cout <<p3<<endl; 
return 0;
}

Python3 解法, 执行用时: 717ms, 内存消耗: 18300K, 提交时间: 2021-08-03 13:37:01

n=int(input())
z=input().split()
ans=0
tmp=0
coun=0
for i in range(1,n+1):
	if(z[i-1]=='2'):
		tmp*=2
		tmp=tmp%1000000007
	elif(z[i-1]=='1'):
		tmp+=1
		coun+=1
	else:
		ans+=tmp-coun
		ans=ans%1000000007
print(ans)

上一题

下一题

详情