Problem: 有 n 个不同的数列成一个队列，现在可以若干次选择两个数交换位置，每个数只能被交换 一次。现在 L想知道能得到多少种不同的队列。输入 第一行是一个整数 T，表示有 T组数据 接下来 T行，每一行是一个整数N表示数量输出 T行，每行一个正整数表示这组数据的答案（模1e9+7的值） 1<=N<=1000 000，1<=T<=100 000
Solution: 数据挺吓人的，试图找了下规律，什么都没有。 肯定不能对于每行都在线算的，应该是一个O(n)预处理。 考虑dp，设dp[i]为i个数的答案。 对于每一个数 1.不与前面的任何一个数交换(+dp[i-1]) 2.与前面的某一个数交换，可以和i-1个人交换，每次交换过后剩下的i-2个人可以随意搭配(+dp[i-2]*(i-1))
Code
#include<bits/stdc++.h> #define N 1000005 const int mod=1000000007; using namespace std; int dp[N];//第i个数之前的方案数 inline void init() { dp[0]=dp[1]=1; for(int i=2;i<=N;i++) { dp[i]=dp[i-1]+(long long)(i-1)*dp[i-2]%mod; dp[i]%=mod; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); init(); int t; cin>>t; while(t--) { int x; cin>>x; cout<<dp[x]<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9390444.html
相关资源：各显卡算力对照表！