HDU 4259 Double Dealing(離散数学)#By Plato


http://acm.hdu.edu.cn/showproblem.php?pid=4259
あなたにn枚のカードをあげて、k人に分けて、1-nから順番に分けます.そして、再びカードを一緒に置きます.1人目の人は一番上に、後ろの人は順番に下に置きます.もう一度分けて、置いて、何回聞いたら元に戻りますか.
Idea:
素朴な思想:シミュレーションは各点に対して変換を行って、それぞれ周期Ciを求めて、それから彼らの最小公倍数を求めます.(TLE)
最適化:ある位置のカードがAからAに戻ると、A->B->C->...->Aの密閉サイクルが経験されることがわかり、サイクル内の各要素について、いずれかの要素を計算するだけでよい.
【ついでにHDUピットお父さんのlong long出力に突っ込み、printf("%lld",ans)でWAに違いない.G++でもC++でも.そしてpirntf("%I 64 d",ans)、cout<#include <cstdio> #include <iostream> #include <fstream> #include <cstring> using namespace std; long long gcd(long long a,long long b) { return b?gcd(b,a%b):a; } int main() { freopen("test.txt","r",stdin); int N,K; while (scanf("%d%d",&N,&K),N|| K) { static int rec[810][810]; static int a[810]; int num = 1; for (int i = 1;;i++) { for (int j = 1;j <= K;j++) { rec[i][j] = num++; if (num >N) break; } if (num > N) break; } num = 1; for (int i = 1;i <= K;i++) { for (int j = (N-i)/K+1;j >= 1;j--) { a[num++] = rec[j][i]; } } static bool vd[810]; memset(vd,0,sizeof(vd)); long long ans = 1; for (int i = 1;i <= N;i++) { if (vd[i]) continue; num = i; long long count = 0; do { num = a[num]; vd[num] = true; count++; } while (num != i); ans = ans/gcd(ans,count)*count; } printf("%I64d
",ans); } return 0; } /* for (int i = 1;i <= K;i++) { for (int j = (N- i)/K *K + i;j > 0;j -= K) { a[num++] = j; } } */

Add:位置交代の原理と実現
a[i] = j;位置iが位置jのカードに置き換えられることを示す.
i<-j <-k;i変換を2回要求してそのカードに置き換えられた場合、すなわちj変換がどのカードに置き換えられるかを求める.もちろんここのi,j,kはいずれも初回の初期位置番号であり、カードとしても理解できる.
実現するには,1)main()では逆順で読む方法を先に区別することが直感的である.
2)他の人のプログラムを見て、一歩一歩の方法で、
for (int i = 1;i <= K;i++)
{
 for (int j = (N- i)/K *K + i;j > 0;j -= K)
{ a[num++] = j; }
}i番目の列について、その持つ要素の個数が(N-i)/K+1であることを知れば、よく理解できる