|
Contest Page
sol
真的有人不會做這道題？
#include<bits/stdc .h>
using namespace std;
int main(){
string s;
int N; cin >> N;
for(int i = 1 ; i <= N ; i){
cin >> s;
if(s.size() >= 2 && s[s.size() - 1] == 'K' && s[s.size() - 2] == 'A'){
for(int i = 0 ; i < s.size() - 2 ; i)
cout << s[i];
return 0;
}
}
return 0;
}
sol
$114514$只有$8$個約數(shù)，暴力統(tǒng)計數(shù)量然后人腦枚舉所有可行方案就行了。
#include<bits/stdc .h>
using namespace std;
#define int unsigned long long
const int _ = 229029 , tar[] = {2,31,1847};
signed main(){
int N; cin >> N; static int arr[_] , num[8];
for(int i = 1 ; i <= N ; i){
cin >> arr[i];
if(arr[i] != 0)
if(114514 % arr[i] == 0){
int cur = 0;
for(int j = 0 ; j < 3 ; j)
if(arr[i] % tar[j] == 0) cur |= 1 << j;
num[cur];
}
}
int p = num[7] num[6] * num[1] num[5] * num[2] num[3] * num[4] num[1] * num[2] * num[4];
cout << p * (1 num[0]);
return 0;
}
sol
把前幾項算出來丟到OEIS里發(fā)現(xiàn)遞推公式：$a_i=2a_{i-1} a_{i-2}-2a_{i-3}-a_{i-4}$，然后矩乘就行了。
#include<bits/stdc .h>
using namespace std;
#define int long long
const int MOD = 998244353;
struct matrix{
int a[4][4];
matrix(){memset(a , 0 , sizeof(a));}
int* operator [](int x){return a[x];}
matrix operator *(matrix b){
matrix c;
for(int i = 0 ; i < 4 ; i)
for(int k = 0 ; k < 4 ; k)
for(int j = 0 ; j < 4 ; j)
c[i][j] = (c[i][j] a[i][k] * 1ll * b[k][j]) % MOD;
return c;
}
}G , T;
signed main(){
int N; cin >> N;
if(N == 1) puts("0");
else if(N == 2) puts("1");
else if(N == 3) puts("2");
else if(N == 4) puts("5");
else{
T[1][0] = T[2][1] = T[3][2] = 1;
T[3][3] = 2; T[2][3] = 1; T[1][3] = MOD - 2; T[0][3] = MOD - 1;
N -= 4; G[0][0] = 0; G[0][1] = 1; G[0][2] = 2; G[0][3] = 5;
while(N){
if(N & 1) G = G * T;
T = T * T; N >>= 1;
}
cout << G[0][3];
}
return 0;
}
sol
考慮枚舉$1 \leq i$<$j \leq N$并$O(1)$計算方案數(shù)。設$p(x,y)$表示將$x$個數(shù)放到$x$個位置，其中$y$個數(shù)有限制某個位置不能放的方案數(shù)，設$S_i = \sum\limits_{j=1}^ij = \binom{i 1}{2}$。
枚舉$i,j$放在了$p_i,p_j$中多少個位置：
如果放了兩個位置，一定是$j$在$p_i$、$i$在$p_j$。如果這樣會產(chǎn)生貢獻，那么我們就用$|i-j||p_i-p_j|p(N-2,N-2)$貢獻答案；
如果放了一個位置，考慮$j$在$p_i$、$i$在$p_j$兩種情況的可行方案距離總和，有可能會出現(xiàn)$i$在$p_j$、$j$在$p_i$的情況減掉，得到可行方案距離總和$S$。我們就可以用$|i-j|Sp(N-2,N-3)$貢獻答案。
如果一個位置都沒有，就是總距離$\sum\limits_{i=1}^{N-1}S_i$減去上述兩種方案的距離乘上$|i-j|$乘上$p(N-2,N-4)$貢獻答案。
所以我們要算$p(N-2,N-2),p(N-2,N-3),p(N-2,N-4)$，直接容斥就行了。
#include<bits/stdc .h>
using namespace std;
const int MOD = 998244353;
int num[1003][3] , N , T , p[1003] , jc[1003] , inv[1003] , sum1[1003] , sum2[1003];
int poww(long long a , int b){
int times = 1;
while(b){
if(b & 1) times = times * a % MOD;
a = a * a % MOD; b >>= 1;
}
return times;
}
int ch(int a , int b){return 1ll * jc[a] * inv[b] % MOD * inv[a - b] % MOD;}
int main(){
jc[0] = 1;
for(int i = 1 ; i <= 1000 ; i) jc[i] = 1ll * jc[i - 1] * i % MOD;
inv[1000] = poww(jc[1000] , MOD - 2);
for(int i = 999 ; i >= 0 ; --i) inv[i] = inv[i 1] * (i 1ll) % MOD;
for(int i = 1 ; i <= 1000 ; i)
for(int j = 0 ; j <= i && j <= 2 ; j){
num[i][j] = 0;
for(int k = 0 ; k <= i - j ; k)
num[i][j] = (num[i][j] (k & 1 ? MOD - 1ll : 1ll) * jc[i - k] % MOD * ch(i - j , k)) % MOD;
}
for(int i = 1 ; i <= 1000 ; i) sum1[i] = sum1[i - 1] i;
for(int i = 1 ; i <= 1000 ; i) sum2[i] = (sum2[i - 1] sum1[i]) % MOD;
for(cin >> T ; T ; --T){
cin >> N; int sum = 0;
for(int i = 1 ; i <= N ; i) cin >> p[i];
if(N == 1){puts("0"); continue;}
if(N == 2){printf("%d\n" , p[1] == 1 ? 1 : 0); continue;}
for(int i = 1 ; i <= N ; i){
for(int j = i 1 ; j <= N ; j){
int val = 0;
val = (val 1ll * num[N - 2][2] *
(sum2[N - 1] - (sum1[p[i] - 1] sum1[N - p[i]]) - (sum1[p[j] - 1] sum1[N - p[j]]) abs(p[i] - p[j])) % MOD MOD) % MOD;
val = (val 1ll * num[N - 2][1] * (sum1[N - p[i]] sum1[p[j] - 1] - 2 * max(p[j] - p[i] , 0)) % MOD MOD) % MOD;
if(p[i] < p[j]) val = (val 1ll * num[N - 2][0] * (p[j] - p[i])) % MOD;
sum = (sum 1ll * val * (j - i)) % MOD;
}
}
cout << sum << endl;
}
return 0;
}
sol
考慮每一個點取正和取負對逆序對數(shù)量造成的影響。不難發(fā)現(xiàn)某個點取負可以使其子樹中所有權值絕對值比它小的和它產(chǎn)生逆序對，而大于它的則一定由這個更大的點取正或者負來確定；它取正可以使其祖先中所有權值絕對值比它小的和它產(chǎn)生逆序對。
所以每個點取正取負對逆序對數(shù)量的貢獻是獨立的，不受其他節(jié)點的影響。
把兩個的貢獻一個二維數(shù)點、一個dfs的時候維護祖先權值進行計算，然后bitset優(yōu)化背包就可以算出是否合法。
#include<bits/stdc .h>
using namespace std;
int read(){int a; scanf("%d" , &a); return a;}
const int _ = 1e5 7;
vector < int > ch[_]; int N , ts , val[_] , lsh[_] , sum[_] , add[_][2] , dfn[_] , sz[_] , ind[_];
bitset < 30001 > now;
namespace BIT{
#define lowbit(x) ((x) & -(x))
int arr[_];
void add(int x , int n){while(x <= N){arr[x] = n; x = lowbit(x);}}
int qry(int x){int sum = 0; while(x){sum = arr[x]; x -= lowbit(x);}return sum;}
}
void dfs(int x , int p){
ind[dfn[x] = ts] = x; sz[x] = 1; add[x][0] = BIT::qry(val[x]); BIT::add(val[x] , 1);
for(auto t : ch[x]) if(!sz[t]){dfs(t , x); sz[x] = sz[t];}
BIT::add(val[x] , -1);
}
#define PII pair < int , int >
void calc(){
vector < PII > qry;
for(int i = 1 ; i <= N ; i){qry.push_back(PII(dfn[i] - 1 , -i)); qry.push_back(PII(dfn[i] sz[i] - 1 , i));}
sort(qry.begin() , qry.end()); int pos = 0;
for(auto t : qry){
while(pos < t.first) BIT::add(val[ind[ pos]] , 1);
int flg = t.second < 0 ? -1 : 1 , id = abs(t.second);
add[id][1] = flg * BIT::qry(val[id]);
}
}
int main(){
N = read(); for(int i = 1 ; i <= N ; i) val[i] = lsh[i] = read();
sort(lsh 1 , lsh N 1);
for(int i = 1 ; i <= N ; i) val[i] = lower_bound(lsh 1 , lsh N 1 , val[i]) - lsh;
for(int i = 1 ; i < N ; i){
int p = read() , q = read();
ch[p].push_back(q); ch[q].push_back(p);
}
dfs(1 , 0); calc(); now[0] = 1;
for(int i = 1 ; i <= N ; i){bitset < 30001 > p = now , q = now; p <<= add[i][0]; q <<= --add[i][1]; now = p | q;}
for(int Q = read() ; Q ; --Q) puts(now[read()] ? "Orz" : "QAQ");
return 0;
}
我怎么可能會這種題
來源：https://www./content-4-461751.html
|
