Alice and Bob are playing a game. This game is played with several identical pots and one marble. When the game starts, Alice puts the pots in one line and puts the marble in one of the pots. After that, Bob cannot see the inside of the pots. Then Alice makes a sequence of swappings and Bob guesses which pot the marble is in. In each of the swapping, Alice chooses two different pots and swaps their positions.
Unfortunately, Alice's actions are very fast, so Bob can only catch k of m swappings and regard these k swappings as all actions Alice has performed. Now given the initial pot the marble is in, and the sequence of swappings, you are asked to calculate which pot Bob most possibly guesses. You can assume that Bob missed any of the swappings with equal possibility.
Input
There are several test cases in the input file. The first line of the input file contains an integer N (N ≈ 100), then N cases follow.
The first line of each test case contains 4 integers n, m, k and s(0 < s ≤ n ≤ 50, 0 ≤ k ≤ m ≤ 50), which are the number of pots, the number of swappings Alice makes, the number of swappings Bob catches and index of the initial pot the marble is in. Pots are indexed from 1 to n. Then m lines follow, each of which contains two integers ai and bi (1 ≤ ai, bi ≤ n), telling the two pots Alice swaps in the i-th swapping.
Outout
For each test case, output the pot that Bob most possibly guesses. If there is a tie, output the smallest one.
Sample Input
3 3 1 1 1 1 2 3 1 0 1 1 2 3 3 2 2 2 3 3 2 1 2
Sample Output
2 1 3
题意：开始小球在s碗中，但小明只能看到接下来m次交换的k个，且是随机的.
思路：dp[i][j][l]代表执行到第i次操作，看到j次，小球的l碗中的概率.若本次可以看到,若恰好是交换的小球所在的碗,则
dp[i][j][l] += dp[i-1][j-1][sw[i][..]],若不是,dp[i][j][l] += dp[i-1][j-1][l]，若本次看不到,dp[i][j][l] += dp[i-1][j][l]
代码：
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const double esp = 1e-7;
const int ff = 0x3f3f3f3f;
map<int,int>::iterator it;
int n,m,k,s;
int sw[52][2];
long long dp[52][52][52];//第几次,看到几次,现在球的位置
int main()
{
int t;
cin>>t;
while(t--)
{
mem(dp,0);
cin>>n>>m>>k>>s;
for(int i = 1;i<= m;i++)
cin>>sw[i][0]>>sw[i][1];
dp[0][0][s] = 1;
for(int i = 1;i<= m;i++)
{
dp[i][0][s] = 1;
for(int j = 1;j<= i&&j<= k;j++)
{
for(int l = 1;l<= n;l++)
{
//如果这次看到了
if(l == sw[i][0])
dp[i][j][l] += dp[i-1][j-1][sw[i][1]];
else if(l == sw[i][1])
dp[i][j][l] += dp[i-1][j-1][sw[i][0]];
else
dp[i][j][l]+= dp[i-1][j-1][l];
//如果这次没看到
dp[i][j][l]+= dp[i-1][j][l];
}
}
}
int ans = 1;
for(int i = 2;i<= n;i++)
{
if(dp[m][k][i]> dp[m][k][ans])
ans = i;
}
cout<<ans<<endl;
}
return 0;
}