链接：
https://vjudge.net/problem/LightOJ-1318
题意：
In a country named "Ajob Desh", people play a game called "Ajob Game" (or strange game). This game is actually a game of words. The rules for the game are as follows:
It's an N player game and players are numbered from 1 to N. And the players alternate turns in a circular way. Player 1 starts first. The next turn is for player 2, then player 3 and so on. After the turn for the Nth player, player 1 gets his turn again and the same procedure is continued.
In each turn a player has to propose a pair of words. Each of the words should have length L, and the words should differ in exactly M positions. As their language has K alphabetical symbols, a word is a collection of symbols from these K alphabets.
The pair of words proposed by a player should differ in exactly M positions, it means that there should be exactly M positions where the two words have different symbols, and in other positions they have same symbols. For example, 'abc' and 'abd' differ in exactly 1 position, 'abc' and 'aca' differ in exactly 2 positions, 'abc' and 'cab' differ in exactly 3 positions.
In each turn a player has to propose a new pair of words. Two pairs are different if at least one word is different. Note that here pair refers to unordered pair. Let A, B, C be three different words, then (A, B) and (B, A) are same, but (A, C) and (A, B) are different. For example, if a player already proposed {abc, def}, then none can propose {abc, def} or {def, abc}. But a player can propose {abc, fed} or {abc, abc} or {pqc, abc} etc.
If a player fails to propose a new pair of words, he is treated as the loser of the game. And the game ends.
Let N = 2, K = 2, L = 2, M = 1 and the alphabet is {ab}. All the words of length 2 are: {aa, ab, ba, bb}. Player 1 chooses pair {aa, ab} (differs in 1 position as M = 1) then player 2 chooses pair {ab, bb}. After that player 1 chooses {aa, ba} then player 2 chooses {bb, ba}. And then there is no pair left for player 1, and so, player 1 will lose.
Now this game is played by N players who know this game very well thus they play optimally. You are given N, K, L and M; you have to find the loosing player.
思路:
一对字符串，一边是，\(k^l\)种，同时另一边需要有m个不同，则是\((k-1)^m\)
共有\(C_l^m*(k-1)^m*k^l\)
同时有重复，要除2，考虑2和n不一定互质，当k为偶数时用k/2，否则用(k-1)/2
代码：
// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string.h>
#include<set>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MOD = 1e9+7;
const int MAXN = 1e6+10;
LL n, k, l, m;
int pos;
int Pri[MAXN], Isp[MAXN], Cnt[MAXN];
void Init()
{
pos = 0;
for (int i = 2;i < MAXN;i++)
{
if (Isp[i] == 0)
Pri[++pos] = i;
for (int j = 1;j <= pos && 1LL*i*Pri[j] < MAXN;j++)
{
Isp[i*Pri[j]] = 1;
if (i%Pri[j] == 0)
break;
}
}
}
void Upd(LL x, int sta)
{
for (int i = 1;i <= pos;i++)
{
LL tmp = x;
while(tmp)
{
Cnt[i] += sta*(tmp/Pri[i]);
tmp /= Pri[i];
}
}
}
LL PowMod(LL a, LL b, LL p)
{
LL res = 1;
while(b)
{
if (b&1)
res = res*a%p;
a = a*a%p;
b >>= 1;
}
return res;
}
LL C(LL n, LL m, LL p)
{
memset(Cnt, 0, sizeof(Cnt));
Upd(l, 1), Upd(m, -1), Upd(l-m, -1);
LL ans = 1;
for (int i = 1;i <= pos;i++)
ans = ans*PowMod(Pri[i], Cnt[i], p)%p;
return ans;
}
int main()
{
// freopen("test.in", "r", stdin);
Init();
int t, cas = 0;
scanf("%d", &t);
while(t--)
{
printf("Case %d:", ++cas);
scanf("%lld%lld%lld%lld", &n, &k, &l, &m);
LL ans;
if (m != 0)
{
if (k&1)
ans = C(l, m, n)*PowMod(k, l, n)%n*PowMod(k-1, m-1, n)%n*(k/2)%n;
else
ans = C(l, m, n)*PowMod(k, l-1, n)%n*PowMod(k-1, m, n)%n*(k/2)%n;
}
else
ans = PowMod(k, l, n);
printf(" %lld\n", ans+1);
}
return 0;
}