Codeforces 1117D
题意：一列魔石排成一排，一块魔石可以分裂成$m$块魔石，你可以选择任意魔石进行分裂，求最后$n$块魔石的方案数。$n \leq 10^{18}$
可以发现组合数公式，即选择出魔石出来分裂，但是并不能通过。
可以考虑DP($n \leq 10^{18}$也是可能DP的，小心，矩阵快速幂)，设$dp(i)$为$i$个未分裂魔石时的方案。则
$$
dp(i)=dp(i-1)+dp(i-m)
$$
那么就可以矩阵快速幂了。
Codeforces 1117E
题意：现在有一个长度 $\leq10000$ 的字符串和一个位置上的双射 $f$ ，使得字符串 $i$ 上的字符换到 $f(i)$ 上来。
交互题其实就是数字游戏……
把题目里的数字拿出来，即$3,26,10000$
考虑关系，则发现$26^2\leq 10000 \leq 26^3 $
就考虑如何一次交互如何扩大 $26$ 倍
以下转载自题解 CF1117E【Decypher the String】 - sysjuruo 的博客 - 洛谷博客
我们可以通过以下方式
第一次:
aaa...aaa(26∗26)bbb...bbb(26∗26)ccc...ccc(26∗26)...
我们称 $26 \times 26$ 个为一个大块
第二次:
aaa...aaa(26)bbb...bbb(26)ccc...ccc(26)...
第三次:
abcdefg...xyzabcdefg...xyz
这样，对于一个位置$i$，第一次我们可以知道 $f(i)$ 属于哪一个大块，第二次可以知道属于哪一个小块，第三次便可以知道属于哪里
我们称 $26$ 个为一个小块
知识点：
1、$n \leq 10^{18}$也是可能DP的，小心，矩阵快速幂
1117D：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 1000000007ll;
LL n, m;
struct mat {
LL a[205][205];
mat() {ms(a, 0);}
} tr, f;
mat mul(mat a, mat b) {
mat ret;
for (LL i = 1ll; i <= m; ++i) {
for (LL j = 1ll; j <= m; ++j) {
for (LL k = 1ll; k <= m; ++k) {
ret.a[i][j] = (ret.a[i][j] + a.a[i][k] * b.a[k][j] % MO) % MO;
}
}
}
//for (LL i = 1; i <= m; ++i, putchar('\n')) for (LL j = 1; j <= m; ++j) printf("%lld ", ret.a[i][j]);
return ret;
}
mat ksm(mat a, LL b) {
mat ans, bs = a;
LL fl = 0ll;
while (b) {
if (b & 1ll) {
if (fl == 0ll) fl = 1ll, ans = bs;
else ans = mul(ans, bs);
}
bs = mul(bs, bs);
b >>= 1ll;
}
return ans;
}
void clean() {
}
int solve() {
clean();
cin >> n >> m;
if (n == m) return printf("2\n"), 0;
if (n < m) return printf("1\n"), 0;
for (LL i = 1; i < m; ++i) {
tr.a[i][i + 1] = 1;
}
tr.a[m][1] = tr.a[m][m] = 1;
for (LL i = 1; i < m; ++i) f.a[1][i] = 1;
f.a[1][m] = 2;
tr = ksm(tr, n - m);
f = mul(f, tr);
printf("%lld\n", f.a[1][m]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
1117E：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 20000 + 5;
string s, t, pt;
int n, bl[MAXN];
char ans[MAXN];
void clean() {
}
int solve() {
clean();
cin >> s;
n = s.length();
// 1
pt = "? ";
char ch = 'a';
for (int i = 0; i < n; ++i) {
pt += ch;
if ((i + 1) % (26 * 26) == 0) ++ch;
}
cout << pt << endl;
cin >> t;
for (int i = 0; i < n; ++i)
bl[i] += (t[i] - 'a') * (26 * 26);
// 2
pt = "? ";
ch = 'a';
for (int i = 0; i < n; ++i) {
pt += ch;
if ((i + 1) % 26 == 0) ++ch;
if (ch > 'z') ch = 'a';
}
cout << pt << endl;
cin >> t;
for (int i = 0; i < n; ++i)
bl[i] += (t[i] - 'a') * 26;
// 3
pt = "? ";
ch = 'a';
for (int i = 0; i < n; ++i) {
pt += ch++;
if (ch > 'z') ch = 'a';
}
cout << pt << endl;
cin >> t;
for (int i = 0; i < n; ++i)
bl[i] += t[i] - 'a';
for (int i = 0; i < n; ++i)
ans[bl[i]] = s[i];
cout << "! " << ans << endl;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
*/
