T1
化一下试子就ok
code
#include<cstdio>
#include<algorithm>
inline long long read() {
long long x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1; c = getchar(); }
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
long long n;
long long a[100007];
long long sum[100007];
long long sum2[100007];
int main() {
n = read();
for(long long i = 1;i <= n;++ i) a[i] = read(),sum[i] = sum[i - 1] + a[i],sum2[i] = sum2[i - 1] + a[i] * a[i];
for(long long i = 1;i <= n;++ i) {
long long s1 = sum2[i - 1] + sum2[n] - sum2[i];
long long s = sum[i - 1] + sum[n] - sum[i];
long long ans = (n - 1) * s1 - s * s ;
if(i != n) printf("%lld ",ans);
else printf("%lld",ans);
}
return 0;
}
T2
设(g(n))为长为n的环的方案数
设(f(n))为长为n的序列方案书
容易得到递推式
(g(n) = f(n) - g(n - 1))
由于(a_1>a_n)的时候不好处理,我们直接把环转一下,让1位置为最小值
对于(f(n))可以容斥求得
[f_i = sum_j f_j imes min(a[j+1... i]) imes (-1)^{i-j-1} \
f_i = (-1)^{i} sum_jmin(a[j+1...i]) imes f_j imes (-1)^{j-1}]
考虑 i 转移到 i+1 时候:
[min(a[j+1...i]) o min(a[j+1...i+1]
]
单调栈为维护一下就好了,单调栈维护
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define pc putchar
#define gc getchar
inline int read() {
int x = 0,f = 1;
char c = gc();
while(c < '0' || c > '9') c = gc();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc();
return x * f;
}
#define LL long long
const int mod = 1000000007;
void print(LL x) {
if(x < 0) {
pc('-');
x = -x;
}
if(x >= 10)print(x / 10);
pc(x % 10 + '0');
}
#define INF 0x3f3f3f3f3f3f3f3fLL
const int maxn = 4000007;
LL a[maxn],b[maxn];
int n;
inline void mo(LL &x,LL y) {
x = ((x + y ) % mod + mod) % mod;
}
LL st[maxn][3];
int main() {
n = read();
a[1] = read();
if(n == 1) {
print(a[1]);
}
int mn = 1;
for(int i = 2;i <= n;++ i) {
a[i] = read();
if(a[i] < a[mn]) mn = i;
}
for(int i = 1;i <= n;++ i) b[i] = a[(mn + i - 2) % n + 1];
int tp = 1;
memset(a,0,sizeof a);
LL ans = 0;
a[0] = n & 1 ? -1 : 1;
st[1][0] = INF,
st[1][1] = a[0];
for(int i = 1;i <= n;++ i) {
LL sum = 0;
for(;tp && b[i] < st[tp][0]; -- tp) mo(sum,st[tp][1]);
mo(a[i],-st[tp][2] - sum * b[i]);
st[++ tp][0] = b[i];
st[tp][1] = sum;
st[tp][2] = (sum * b[i] + st[tp - 1][2]) % mod;
st[++ tp][0] = INF;
st[tp][1] = a[i];
mo(ans,a[i]);
}
mo(ans,n & 1? - b[1]:b[1]);
print(ans);
}
T3
- 假设 ({1,2,dots, n}in S)
那么一定存在一个 (i) ,使得 (forall U) 使得 (iin U), 必有 (Uin S) .
(如果不存在,那么 (forall i, exists iin V_i, V_iin T) ,那么 ({1,2,dots, n}=igcup_i V_i in T),矛盾) - 假设 ({1,2,dots, n}in T)
那么一定存在一个 (i) ,使得 (forall U) 使得 (iin U), 必有 (Uin T) .
(如果不存在,那么 (forall i, exists iin V_i, V_iin S) ,那么 ({1,2,dots, n}=igcup_i V_i in S),矛盾)
(2^0 , 2^1, dots, 2^{n-1}) ,
假设 (K=2^{a_0}+2^{a_1}+dots +2^{a_s})
咕咕咕