A
赶火车
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4 Accepted Submission(s): 4
Problem Description
小伙伴们愉快地结束了暑假wannafly训练营的生活，决定返回学校，早上小伙伴们要赶到高铁站，高铁将在y分钟后停止检票，但他们发现了一件尴尬的事情——他们不认路。
这个城市的道路是非常诡异的，在他们面前有n+m条路，其中n条路是正确的，如果走正确的路，将会在ai分钟后走到高铁站，另外m条路是不正确的，如果走不正确的路，将会在bi分钟后回到起点。
小伙伴们只能随机选择一条路走，但他们记性很差，即使走过一条不正确的路，他们也可能会再次选择这条路。
小伙伴们是非常谨慎的人，他们想要计算到达高铁站所需时间的期望EX，如果EX≤y，那么就出发，否则就退票。
Input
第一行是一个整数T，表示有T组数据，接下来T组数据，每组数据包含三行：
n,m,y
a1,a2,...,an
b1,b2,...,bm
含义如题中所述
1≤T≤100,1≤n,m≤10,1≤ai,bi,y≤1000
Output
对于每组数据，如果要出发，那么就输出“Go”，否则输出“Wait”，不含引号。
Sample Input
2 4 7 2 1 1 1 1 1 1 1 1 1 1 1 7 4 2 1 1 1 1 1 1 1 1 1 1 1
Sample Output
Wait Go
//
//#include <bits/stdc++.h>
//#include <time.h>
//#define fi first
//#define se second
//#define endll "\n"
//#define MS0(X) memset((X), 0, sizeof((X)))
//#define MS1(X) memset((X), -1, sizeof((X)))
//#define LEN(X) strlen(X)
//#define INF 0x3f3f3f3f3f3f3f3f
//#define inf 0x3f3f3f3f
/vector(len,val);
//using namespace std;
//
//typedef long long ll;
//typedef double db;
//int xx[4] = {1,-1,0,0};
//int yy[4] = {0,0,1,-1};
//const double eps = 1e-9;
//typedef pair<int,int> P;
//const int maxn = 2e6 + 5000;
//const ll mod = 1e9 + 7;
//inline int sign(db a) { return a < -eps ? -1 : a > eps;}
//inline int cmp(db a,db b){ return sign(a - b);}
//void debug(int x){ cout << x << endl; }
//ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
//ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
//
//int fa[maxn];
//int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
//ll c,n,k,m,y;
//ll a[maxn];
//ll s[maxn];
//int main() { int t;
// ios::sync_with_stdio(false);
// ll x,y;
// cout << 1380.9 << endl;cin >> t;while(t--){cin >> n;cout << n * (n - 1) / 2 + n - 1 << endl;
// n * (n + 3ll ) / 2ll}cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
// return 0;
//}
//
15 + 40 + 54 + 48 + 25
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se second
#define endll "\n"
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
///vector(len,val);
using namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
void debug(int x){ cout << x << endl; }
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}int fa[maxn];
int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
ll c,n,k,m,y;
ll a[maxn];
ll s[maxn];
int main() { int m,t;ios::sync_with_stdio(false);cin >> t;while(t--){cin >> n >> m >> y;y *= n;ll ans = 0;for(int i = 1;i <= n + m;i++){ll x; cin >> x; ans += x;}if(ans <= y) cout << "Go" << endl;else cout << "Wait" << endl;}
// cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}//15 +
B
美丽度
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1 Accepted Submission(s): 1
Problem Description
街道上依次坐落着n个景点，每个景点都有一个美丽度a[i]。
定义[l,r]之间景点的美丽度为(r-l+1)*a[l]+(r-l)*a[l+1]+...+2*a[r-1]+1*a[r]
现在我们想要知道对于所有的子区间，景点的美丽度和为多少。
Input
第一行输入一个整数n(1<n<=1000000)，
第二行输入n个整数。
0<=ai<=1e9
Output
输出所有区间的美丽度和(由于输出结果太大，答案取模1e9+7)。
Sample Input
3 1 2 3
5 1 2 3 4 5
Sample Output
27 182
很简单一个题，把两个样例写出来就可以看出贡献了
a_i的贡献为 a[i] * i * (n - i + 1) * (n - i + 2) / 2，注意取模
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se second
#define endll "\n"
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
///vector(len,val);
using namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
void debug(int x){ cout << x << endl; }
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}int fa[maxn];
int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
ll c,n,k,m,y;
ll a[maxn];
ll s[maxn];
int main() { int m,t;ios::sync_with_stdio(false);while(cin >> n){for(int i = 1;i <= n;i++) cin >> a[i];ll cnt = n,ans = 0;for(ll i = 1;i <= n;i++){ll x = (1ll + cnt) * cnt / 2ll; x %= mod;ans += (x * a[i]) % mod * i % mod;ans %= mod;cnt--;}cout << ans << endl;}
// cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}//15 + 40 + 54 + 48 + 25C:没意义略
D:
定理证明
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1 Accepted Submission(s): 1
Problem Description
现在我们有n个定理，并且这n个定理是等价的，也就是说从任意一个定理出发，都可以推出其他所有的定理。
例如
定理1：有上界的实数集合必有上确界
定理2：有界实数列必有收敛子列
定理3：单调有界的实数列一定收敛
一共存在定理1→定理2、定理2→定理1、定理1→定理3、定理3→定理1、定理2→定理3、定理3→定理2这六种推导关系，但很显然有些推导是冗余的，例如，如果已经证明了定理1→定理2、定理2→定理3，那么定理1→定理3是显然成立的，证明定理1→定理3就是多余的。
请问我们最多可以按顺序写出多少个推导关系，使得其中任意一个推导关系和前面的结合起来不是多余的？
Input
第一行是一个整数T，表示有T组数据，接下来T组数据，每组数据包含一个整数n表示定理的个数。
1≤T≤100,1≤n≤1000
Output
对于每组数据，输出答案除以 10^9+7 的余数。
Sample Input
3 1 2 3
Sample Output
0 2 5
Hint
证明定理1→定理2、定理2→定理3，那么定理1→定理3是冗余的 证明定理1→定理2、定理1→定理3，那么定理2→定理3不是冗余的
手动写到5就可以发现规律了 ，n --, n * (n + 3) / 2，比较简单
代码略