1001： 可以证明(扩展欧几里得)，只要卡片中有两个卡片互素，旁边点就是可达的。 因此只需要算出所有卡片不互素的情况有多少种，可用容斥原理。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector> using namespace std; typedef __int64 ll; ll A, B;
ll prime[] = {, , , , , , , , };
ll ans;
bool vis[]; vector<ll> yinzi(ll x) {
vector<ll> res;
for (int i = ; i < ; i++) if ( == x%prime[i]) {
res.push_back(prime[i]);
}
return res;
} ll my_pow(ll d, ll n) {
ll res = ;
while (n) {
if (n&) res *= d;
d *= d;
n >>= ;
}
return res;
} void dfs(const vector<ll> &d, int cnt, ll tmp, ll flag) {
if (cnt >= d.size()) return ;
int i = cnt;
ll t = B/d[i]/tmp;
ans += flag * my_pow(t, A);
dfs(d, cnt+, tmp*d[i], -*flag);
dfs(d, cnt+, tmp, flag);
} int main() {
// freopen("1001.txt", "r", stdin); int T;
scanf("%d", &T); while (T--) {
scanf("%I64d%I64d", &A, &B);
ans = my_pow(B, A);
dfs(yinzi(B), , , -);
memset(vis, false, sizeof(vis));
printf("%I64d\n", ans);
} return ;
}
1001
1002: 括号匹配，区间dp
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int MAXN = ; int dp[MAXN][MAXN];
char str[MAXN]; int dfs(int L, int R) {
if (-!=dp[L][R])
return dp[L][R];
int &res = dp[L][R] = ;
if (('('==str[L]&&str[R-]==')') || ('['==str[L]&&str[R-]==']'))
res = dfs(L+, R-) + ;
for (int i = L+; i < R; i++)
res = max(res, dfs(L, i)+dfs(i, R));
return res;
} int main() {
#ifdef Phantom01
freopen("1002.txt", "r", stdin);
#endif // Phantom01 int Case;
scanf("%d", &Case);
gets(str); while (Case--) {
gets(str);
int len = strlen(str);
memset(dp, -, sizeof(dp));
printf("%d\n", len - *dfs(, len));
} return ;
}
1002
1003：最小生成树
已知经纬度求球面距离 连接
代码略。
1004： 直接大数模拟。
代码略